filter/filter.c

   1 /*
   2  *      Filters: utility functions
   3  *
   4  *      Copyright 1998 Pavel Machek <pavel@ucw.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  *
   8  */
   9
  10 /**
  11  * DOC: Filters
  12  *
  13  * You can find sources of the filter language in |filter/|
  14  * directory. File |filter/config.Y| contains filter grammar and basically translates
  15  * the source from user into a tree of &f_inst structures. These trees are
  16  * later interpreted using code in |filter/filter.c|.
  17  *
  18  * A filter is represented by a tree of &f_inst structures, one structure per
  19  * "instruction". Each &f_inst contains @code, @aux value which is
  20  * usually the data type this instruction operates on and two generic
  21  * arguments (@a1, @a2). Some instructions contain pointer(s) to other
  22  * instructions in their (@a1, @a2) fields.
  23  *
  24  * Filters use a &f_val structure for their data. Each &f_val
  25  * contains type and value (types are constants prefixed with %T_). Few
  26  * of the types are special; %T_RETURN can be or-ed with a type to indicate
  27  * that return from a function or from the whole filter should be
  28  * forced. Important thing about &f_val's is that they may be copied
  29  * with a simple |=|. That's fine for all currently defined types: strings
  30  * are read-only (and therefore okay), paths are copied for each
  31  * operation (okay too).
  32  */
  33
  34 #undef LOCAL_DEBUG
  35
  36 #include "nest/bird.h"
  37 #include "lib/lists.h"
  38 #include "lib/resource.h"
  39 #include "lib/socket.h"
  40 #include "lib/string.h"
  41 #include "lib/unaligned.h"
  42 #include "nest/route.h"
  43 #include "nest/protocol.h"
  44 #include "nest/iface.h"
  45 #include "nest/attrs.h"
  46 #include "conf/conf.h"
  47 #include "filter/filter.h"
  48
  49 #define CMP_ERROR 999
  50
  51 static struct adata *
  52 adata_empty(struct linpool *pool, int l)
  53 {
  54   struct adata *res = lp_alloc(pool, sizeof(struct adata) + l);
  55   res->length = l;
  56   return res;
  57 }
  58
  59 static void
  60 pm_format(struct f_path_mask *p, buffer *buf)
  61 {
  62   buffer_puts(buf, "[= ");
  63
  64   while (p)
  65   {
  66     switch(p->kind)
  67     {
  68     case PM_ASN:
  69       buffer_print(buf, "%u ", p->val);
  70       break;
  71
  72     case PM_QUESTION:
  73       buffer_puts(buf, "? ");
  74       break;
  75
  76     case PM_ASTERISK:
  77       buffer_puts(buf, "* ");
  78       break;
  79
  80     case PM_ASN_RANGE:
  81       buffer_print(buf, "%u..%u ", p->val, p->val2);
  82       break;
  83
  84     case PM_ASN_EXPR:
  85       ASSERT(0);
  86     }
  87
  88     p = p->next;
  89   }
  90
  91   buffer_puts(buf, "=]");
  92 }
  93
  94 static inline int
  95 uint_cmp(uint i1, uint i2)
  96 {
  97   return (int)(i1 > i2) - (int)(i1 < i2);
  98 }
  99
 100 static inline int
 101 u64_cmp(u64 i1, u64 i2)
 102 {
 103   return (int)(i1 > i2) - (int)(i1 < i2);
 104 }
 105
 106 static inline int
 107 lcomm_cmp(lcomm v1, lcomm v2)
 108 {
 109   if (v1.asn != v2.asn)
 110     return (v1.asn > v2.asn) ? 1 : -1;
 111   if (v1.ldp1 != v2.ldp1)
 112     return (v1.ldp1 > v2.ldp1) ? 1 : -1;
 113   if (v1.ldp2 != v2.ldp2)
 114     return (v1.ldp2 > v2.ldp2) ? 1 : -1;
 115   return 0;
 116 }
 117
 118 /**
 119  * val_compare - compare two values
 120  * @v1: first value
 121  * @v2: second value
 122  *
 123  * Compares two values and returns -1, 0, 1 on <, =, > or CMP_ERROR on
 124  * error. Tree module relies on this giving consistent results so
 125  * that it can be used for building balanced trees.
 126  */
 127 int
 128 val_compare(struct f_val v1, struct f_val v2)
 129 {
 130   int rc;
 131
 132   if (v1.type != v2.type) {
 133     if (v1.type == T_VOID)      /* Hack for else */
 134       return -1;
 135     if (v2.type == T_VOID)
 136       return 1;
 137
 138 #ifndef IPV6
 139     /* IP->Quad implicit conversion */
 140     if ((v1.type == T_QUAD) && (v2.type == T_IP))
 141       return uint_cmp(v1.val.i, ipa_to_u32(v2.val.px.ip));
 142     if ((v1.type == T_IP) && (v2.type == T_QUAD))
 143       return uint_cmp(ipa_to_u32(v1.val.px.ip), v2.val.i);
 144 #endif
 145
 146     debug( "Types do not match in val_compare\n" );
 147     return CMP_ERROR;
 148   }
 149
 150   switch (v1.type) {
 151   case T_VOID:
 152     return 0;
 153   case T_ENUM:
 154   case T_INT:
 155   case T_BOOL:
 156   case T_PAIR:
 157   case T_QUAD:
 158     return uint_cmp(v1.val.i, v2.val.i);
 159   case T_EC:
 160     return u64_cmp(v1.val.ec, v2.val.ec);
 161   case T_LC:
 162     return lcomm_cmp(v1.val.lc, v2.val.lc);
 163   case T_IP:
 164     return ipa_compare(v1.val.px.ip, v2.val.px.ip);
 165   case T_PREFIX:
 166     if (rc = ipa_compare(v1.val.px.ip, v2.val.px.ip))
 167       return rc;
 168     return uint_cmp(v1.val.px.len, v2.val.px.len);
 169   case T_STRING:
 170     return strcmp(v1.val.s, v2.val.s);
 171   default:
 172     return CMP_ERROR;
 173   }
 174 }
 175
 176 static int
 177 pm_same(struct f_path_mask *m1, struct f_path_mask *m2)
 178 {
 179   while (m1 && m2)
 180   {
 181     if (m1->kind != m2->kind)
 182       return 0;
 183
 184     if (m1->kind == PM_ASN_EXPR)
 185     {
 186       if (!i_same((struct f_inst *) m1->val, (struct f_inst *) m2->val))
 187         return 0;
 188     }
 189     else
 190     {
 191       if ((m1->val != m2->val) || (m1->val2 != m2->val2))
 192         return 0;
 193     }
 194
 195     m1 = m1->next;
 196     m2 = m2->next;
 197   }
 198
 199   return !m1 && !m2;
 200 }
 201
 202 /**
 203  * val_same - compare two values
 204  * @v1: first value
 205  * @v2: second value
 206  *
 207  * Compares two values and returns 1 if they are same and 0 if not.
 208  * Comparison of values of different types is valid and returns 0.
 209  */
 210 int
 211 val_same(struct f_val v1, struct f_val v2)
 212 {
 213   int rc;
 214
 215   rc = val_compare(v1, v2);
 216   if (rc != CMP_ERROR)
 217     return !rc;
 218
 219   if (v1.type != v2.type)
 220     return 0;
 221
 222   switch (v1.type) {
 223   case T_PATH_MASK:
 224     return pm_same(v1.val.path_mask, v2.val.path_mask);
 225   case T_PATH:
 226   case T_CLIST:
 227   case T_ECLIST:
 228   case T_LCLIST:
 229     return adata_same(v1.val.ad, v2.val.ad);
 230   case T_SET:
 231     return same_tree(v1.val.t, v2.val.t);
 232   case T_PREFIX_SET:
 233     return trie_same(v1.val.ti, v2.val.ti);
 234   default:
 235     bug("Invalid type in val_same(): %x", v1.type);
 236   }
 237 }
 238
 239 void
 240 fprefix_get_bounds(struct f_prefix *px, int *l, int *h)
 241 {
 242   *l = *h = px->len & LEN_MASK;
 243
 244   if (px->len & LEN_MINUS)
 245     *l = 0;
 246
 247   else if (px->len & LEN_PLUS)
 248     *h = MAX_PREFIX_LENGTH;
 249
 250   else if (px->len & LEN_RANGE)
 251     {
 252       *l = 0xff & (px->len >> 16);
 253       *h = 0xff & (px->len >> 8);
 254     }
 255 }
 256
 257 static int
 258 clist_set_type(struct f_tree *set, struct f_val *v)
 259 {
 260  switch (set->from.type) {
 261   case T_PAIR:
 262     v->type = T_PAIR;
 263     return 1;
 264   case T_QUAD:
 265 #ifndef IPV6
 266   case T_IP:
 267 #endif
 268     v->type = T_QUAD;
 269     return 1;
 270     break;
 271   default:
 272     v->type = T_VOID;
 273     return 0;
 274   }
 275 }
 276
 277 static inline int
 278 eclist_set_type(struct f_tree *set)
 279 { return set->from.type == T_EC; }
 280
 281 static inline int
 282 lclist_set_type(struct f_tree *set)
 283 { return set->from.type == T_LC; }
 284
 285 static int
 286 clist_match_set(struct adata *clist, struct f_tree *set)
 287 {
 288   if (!clist)
 289     return 0;
 290
 291   struct f_val v;
 292   if (!clist_set_type(set, &v))
 293     return CMP_ERROR;
 294
 295   u32 *l = (u32 *) clist->data;
 296   u32 *end = l + clist->length/4;
 297
 298   while (l < end) {
 299     v.val.i = *l++;
 300     if (find_tree(set, v))
 301       return 1;
 302   }
 303   return 0;
 304 }
 305
 306 static int
 307 eclist_match_set(struct adata *list, struct f_tree *set)
 308 {
 309   if (!list)
 310     return 0;
 311
 312   if (!eclist_set_type(set))
 313     return CMP_ERROR;
 314
 315   struct f_val v;
 316   u32 *l = int_set_get_data(list);
 317   int len = int_set_get_size(list);
 318   int i;
 319
 320   v.type = T_EC;
 321   for (i = 0; i < len; i += 2) {
 322     v.val.ec = ec_get(l, i);
 323     if (find_tree(set, v))
 324       return 1;
 325   }
 326
 327   return 0;
 328 }
 329
 330 static int
 331 lclist_match_set(struct adata *list, struct f_tree *set)
 332 {
 333   if (!list)
 334     return 0;
 335
 336   if (!lclist_set_type(set))
 337     return CMP_ERROR;
 338
 339   struct f_val v;
 340   u32 *l = int_set_get_data(list);
 341   int len = int_set_get_size(list);
 342   int i;
 343
 344   v.type = T_LC;
 345   for (i = 0; i < len; i += 3) {
 346     v.val.lc = lc_get(l, i);
 347     if (find_tree(set, v))
 348       return 1;
 349   }
 350
 351   return 0;
 352 }
 353
 354 static struct adata *
 355 clist_filter(struct linpool *pool, struct adata *list, struct f_val set, int pos)
 356 {
 357   if (!list)
 358     return NULL;
 359
 360   int tree = (set.type == T_SET);       /* 1 -> set is T_SET, 0 -> set is T_CLIST */
 361   struct f_val v;
 362   if (tree)
 363     clist_set_type(set.val.t, &v);
 364   else
 365     v.type = T_PAIR;
 366
 367   int len = int_set_get_size(list);
 368   u32 *l = int_set_get_data(list);
 369   u32 tmp[len];
 370   u32 *k = tmp;
 371   u32 *end = l + len;
 372
 373   while (l < end) {
 374     v.val.i = *l++;
 375     /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
 376     if ((tree ? !!find_tree(set.val.t, v) : int_set_contains(set.val.ad, v.val.i)) == pos)
 377       *k++ = v.val.i;
 378   }
 379
 380   uint nl = (k - tmp) * sizeof(u32);
 381   if (nl == list->length)
 382     return list;
 383
 384   struct adata *res = adata_empty(pool, nl);
 385   memcpy(res->data, tmp, nl);
 386   return res;
 387 }
 388
 389 static struct adata *
 390 eclist_filter(struct linpool *pool, struct adata *list, struct f_val set, int pos)
 391 {
 392   if (!list)
 393     return NULL;
 394
 395   int tree = (set.type == T_SET);       /* 1 -> set is T_SET, 0 -> set is T_CLIST */
 396   struct f_val v;
 397
 398   int len = int_set_get_size(list);
 399   u32 *l = int_set_get_data(list);
 400   u32 tmp[len];
 401   u32 *k = tmp;
 402   int i;
 403
 404   v.type = T_EC;
 405   for (i = 0; i < len; i += 2) {
 406     v.val.ec = ec_get(l, i);
 407     /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
 408     if ((tree ? !!find_tree(set.val.t, v) : ec_set_contains(set.val.ad, v.val.ec)) == pos) {
 409       *k++ = l[i];
 410       *k++ = l[i+1];
 411     }
 412   }
 413
 414   uint nl = (k - tmp) * sizeof(u32);
 415   if (nl == list->length)
 416     return list;
 417
 418   struct adata *res = adata_empty(pool, nl);
 419   memcpy(res->data, tmp, nl);
 420   return res;
 421 }
 422
 423 static struct adata *
 424 lclist_filter(struct linpool *pool, struct adata *list, struct f_val set, int pos)
 425 {
 426   if (!list)
 427     return NULL;
 428
 429   int tree = (set.type == T_SET);       /* 1 -> set is T_SET, 0 -> set is T_CLIST */
 430   struct f_val v;
 431
 432   int len = int_set_get_size(list);
 433   u32 *l = int_set_get_data(list);
 434   u32 tmp[len];
 435   u32 *k = tmp;
 436   int i;
 437
 438   v.type = T_LC;
 439   for (i = 0; i < len; i += 3) {
 440     v.val.lc = lc_get(l, i);
 441     /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
 442     if ((tree ? !!find_tree(set.val.t, v) : lc_set_contains(set.val.ad, v.val.lc)) == pos)
 443       k = lc_copy(k, l+i);
 444   }
 445
 446   uint nl = (k - tmp) * sizeof(u32);
 447   if (nl == list->length)
 448     return list;
 449
 450   struct adata *res = adata_empty(pool, nl);
 451   memcpy(res->data, tmp, nl);
 452   return res;
 453 }
 454
 455 /**
 456  * val_in_range - implement |~| operator
 457  * @v1: element
 458  * @v2: set
 459  *
 460  * Checks if @v1 is element (|~| operator) of @v2.
 461  */
 462 static int
 463 val_in_range(struct f_val v1, struct f_val v2)
 464 {
 465   if ((v1.type == T_PATH) && (v2.type == T_PATH_MASK))
 466     return as_path_match(v1.val.ad, v2.val.path_mask);
 467
 468   if ((v1.type == T_INT) && (v2.type == T_PATH))
 469     return as_path_contains(v2.val.ad, v1.val.i, 1);
 470
 471   if (((v1.type == T_PAIR) || (v1.type == T_QUAD)) && (v2.type == T_CLIST))
 472     return int_set_contains(v2.val.ad, v1.val.i);
 473 #ifndef IPV6
 474   /* IP->Quad implicit conversion */
 475   if ((v1.type == T_IP) && (v2.type == T_CLIST))
 476     return int_set_contains(v2.val.ad, ipa_to_u32(v1.val.px.ip));
 477 #endif
 478
 479   if ((v1.type == T_EC) && (v2.type == T_ECLIST))
 480     return ec_set_contains(v2.val.ad, v1.val.ec);
 481
 482   if ((v1.type == T_LC) && (v2.type == T_LCLIST))
 483     return lc_set_contains(v2.val.ad, v1.val.lc);
 484
 485   if ((v1.type == T_STRING) && (v2.type == T_STRING))
 486     return patmatch(v2.val.s, v1.val.s);
 487
 488   if ((v1.type == T_IP) && (v2.type == T_PREFIX))
 489     return ipa_in_net(v1.val.px.ip, v2.val.px.ip, v2.val.px.len);
 490
 491   if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX))
 492     return net_in_net(v1.val.px.ip, v1.val.px.len, v2.val.px.ip, v2.val.px.len);
 493
 494   if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX_SET))
 495     return trie_match_fprefix(v2.val.ti, &v1.val.px);
 496
 497   if (v2.type != T_SET)
 498     return CMP_ERROR;
 499
 500   /* With integrated Quad<->IP implicit conversion */
 501   if ((v1.type == v2.val.t->from.type) ||
 502       ((IP_VERSION == 4) && (v1.type == T_QUAD) && (v2.val.t->from.type == T_IP)))
 503     return !!find_tree(v2.val.t, v1);
 504
 505   if (v1.type == T_CLIST)
 506     return clist_match_set(v1.val.ad, v2.val.t);
 507
 508   if (v1.type == T_ECLIST)
 509     return eclist_match_set(v1.val.ad, v2.val.t);
 510
 511   if (v1.type == T_LCLIST)
 512     return lclist_match_set(v1.val.ad, v2.val.t);
 513
 514   if (v1.type == T_PATH)
 515     return as_path_match_set(v1.val.ad, v2.val.t);
 516
 517   return CMP_ERROR;
 518 }
 519
 520 /*
 521  * val_format - format filter value
 522  */
 523 void
 524 val_format(struct f_val v, buffer *buf)
 525 {
 526   char buf2[1024];
 527   switch (v.type)
 528   {
 529   case T_VOID:  buffer_puts(buf, "(void)"); return;
 530   case T_BOOL:  buffer_puts(buf, v.val.i ? "TRUE" : "FALSE"); return;
 531   case T_INT:   buffer_print(buf, "%u", v.val.i); return;
 532   case T_STRING: buffer_print(buf, "%s", v.val.s); return;
 533   case T_IP:    buffer_print(buf, "%I", v.val.px.ip); return;
 534   case T_PREFIX: buffer_print(buf, "%I/%d", v.val.px.ip, v.val.px.len); return;
 535   case T_PAIR:  buffer_print(buf, "(%u,%u)", v.val.i >> 16, v.val.i & 0xffff); return;
 536   case T_QUAD:  buffer_print(buf, "%R", v.val.i); return;
 537   case T_EC:    ec_format(buf2, v.val.ec); buffer_print(buf, "%s", buf2); return;
 538   case T_LC:    lc_format(buf2, v.val.lc); buffer_print(buf, "%s", buf2); return;
 539   case T_PREFIX_SET: trie_format(v.val.ti, buf); return;
 540   case T_SET:   tree_format(v.val.t, buf); return;
 541   case T_ENUM:  buffer_print(buf, "(enum %x)%u", v.type, v.val.i); return;
 542   case T_PATH:  as_path_format(v.val.ad, buf2, 1000); buffer_print(buf, "(path %s)", buf2); return;
 543   case T_CLIST: int_set_format(v.val.ad, 1, -1, buf2, 1000); buffer_print(buf, "(clist %s)", buf2); return;
 544   case T_ECLIST: ec_set_format(v.val.ad, -1, buf2, 1000); buffer_print(buf, "(eclist %s)", buf2); return;
 545   case T_LCLIST: lc_set_format(v.val.ad, -1, buf2, 1000); buffer_print(buf, "(lclist %s)", buf2); return;
 546   case T_PATH_MASK: pm_format(v.val.path_mask, buf); return;
 547   default:      buffer_print(buf, "[unknown type %x]", v.type); return;
 548   }
 549 }
 550
 551 static struct rte **f_rte;
 552 static struct rta *f_old_rta;
 553 static struct ea_list **f_tmp_attrs;
 554 static struct linpool *f_pool;
 555 static struct buffer f_buf;
 556 static int f_flags;
 557
 558 static inline void f_rte_cow(void)
 559 {
 560   *f_rte = rte_cow(*f_rte);
 561 }
 562
 563 /*
 564  * rta_cow - prepare rta for modification by filter
 565  */
 566 static void
 567 f_rta_cow(void)
 568 {
 569   if (!rta_is_cached((*f_rte)->attrs))
 570     return;
 571
 572   /* Prepare to modify rte */
 573   f_rte_cow();
 574
 575   /* Store old rta to free it later, it stores reference from rte_cow() */
 576   f_old_rta = (*f_rte)->attrs;
 577
 578   /*
 579    * Get shallow copy of rta. Fields eattrs and nexthops of rta are shared
 580    * with f_old_rta (they will be copied when the cached rta will be obtained
 581    * at the end of f_run()), also the lock of hostentry is inherited (we
 582    * suppose hostentry is not changed by filters).
 583    */
 584   (*f_rte)->attrs = rta_do_cow((*f_rte)->attrs, f_pool);
 585 }
 586
 587 static struct tbf rl_runtime_err = TBF_DEFAULT_LOG_LIMITS;
 588
 589 #define runtime(x) do { \
 590     if (!(f_flags & FF_SILENT)) \
 591       log_rl(&rl_runtime_err, L_ERR "filters, line %d: %s", what->lineno, x); \
 592     res.type = T_RETURN; \
 593     res.val.i = F_ERROR; \
 594     return res; \
 595   } while(0)
 596
 597 #define ARG(x,y) \
 598         x = interpret(what->y); \
 599         if (x.type & T_RETURN) \
 600                 return x;
 601
 602 #define ONEARG ARG(v1, a1.p)
 603 #define TWOARGS ARG(v1, a1.p) \
 604                 ARG(v2, a2.p)
 605 #define TWOARGS_C TWOARGS \
 606                   if (v1.type != v2.type) \
 607                     runtime( "Can't operate with values of incompatible types" );
 608 #define ACCESS_RTE \
 609   do { if (!f_rte) runtime("No route to access"); } while (0)
 610
 611 #define BITFIELD_MASK(what) \
 612   (1u << (what->a2.i >> 24))
 613
 614 /**
 615  * interpret
 616  * @what: filter to interpret
 617  *
 618  * Interpret given tree of filter instructions. This is core function
 619  * of filter system and does all the hard work.
 620  *
 621  * Each instruction has 4 fields: code (which is instruction code),
 622  * aux (which is extension to instruction code, typically type),
 623  * arg1 and arg2 - arguments. Depending on instruction, arguments
 624  * are either integers, or pointers to instruction trees. Common
 625  * instructions like +, that have two expressions as arguments use
 626  * TWOARGS macro to get both of them evaluated.
 627  *
 628  * &f_val structures are copied around, so there are no problems with
 629  * memory managment.
 630  */
 631 static struct f_val
 632 interpret(struct f_inst *what)
 633 {
 634   struct symbol *sym;
 635   struct f_val v1, v2, res = { .type = T_VOID }, *vp;
 636   unsigned u1, u2;
 637   int i;
 638   u32 as;
 639
 640   for ( ; what; what = what->next) {
 641   res.type = T_VOID;
 642   switch(what->fi_code) {
 643 /* Binary operators */
 644   case FI_ADD:
 645     TWOARGS_C;
 646     switch (res.type = v1.type) {
 647     case T_VOID: runtime( "Can't operate with values of type void" );
 648     case T_INT: res.val.i = v1.val.i + v2.val.i; break;
 649     default: runtime( "Usage of unknown type" );
 650     }
 651     break;
 652   case FI_SUBTRACT:
 653     TWOARGS_C;
 654     switch (res.type = v1.type) {
 655     case T_VOID: runtime( "Can't operate with values of type void" );
 656     case T_INT: res.val.i = v1.val.i - v2.val.i; break;
 657     default: runtime( "Usage of unknown type" );
 658     }
 659     break;
 660   case FI_MULTIPLY:
 661     TWOARGS_C;
 662     switch (res.type = v1.type) {
 663     case T_VOID: runtime( "Can't operate with values of type void" );
 664     case T_INT: res.val.i = v1.val.i * v2.val.i; break;
 665     default: runtime( "Usage of unknown type" );
 666     }
 667     break;
 668   case FI_DIVIDE:
 669     TWOARGS_C;
 670     switch (res.type = v1.type) {
 671     case T_VOID: runtime( "Can't operate with values of type void" );
 672     case T_INT: if (v2.val.i == 0) runtime( "Mother told me not to divide by 0" );
 673                 res.val.i = v1.val.i / v2.val.i; break;
 674     default: runtime( "Usage of unknown type" );
 675     }
 676     break;
 677
 678   case FI_AND:
 679   case FI_OR:
 680     ARG(v1, a1.p);
 681     if (v1.type != T_BOOL)
 682       runtime( "Can't do boolean operation on non-booleans" );
 683     if (v1.val.i == (what->fi_code == FI_OR)) {
 684       res.type = T_BOOL;
 685       res.val.i = v1.val.i;
 686       break;
 687     }
 688
 689     ARG(v2, a2.p);
 690     if (v2.type != T_BOOL)
 691       runtime( "Can't do boolean operation on non-booleans" );
 692     res.type = T_BOOL;
 693     res.val.i = v2.val.i;
 694     break;
 695
 696   case FI_PAIR_CONSTRUCT:
 697     TWOARGS;
 698     if ((v1.type != T_INT) || (v2.type != T_INT))
 699       runtime( "Can't operate with value of non-integer type in pair constructor" );
 700     u1 = v1.val.i;
 701     u2 = v2.val.i;
 702     if ((u1 > 0xFFFF) || (u2 > 0xFFFF))
 703       runtime( "Can't operate with value out of bounds in pair constructor" );
 704     res.val.i = (u1 << 16) | u2;
 705     res.type = T_PAIR;
 706     break;
 707
 708   case FI_EC_CONSTRUCT:
 709     {
 710       TWOARGS;
 711
 712       int check, ipv4_used;
 713       u32 key, val;
 714
 715       if (v1.type == T_INT) {
 716         ipv4_used = 0; key = v1.val.i;
 717       }
 718       else if (v1.type == T_QUAD) {
 719         ipv4_used = 1; key = v1.val.i;
 720       }
 721 #ifndef IPV6
 722       /* IP->Quad implicit conversion */
 723       else if (v1.type == T_IP) {
 724         ipv4_used = 1; key = ipa_to_u32(v1.val.px.ip);
 725       }
 726 #endif
 727       else
 728         runtime("Can't operate with key of non-integer/IPv4 type in EC constructor");
 729
 730       if (v2.type != T_INT)
 731         runtime("Can't operate with value of non-integer type in EC constructor");
 732       val = v2.val.i;
 733
 734       /* XXXX */
 735       res.type = T_EC;
 736
 737       if (what->aux == EC_GENERIC) {
 738         check = 0; res.val.ec = ec_generic(key, val);
 739       }
 740       else if (ipv4_used) {
 741         check = 1; res.val.ec = ec_ip4(what->aux, key, val);
 742       }
 743       else if (key < 0x10000) {
 744         check = 0; res.val.ec = ec_as2(what->aux, key, val);
 745       }
 746       else {
 747         check = 1; res.val.ec = ec_as4(what->aux, key, val);
 748       }
 749
 750       if (check && (val > 0xFFFF))
 751         runtime("Can't operate with value out of bounds in EC constructor");
 752
 753       break;
 754     }
 755
 756   case FI_LC_CONSTRUCT:
 757     {
 758       TWOARGS;
 759
 760       /* Third argument hack */
 761       struct f_val v3 = interpret(INST3(what).p);
 762       if (v3.type & T_RETURN)
 763         return v3;
 764
 765       if ((v1.type != T_INT) || (v2.type != T_INT) || (v3.type != T_INT))
 766         runtime( "Can't operate with value of non-integer type in LC constructor" );
 767
 768       res.type = T_LC;
 769       res.val.lc = (lcomm) { v1.val.i, v2.val.i, v3.val.i };
 770
 771       break;
 772     }
 773
 774   case FI_PATHMASK_CONSTRUCT:
 775     {
 776       struct f_path_mask *tt = what->a1.p, *vbegin, **vv = &vbegin;
 777
 778       while (tt) {
 779         *vv = lp_alloc(f_pool, sizeof(struct f_path_mask));
 780         if (tt->kind == PM_ASN_EXPR) {
 781           struct f_val res = interpret((struct f_inst *) tt->val);
 782           (*vv)->kind = PM_ASN;
 783           if (res.type != T_INT) {
 784             runtime( "Error resolving path mask template: value not an integer" );
 785             return (struct f_val) { .type = T_VOID };
 786           }
 787
 788           (*vv)->val = res.val.i;
 789         } else {
 790           **vv = *tt;
 791         }
 792         tt = tt->next;
 793         vv = &((*vv)->next);
 794       }
 795
 796       res = (struct f_val) { .type = T_PATH_MASK, .val.path_mask = vbegin };
 797       break;
 798     }
 799
 800 /* Relational operators */
 801
 802 #define COMPARE(x) \
 803     TWOARGS; \
 804     i = val_compare(v1, v2); \
 805     if (i==CMP_ERROR) \
 806       runtime( "Can't compare values of incompatible types" ); \
 807     res.type = T_BOOL; \
 808     res.val.i = (x); \
 809     break;
 810
 811 #define SAME(x) \
 812     TWOARGS; \
 813     i = val_same(v1, v2); \
 814     res.type = T_BOOL; \
 815     res.val.i = (x); \
 816     break;
 817
 818   case FI_NEQ: SAME(!i);
 819   case FI_EQ: SAME(i);
 820   case FI_LT: COMPARE(i==-1);
 821   case FI_LTE: COMPARE(i!=1);
 822
 823   case FI_NOT:
 824     ONEARG;
 825     if (v1.type != T_BOOL)
 826       runtime( "Not applied to non-boolean" );
 827     res = v1;
 828     res.val.i = !res.val.i;
 829     break;
 830
 831   case FI_MATCH:
 832     TWOARGS;
 833     res.type = T_BOOL;
 834     res.val.i = val_in_range(v1, v2);
 835     if (res.val.i == CMP_ERROR)
 836       runtime( "~ applied on unknown type pair" );
 837     res.val.i = !!res.val.i;
 838     break;
 839
 840   case FI_NOT_MATCH:
 841     TWOARGS;
 842     res.type = T_BOOL;
 843     res.val.i = val_in_range(v1, v2);
 844     if (res.val.i == CMP_ERROR)
 845       runtime( "!~ applied on unknown type pair" );
 846     res.val.i = !res.val.i;
 847     break;
 848
 849   case FI_DEFINED:
 850     ONEARG;
 851     res.type = T_BOOL;
 852     res.val.i = (v1.type != T_VOID);
 853     break;
 854
 855   /* Set to indirect value, a1 = variable, a2 = value */
 856   case FI_SET:
 857     ARG(v2, a2.p);
 858     sym = what->a1.p;
 859     vp = sym->def;
 860     if ((sym->class != (SYM_VARIABLE | v2.type)) && (v2.type != T_VOID)) {
 861 #ifndef IPV6
 862       /* IP->Quad implicit conversion */
 863       if ((sym->class == (SYM_VARIABLE | T_QUAD)) && (v2.type == T_IP)) {
 864         vp->type = T_QUAD;
 865         vp->val.i = ipa_to_u32(v2.val.px.ip);
 866         break;
 867       }
 868 #endif
 869       runtime( "Assigning to variable of incompatible type" );
 870     }
 871     *vp = v2;
 872     break;
 873
 874     /* some constants have value in a2, some in *a1.p, strange. */
 875   case FI_CONSTANT:     /* integer (or simple type) constant, string, set, or prefix_set */
 876     res.type = what->aux;
 877
 878     if (res.type == T_PREFIX_SET)
 879       res.val.ti = what->a2.p;
 880     else if (res.type == T_SET)
 881       res.val.t = what->a2.p;
 882     else if (res.type == T_STRING)
 883       res.val.s = what->a2.p;
 884     else
 885       res.val.i = what->a2.i;
 886     break;
 887   case FI_VARIABLE:
 888   case FI_CONSTANT_INDIRECT:
 889     res = * ((struct f_val *) what->a1.p);
 890     break;
 891   case FI_PRINT:
 892     ONEARG;
 893     val_format(v1, &f_buf);
 894     break;
 895   case FI_CONDITION:    /* ? has really strange error value, so we can implement if ... else nicely :-) */
 896     ONEARG;
 897     if (v1.type != T_BOOL)
 898       runtime( "If requires boolean expression" );
 899     if (v1.val.i) {
 900       ARG(res,a2.p);
 901       res.val.i = 0;
 902     } else res.val.i = 1;
 903     res.type = T_BOOL;
 904     break;
 905   case FI_NOP:
 906     debug( "No operation\n" );
 907     break;
 908   case FI_PRINT_AND_DIE:
 909     ONEARG;
 910     if ((what->a2.i == F_NOP || (what->a2.i != F_NONL && what->a1.p)) &&
 911         !(f_flags & FF_SILENT))
 912       log_commit(*L_INFO, &f_buf);
 913
 914     switch (what->a2.i) {
 915     case F_QUITBIRD:
 916       die( "Filter asked me to die" );
 917     case F_ACCEPT:
 918       /* Should take care about turning ACCEPT into MODIFY */
 919     case F_ERROR:
 920     case F_REJECT:      /* FIXME (noncritical) Should print complete route along with reason to reject route */
 921       res.type = T_RETURN;
 922       res.val.i = what->a2.i;
 923       return res;       /* We have to return now, no more processing. */
 924     case F_NONL:
 925     case F_NOP:
 926       break;
 927     default:
 928       bug( "unknown return type: Can't happen");
 929     }
 930     break;
 931   case FI_RTA_GET:      /* rta access */
 932     {
 933       ACCESS_RTE;
 934       struct rta *rta = (*f_rte)->attrs;
 935       res.type = what->aux;
 936
 937       switch (what->a2.i)
 938       {
 939       case SA_FROM:     res.val.px.ip = rta->from; break;
 940       case SA_GW:       res.val.px.ip = rta->gw; break;
 941       case SA_NET:      res.val.px.ip = (*f_rte)->net->n.prefix;
 942                         res.val.px.len = (*f_rte)->net->n.pxlen; break;
 943       case SA_PROTO:    res.val.s = rta->src->proto->name; break;
 944       case SA_SOURCE:   res.val.i = rta->source; break;
 945       case SA_SCOPE:    res.val.i = rta->scope; break;
 946       case SA_CAST:     res.val.i = rta->cast; break;
 947       case SA_DEST:     res.val.i = rta->dest; break;
 948       case SA_IFNAME:   res.val.s = rta->iface ? rta->iface->name : ""; break;
 949       case SA_IFINDEX:  res.val.i = rta->iface ? rta->iface->index : 0; break;
 950
 951       default:
 952         bug("Invalid static attribute access (%x)", res.type);
 953       }
 954     }
 955     break;
 956   case FI_RTA_SET:
 957     ACCESS_RTE;
 958     ONEARG;
 959     if (what->aux != v1.type)
 960       runtime( "Attempt to set static attribute to incompatible type" );
 961
 962     f_rta_cow();
 963     {
 964       struct rta *rta = (*f_rte)->attrs;
 965
 966       switch (what->a2.i)
 967       {
 968       case SA_FROM:
 969         rta->from = v1.val.px.ip;
 970         break;
 971
 972       case SA_GW:
 973         {
 974           ip_addr ip = v1.val.px.ip;
 975           neighbor *n = neigh_find(rta->src->proto, &ip, 0);
 976           if (!n || (n->scope == SCOPE_HOST))
 977             runtime( "Invalid gw address" );
 978
 979           rta->dest = RTD_ROUTER;
 980           rta->gw = ip;
 981           rta->iface = n->iface;
 982           rta->nexthops = NULL;
 983           rta->hostentry = NULL;
 984         }
 985         break;
 986
 987       case SA_SCOPE:
 988         rta->scope = v1.val.i;
 989         break;
 990
 991       case SA_DEST:
 992         i = v1.val.i;
 993         if ((i != RTD_BLACKHOLE) && (i != RTD_UNREACHABLE) && (i != RTD_PROHIBIT))
 994           runtime( "Destination can be changed only to blackhole, unreachable or prohibit" );
 995
 996         rta->dest = i;
 997         rta->gw = IPA_NONE;
 998         rta->iface = NULL;
 999         rta->nexthops = NULL;
1000         rta->hostentry = NULL;
1001         break;
1002
1003       case SA_IFNAME:
1004         {
1005           struct iface *ifa = if_find_by_name(v1.val.s);
1006           if (!ifa)
1007             runtime( "Invalid iface name" );
1008
1009           rta->dest = RTD_DEVICE;
1010           rta->gw = IPA_NONE;
1011           rta->iface = ifa;
1012           rta->nexthops = NULL;
1013           rta->hostentry = NULL;
1014         }
1015         break;
1016
1017       default:
1018         bug("Invalid static attribute access (%x)", res.type);
1019       }
1020     }
1021     break;
1022   case FI_EA_GET:       /* Access to extended attributes */
1023     ACCESS_RTE;
1024     {
1025       eattr *e = NULL;
1026       u16 code = what->a2.i;
1027
1028       if (!(f_flags & FF_FORCE_TMPATTR))
1029         e = ea_find((*f_rte)->attrs->eattrs, code);
1030       if (!e)
1031         e = ea_find((*f_tmp_attrs), code);
1032       if ((!e) && (f_flags & FF_FORCE_TMPATTR))
1033         e = ea_find((*f_rte)->attrs->eattrs, code);
1034
1035       if (!e) {
1036         /* A special case: undefined int_set looks like empty int_set */
1037         if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_INT_SET) {
1038           res.type = T_CLIST;
1039           res.val.ad = adata_empty(f_pool, 0);
1040           break;
1041         }
1042
1043         /* The same special case for ec_set */
1044         if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_EC_SET) {
1045           res.type = T_ECLIST;
1046           res.val.ad = adata_empty(f_pool, 0);
1047           break;
1048         }
1049
1050         /* The same special case for lc_set */
1051         if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_LC_SET) {
1052           res.type = T_LCLIST;
1053           res.val.ad = adata_empty(f_pool, 0);
1054           break;
1055         }
1056
1057         /* Undefined value */
1058         res.type = T_VOID;
1059         break;
1060       }
1061
1062       switch (what->aux & EAF_TYPE_MASK) {
1063       case EAF_TYPE_INT:
1064         res.type = T_INT;
1065         res.val.i = e->u.data;
1066         break;
1067       case EAF_TYPE_ROUTER_ID:
1068         res.type = T_QUAD;
1069         res.val.i = e->u.data;
1070         break;
1071       case EAF_TYPE_OPAQUE:
1072         res.type = T_ENUM_EMPTY;
1073         res.val.i = 0;
1074         break;
1075       case EAF_TYPE_IP_ADDRESS:
1076         res.type = T_IP;
1077         struct adata * ad = e->u.ptr;
1078         res.val.px.ip = * (ip_addr *) ad->data;
1079         break;
1080       case EAF_TYPE_AS_PATH:
1081         res.type = T_PATH;
1082         res.val.ad = e->u.ptr;
1083         break;
1084       case EAF_TYPE_BITFIELD:
1085         res.type = T_BOOL;
1086         res.val.i = !!(e->u.data & BITFIELD_MASK(what));
1087         break;
1088       case EAF_TYPE_INT_SET:
1089         res.type = T_CLIST;
1090         res.val.ad = e->u.ptr;
1091         break;
1092       case EAF_TYPE_EC_SET:
1093         res.type = T_ECLIST;
1094         res.val.ad = e->u.ptr;
1095         break;
1096       case EAF_TYPE_LC_SET:
1097         res.type = T_LCLIST;
1098         res.val.ad = e->u.ptr;
1099         break;
1100       case EAF_TYPE_UNDEF:
1101         res.type = T_VOID;
1102         break;
1103       default:
1104         bug("Unknown type in e,a");
1105       }
1106     }
1107     break;
1108   case FI_EA_SET:
1109     ACCESS_RTE;
1110     ONEARG;
1111     {
1112       struct ea_list *l = lp_alloc(f_pool, sizeof(struct ea_list) + sizeof(eattr));
1113       u16 code = what->a2.i;
1114
1115       l->next = NULL;
1116       l->flags = EALF_SORTED;
1117       l->count = 1;
1118       l->attrs[0].id = code;
1119       l->attrs[0].flags = 0;
1120       l->attrs[0].type = what->aux | EAF_ORIGINATED;
1121
1122       switch (what->aux & EAF_TYPE_MASK) {
1123       case EAF_TYPE_INT:
1124         // Enums are also ints, so allow them in.
1125         if (v1.type != T_INT && (v1.type < T_ENUM_LO || v1.type > T_ENUM_HI))
1126           runtime( "Setting int attribute to non-int value" );
1127         l->attrs[0].u.data = v1.val.i;
1128         break;
1129
1130       case EAF_TYPE_ROUTER_ID:
1131 #ifndef IPV6
1132         /* IP->Quad implicit conversion */
1133         if (v1.type == T_IP) {
1134           l->attrs[0].u.data = ipa_to_u32(v1.val.px.ip);
1135           break;
1136         }
1137 #endif
1138         /* T_INT for backward compatibility */
1139         if ((v1.type != T_QUAD) && (v1.type != T_INT))
1140           runtime( "Setting quad attribute to non-quad value" );
1141         l->attrs[0].u.data = v1.val.i;
1142         break;
1143
1144       case EAF_TYPE_OPAQUE:
1145         runtime( "Setting opaque attribute is not allowed" );
1146         break;
1147       case EAF_TYPE_IP_ADDRESS:
1148         if (v1.type != T_IP)
1149           runtime( "Setting ip attribute to non-ip value" );
1150         int len = sizeof(ip_addr);
1151         struct adata *ad = lp_alloc(f_pool, sizeof(struct adata) + len);
1152         ad->length = len;
1153         (* (ip_addr *) ad->data) = v1.val.px.ip;
1154         l->attrs[0].u.ptr = ad;
1155         break;
1156       case EAF_TYPE_AS_PATH:
1157         if (v1.type != T_PATH)
1158           runtime( "Setting path attribute to non-path value" );
1159         l->attrs[0].u.ptr = v1.val.ad;
1160         break;
1161       case EAF_TYPE_BITFIELD:
1162         if (v1.type != T_BOOL)
1163           runtime( "Setting bit in bitfield attribute to non-bool value" );
1164         {
1165           /* First, we have to find the old value */
1166           eattr *e = NULL;
1167           if (!(f_flags & FF_FORCE_TMPATTR))
1168             e = ea_find((*f_rte)->attrs->eattrs, code);
1169           if (!e)
1170             e = ea_find((*f_tmp_attrs), code);
1171           if ((!e) && (f_flags & FF_FORCE_TMPATTR))
1172             e = ea_find((*f_rte)->attrs->eattrs, code);
1173           u32 data = e ? e->u.data : 0;
1174
1175           if (v1.val.i)
1176             l->attrs[0].u.data = data | BITFIELD_MASK(what);
1177           else
1178             l->attrs[0].u.data = data & ~BITFIELD_MASK(what);;
1179         }
1180         break;
1181       case EAF_TYPE_INT_SET:
1182         if (v1.type != T_CLIST)
1183           runtime( "Setting clist attribute to non-clist value" );
1184         l->attrs[0].u.ptr = v1.val.ad;
1185         break;
1186       case EAF_TYPE_EC_SET:
1187         if (v1.type != T_ECLIST)
1188           runtime( "Setting eclist attribute to non-eclist value" );
1189         l->attrs[0].u.ptr = v1.val.ad;
1190         break;
1191       case EAF_TYPE_LC_SET:
1192         if (v1.type != T_LCLIST)
1193           runtime( "Setting lclist attribute to non-lclist value" );
1194         l->attrs[0].u.ptr = v1.val.ad;
1195         break;
1196       case EAF_TYPE_UNDEF:
1197         if (v1.type != T_VOID)
1198           runtime( "Setting void attribute to non-void value" );
1199         l->attrs[0].u.data = 0;
1200         break;
1201       default: bug("Unknown type in e,S");
1202       }
1203
1204       if (!(what->aux & EAF_TEMP) && (!(f_flags & FF_FORCE_TMPATTR))) {
1205         f_rta_cow();
1206         l->next = (*f_rte)->attrs->eattrs;
1207         (*f_rte)->attrs->eattrs = l;
1208       } else {
1209         l->next = (*f_tmp_attrs);
1210         (*f_tmp_attrs) = l;
1211       }
1212     }
1213     break;
1214   case FI_PREF_GET:
1215     ACCESS_RTE;
1216     res.type = T_INT;
1217     res.val.i = (*f_rte)->pref;
1218     break;
1219   case FI_PREF_SET:
1220     ACCESS_RTE;
1221     ONEARG;
1222     if (v1.type != T_INT)
1223       runtime( "Can't set preference to non-integer" );
1224     if (v1.val.i > 0xFFFF)
1225       runtime( "Setting preference value out of bounds" );
1226     f_rte_cow();
1227     (*f_rte)->pref = v1.val.i;
1228     break;
1229   case FI_LENGTH:       /* Get length of */
1230     ONEARG;
1231     res.type = T_INT;
1232     switch(v1.type) {
1233     case T_PREFIX: res.val.i = v1.val.px.len; break;
1234     case T_PATH:   res.val.i = as_path_getlen(v1.val.ad); break;
1235     case T_CLIST:  res.val.i = int_set_get_size(v1.val.ad); break;
1236     case T_ECLIST: res.val.i = ec_set_get_size(v1.val.ad); break;
1237     case T_LCLIST: res.val.i = lc_set_get_size(v1.val.ad); break;
1238     default: runtime( "Prefix, path, clist or eclist expected" );
1239     }
1240     break;
1241   case FI_IP:   /* Convert prefix to ... */
1242     ONEARG;
1243     if (v1.type != T_PREFIX)
1244       runtime( "Prefix expected" );
1245     res.type = what->aux;
1246     switch(res.type) {
1247       /*    case T_INT: res.val.i = v1.val.px.len; break; Not needed any more */
1248     case T_IP: res.val.px.ip = v1.val.px.ip; break;
1249     default: bug( "Unknown prefix to conversion" );
1250     }
1251     break;
1252   case FI_AS_PATH_FIRST:        /* Get first ASN from AS PATH */
1253     ONEARG;
1254     if (v1.type != T_PATH)
1255       runtime( "AS path expected" );
1256
1257     as = 0;
1258     as_path_get_first(v1.val.ad, &as);
1259     res.type = T_INT;
1260     res.val.i = as;
1261     break;
1262   case FI_AS_PATH_LAST: /* Get last ASN from AS PATH */
1263     ONEARG;
1264     if (v1.type != T_PATH)
1265       runtime( "AS path expected" );
1266
1267     as = 0;
1268     as_path_get_last(v1.val.ad, &as);
1269     res.type = T_INT;
1270     res.val.i = as;
1271     break;
1272   case FI_AS_PATH_LAST_NAG:     /* Get last ASN from non-aggregated part of AS PATH */
1273     ONEARG;
1274     if (v1.type != T_PATH)
1275       runtime( "AS path expected" );
1276
1277     res.type = T_INT;
1278     res.val.i = as_path_get_last_nonaggregated(v1.val.ad);
1279     break;
1280   case FI_RETURN:
1281     ONEARG;
1282     res = v1;
1283     res.type |= T_RETURN;
1284     return res;
1285   case FI_CALL: /* CALL: this is special: if T_RETURN and returning some value, mask it out  */
1286     ONEARG;
1287     res = interpret(what->a2.p);
1288     if (res.type == T_RETURN)
1289       return res;
1290     res.type &= ~T_RETURN;
1291     break;
1292   case FI_CLEAR_LOCAL_VARS:     /* Clear local variables */
1293     for (sym = what->a1.p; sym != NULL; sym = sym->aux2)
1294       ((struct f_val *) sym->def)->type = T_VOID;
1295     break;
1296   case FI_SWITCH:
1297     ONEARG;
1298     {
1299       struct f_tree *t = find_tree(what->a2.p, v1);
1300       if (!t) {
1301         v1.type = T_VOID;
1302         t = find_tree(what->a2.p, v1);
1303         if (!t) {
1304           debug( "No else statement?\n");
1305           break;
1306         }
1307       }
1308       /* It is actually possible to have t->data NULL */
1309
1310       res = interpret(t->data);
1311       if (res.type & T_RETURN)
1312         return res;
1313     }
1314     break;
1315   case FI_IP_MASK: /* IP.MASK(val) */
1316     TWOARGS;
1317     if (v2.type != T_INT)
1318       runtime( "Integer expected");
1319     if (v1.type != T_IP)
1320       runtime( "You can mask only IP addresses" );
1321     {
1322       ip_addr mask = ipa_mkmask(v2.val.i);
1323       res.type = T_IP;
1324       res.val.px.ip = ipa_and(mask, v1.val.px.ip);
1325     }
1326     break;
1327
1328   case FI_EMPTY:        /* Create empty attribute */
1329     res.type = what->aux;
1330     res.val.ad = adata_empty(f_pool, 0);
1331     break;
1332   case FI_PATH_PREPEND: /* Path prepend */
1333     TWOARGS;
1334     if (v1.type != T_PATH)
1335       runtime("Can't prepend to non-path");
1336     if (v2.type != T_INT)
1337       runtime("Can't prepend non-integer");
1338
1339     res.type = T_PATH;
1340     res.val.ad = as_path_prepend(f_pool, v1.val.ad, v2.val.i);
1341     break;
1342
1343   case FI_CLIST_ADD_DEL:        /* (Extended) Community list add or delete */
1344     TWOARGS;
1345     if (v1.type == T_PATH)
1346     {
1347       struct f_tree *set = NULL;
1348       u32 key = 0;
1349       int pos;
1350
1351       if (v2.type == T_INT)
1352         key = v2.val.i;
1353       else if ((v2.type == T_SET) && (v2.val.t->from.type == T_INT))
1354         set = v2.val.t;
1355       else
1356         runtime("Can't delete non-integer (set)");
1357
1358       switch (what->aux)
1359       {
1360       case 'a': runtime("Can't add to path");
1361       case 'd': pos = 0; break;
1362       case 'f': pos = 1; break;
1363       default:  bug("unknown Ca operation");
1364       }
1365
1366       if (pos && !set)
1367         runtime("Can't filter integer");
1368
1369       res.type = T_PATH;
1370       res.val.ad = as_path_filter(f_pool, v1.val.ad, set, key, pos);
1371     }
1372     else if (v1.type == T_CLIST)
1373     {
1374       /* Community (or cluster) list */
1375       struct f_val dummy;
1376       int arg_set = 0;
1377       uint n = 0;
1378
1379       if ((v2.type == T_PAIR) || (v2.type == T_QUAD))
1380         n = v2.val.i;
1381 #ifndef IPV6
1382       /* IP->Quad implicit conversion */
1383       else if (v2.type == T_IP)
1384         n = ipa_to_u32(v2.val.px.ip);
1385 #endif
1386       else if ((v2.type == T_SET) && clist_set_type(v2.val.t, &dummy))
1387         arg_set = 1;
1388       else if (v2.type == T_CLIST)
1389         arg_set = 2;
1390       else
1391         runtime("Can't add/delete non-pair");
1392
1393       res.type = T_CLIST;
1394       switch (what->aux)
1395       {
1396       case 'a':
1397         if (arg_set == 1)
1398           runtime("Can't add set");
1399         else if (!arg_set)
1400           res.val.ad = int_set_add(f_pool, v1.val.ad, n);
1401         else
1402           res.val.ad = int_set_union(f_pool, v1.val.ad, v2.val.ad);
1403         break;
1404
1405       case 'd':
1406         if (!arg_set)
1407           res.val.ad = int_set_del(f_pool, v1.val.ad, n);
1408         else
1409           res.val.ad = clist_filter(f_pool, v1.val.ad, v2, 0);
1410         break;
1411
1412       case 'f':
1413         if (!arg_set)
1414           runtime("Can't filter pair");
1415         res.val.ad = clist_filter(f_pool, v1.val.ad, v2, 1);
1416         break;
1417
1418       default:
1419         bug("unknown Ca operation");
1420       }
1421     }
1422     else if (v1.type == T_ECLIST)
1423     {
1424       /* Extended community list */
1425       int arg_set = 0;
1426
1427       /* v2.val is either EC or EC-set */
1428       if ((v2.type == T_SET) && eclist_set_type(v2.val.t))
1429         arg_set = 1;
1430       else if (v2.type == T_ECLIST)
1431         arg_set = 2;
1432       else if (v2.type != T_EC)
1433         runtime("Can't add/delete non-ec");
1434
1435       res.type = T_ECLIST;
1436       switch (what->aux)
1437       {
1438       case 'a':
1439         if (arg_set == 1)
1440           runtime("Can't add set");
1441         else if (!arg_set)
1442           res.val.ad = ec_set_add(f_pool, v1.val.ad, v2.val.ec);
1443         else
1444           res.val.ad = ec_set_union(f_pool, v1.val.ad, v2.val.ad);
1445         break;
1446
1447       case 'd':
1448         if (!arg_set)
1449           res.val.ad = ec_set_del(f_pool, v1.val.ad, v2.val.ec);
1450         else
1451           res.val.ad = eclist_filter(f_pool, v1.val.ad, v2, 0);
1452         break;
1453
1454       case 'f':
1455         if (!arg_set)
1456           runtime("Can't filter ec");
1457         res.val.ad = eclist_filter(f_pool, v1.val.ad, v2, 1);
1458         break;
1459
1460       default:
1461         bug("unknown Ca operation");
1462       }
1463     }
1464     else if (v1.type == T_LCLIST)
1465     {
1466       /* Large community list */
1467       int arg_set = 0;
1468
1469       /* v2.val is either LC or LC-set */
1470       if ((v2.type == T_SET) && lclist_set_type(v2.val.t))
1471         arg_set = 1;
1472       else if (v2.type == T_LCLIST)
1473         arg_set = 2;
1474       else if (v2.type != T_LC)
1475         runtime("Can't add/delete non-lc");
1476
1477       res.type = T_LCLIST;
1478       switch (what->aux)
1479       {
1480       case 'a':
1481         if (arg_set == 1)
1482           runtime("Can't add set");
1483         else if (!arg_set)
1484           res.val.ad = lc_set_add(f_pool, v1.val.ad, v2.val.lc);
1485         else
1486           res.val.ad = lc_set_union(f_pool, v1.val.ad, v2.val.ad);
1487         break;
1488
1489       case 'd':
1490         if (!arg_set)
1491           res.val.ad = lc_set_del(f_pool, v1.val.ad, v2.val.lc);
1492         else
1493           res.val.ad = lclist_filter(f_pool, v1.val.ad, v2, 0);
1494         break;
1495
1496       case 'f':
1497         if (!arg_set)
1498           runtime("Can't filter lc");
1499         res.val.ad = lclist_filter(f_pool, v1.val.ad, v2, 1);
1500         break;
1501
1502       default:
1503         bug("unknown Ca operation");
1504       }
1505     }
1506     else
1507       runtime("Can't add/delete to non-[e|l]clist");
1508
1509     break;
1510
1511   case FI_ROA_CHECK:    /* ROA Check */
1512     if (what->arg1)
1513     {
1514       TWOARGS;
1515       if ((v1.type != T_PREFIX) || (v2.type != T_INT))
1516         runtime("Invalid argument to roa_check()");
1517
1518       as = v2.val.i;
1519     }
1520     else
1521     {
1522       ACCESS_RTE;
1523       v1.val.px.ip = (*f_rte)->net->n.prefix;
1524       v1.val.px.len = (*f_rte)->net->n.pxlen;
1525
1526       /* We ignore temporary attributes, probably not a problem here */
1527       /* 0x02 is a value of BA_AS_PATH, we don't want to include BGP headers */
1528       eattr *e = ea_find((*f_rte)->attrs->eattrs, EA_CODE(EAP_BGP, 0x02));
1529
1530       if (!e || e->type != EAF_TYPE_AS_PATH)
1531         runtime("Missing AS_PATH attribute");
1532
1533       as_path_get_last(e->u.ptr, &as);
1534     }
1535
1536     struct roa_table_config *rtc = ((struct f_inst_roa_check *) what)->rtc;
1537     if (!rtc->table)
1538       runtime("Missing ROA table");
1539
1540     res.type = T_ENUM_ROA;
1541     res.val.i = roa_check(rtc->table, v1.val.px.ip, v1.val.px.len, as);
1542     break;
1543
1544   default:
1545     bug( "Unknown instruction %d (%c)", what->fi_code, what->fi_code & 0xff);
1546   }}
1547   return res;
1548 }
1549
1550 #undef ARG
1551 #define ARG(x,y) \
1552         if (!i_same(f1->y, f2->y)) \
1553                 return 0;
1554
1555 #define ONEARG ARG(v1, a1.p)
1556 #define TWOARGS ARG(v1, a1.p) \
1557                 ARG(v2, a2.p)
1558
1559 #define A2_SAME if (f1->a2.i != f2->a2.i) return 0;
1560
1561 /*
1562  * i_same - function that does real comparing of instruction trees, you should call filter_same from outside
1563  */
1564 int
1565 i_same(struct f_inst *f1, struct f_inst *f2)
1566 {
1567   if ((!!f1) != (!!f2))
1568     return 0;
1569   if (!f1)
1570     return 1;
1571   if (f1->aux != f2->aux)
1572     return 0;
1573   if (f1->fi_code != f2->fi_code)
1574     return 0;
1575   if (f1 == f2)         /* It looks strange, but it is possible with call rewriting trickery */
1576     return 1;
1577
1578   switch(f1->fi_code) {
1579   case FI_ADD: /* fall through */
1580   case FI_SUBTRACT:
1581   case FI_MULTIPLY:
1582   case FI_DIVIDE:
1583   case FI_OR:
1584   case FI_AND:
1585   case FI_PAIR_CONSTRUCT:
1586   case FI_EC_CONSTRUCT:
1587   case FI_NEQ:
1588   case FI_EQ:
1589   case FI_LT:
1590   case FI_LTE: TWOARGS; break;
1591
1592   case FI_PATHMASK_CONSTRUCT: if (!pm_same(f1->a1.p, f2->a1.p)) return 0; break;
1593
1594   case FI_NOT: ONEARG; break;
1595   case FI_NOT_MATCH:
1596   case FI_MATCH: TWOARGS; break;
1597   case FI_DEFINED: ONEARG; break;
1598
1599   case FI_LC_CONSTRUCT:
1600     TWOARGS;
1601     if (!i_same(INST3(f1).p, INST3(f2).p))
1602       return 0;
1603     break;
1604
1605   case FI_SET:
1606     ARG(v2, a2.p);
1607     {
1608       struct symbol *s1, *s2;
1609       s1 = f1->a1.p;
1610       s2 = f2->a1.p;
1611       if (strcmp(s1->name, s2->name))
1612         return 0;
1613       if (s1->class != s2->class)
1614         return 0;
1615     }
1616     break;
1617
1618   case FI_CONSTANT:
1619     switch (f1->aux) {
1620
1621     case T_PREFIX_SET:
1622       if (!trie_same(f1->a2.p, f2->a2.p))
1623         return 0;
1624       break;
1625
1626     case T_SET:
1627       if (!same_tree(f1->a2.p, f2->a2.p))
1628         return 0;
1629       break;
1630
1631     case T_STRING:
1632       if (strcmp(f1->a2.p, f2->a2.p))
1633         return 0;
1634       break;
1635
1636     default:
1637       A2_SAME;
1638     }
1639     break;
1640
1641   case FI_CONSTANT_INDIRECT:
1642     if (!val_same(* (struct f_val *) f1->a1.p, * (struct f_val *) f2->a1.p))
1643       return 0;
1644     break;
1645
1646   case FI_VARIABLE:
1647     if (strcmp((char *) f1->a2.p, (char *) f2->a2.p))
1648       return 0;
1649     break;
1650   case FI_PRINT: case FI_LENGTH: ONEARG; break;
1651   case FI_CONDITION: TWOARGS; break;
1652   case FI_NOP: case FI_EMPTY: break;
1653   case FI_PRINT_AND_DIE: ONEARG; A2_SAME; break;
1654   case FI_PREF_GET:
1655   case FI_RTA_GET: A2_SAME; break;
1656   case FI_EA_GET: A2_SAME; break;
1657   case FI_PREF_SET:
1658   case FI_RTA_SET:
1659   case FI_EA_SET: ONEARG; A2_SAME; break;
1660
1661   case FI_RETURN: ONEARG; break;
1662   case FI_IP: ONEARG; break;
1663   case FI_CALL: /* Call rewriting trickery to avoid exponential behaviour */
1664              ONEARG;
1665              if (!i_same(f1->a2.p, f2->a2.p))
1666                return 0;
1667              f2->a2.p = f1->a2.p;
1668              break;
1669   case FI_CLEAR_LOCAL_VARS: break; /* internal instruction */
1670   case FI_SWITCH: ONEARG; if (!same_tree(f1->a2.p, f2->a2.p)) return 0; break;
1671   case FI_IP_MASK: TWOARGS; break;
1672   case FI_PATH_PREPEND: TWOARGS; break;
1673   case FI_CLIST_ADD_DEL: TWOARGS; break;
1674   case FI_AS_PATH_FIRST:
1675   case FI_AS_PATH_LAST:
1676   case FI_AS_PATH_LAST_NAG: ONEARG; break;
1677   case FI_ROA_CHECK:
1678     TWOARGS;
1679     /* Does not really make sense - ROA check resuls may change anyway */
1680     if (strcmp(((struct f_inst_roa_check *) f1)->rtc->name,
1681                ((struct f_inst_roa_check *) f2)->rtc->name))
1682       return 0;
1683     break;
1684   default:
1685     bug( "Unknown instruction %d in same (%c)", f1->fi_code, f1->fi_code & 0xff);
1686   }
1687   return i_same(f1->next, f2->next);
1688 }
1689
1690 /**
1691  * f_run - run a filter for a route
1692  * @filter: filter to run
1693  * @rte: route being filtered, may be modified
1694  * @tmp_attrs: temporary attributes, prepared by caller or generated by f_run()
1695  * @tmp_pool: all filter allocations go from this pool
1696  * @flags: flags
1697  *
1698  * If filter needs to modify the route, there are several
1699  * posibilities. @rte might be read-only (with REF_COW flag), in that
1700  * case rw copy is obtained by rte_cow() and @rte is replaced. If
1701  * @rte is originally rw, it may be directly modified (and it is never
1702  * copied).
1703  *
1704  * The returned rte may reuse the (possibly cached, cloned) rta, or
1705  * (if rta was modificied) contains a modified uncached rta, which
1706  * uses parts allocated from @tmp_pool and parts shared from original
1707  * rta. There is one exception - if @rte is rw but contains a cached
1708  * rta and that is modified, rta in returned rte is also cached.
1709  *
1710  * Ownership of cached rtas is consistent with rte, i.e.
1711  * if a new rte is returned, it has its own clone of cached rta
1712  * (and cached rta of read-only source rte is intact), if rte is
1713  * modified in place, old cached rta is possibly freed.
1714  */
1715 int
1716 f_run(struct filter *filter, struct rte **rte, struct ea_list **tmp_attrs, struct linpool *tmp_pool, int flags)
1717 {
1718   if (filter == FILTER_ACCEPT)
1719     return F_ACCEPT;
1720
1721   if (filter == FILTER_REJECT)
1722     return F_REJECT;
1723
1724   int rte_cow = ((*rte)->flags & REF_COW);
1725   DBG( "Running filter `%s'...", filter->name );
1726
1727   f_rte = rte;
1728   f_old_rta = NULL;
1729   f_tmp_attrs = tmp_attrs;
1730   f_pool = tmp_pool;
1731   f_flags = flags;
1732
1733   LOG_BUFFER_INIT(f_buf);
1734
1735   struct f_val res = interpret(filter->root);
1736
1737   if (f_old_rta) {
1738     /*
1739      * Cached rta was modified and f_rte contains now an uncached one,
1740      * sharing some part with the cached one. The cached rta should
1741      * be freed (if rte was originally COW, f_old_rta is a clone
1742      * obtained during rte_cow()).
1743      *
1744      * This also implements the exception mentioned in f_run()
1745      * description. The reason for this is that rta reuses parts of
1746      * f_old_rta, and these may be freed during rta_free(f_old_rta).
1747      * This is not the problem if rte was COW, because original rte
1748      * also holds the same rta.
1749      */
1750     if (!rte_cow)
1751       (*f_rte)->attrs = rta_lookup((*f_rte)->attrs);
1752
1753     rta_free(f_old_rta);
1754   }
1755
1756
1757   if (res.type != T_RETURN) {
1758     if (!(f_flags & FF_SILENT))
1759       log_rl(&rl_runtime_err, L_ERR "Filter %s did not return accept nor reject. Make up your mind", filter->name);
1760     return F_ERROR;
1761   }
1762   DBG( "done (%u)\n", res.val.i );
1763   return res.val.i;
1764 }
1765
1766 /* TODO: perhaps we could integrate f_eval(), f_eval_rte() and f_run() */
1767
1768 struct f_val
1769 f_eval_rte(struct f_inst *expr, struct rte **rte, struct linpool *tmp_pool)
1770 {
1771   struct ea_list *tmp_attrs = NULL;
1772
1773   f_rte = rte;
1774   f_old_rta = NULL;
1775   f_tmp_attrs = &tmp_attrs;
1776   f_pool = tmp_pool;
1777   f_flags = 0;
1778
1779   LOG_BUFFER_INIT(f_buf);
1780
1781   /* Note that in this function we assume that rte->attrs is private / uncached */
1782   struct f_val res = interpret(expr);
1783
1784   /* Hack to include EAF_TEMP attributes to the main list */
1785   (*rte)->attrs->eattrs = ea_append(tmp_attrs, (*rte)->attrs->eattrs);
1786
1787   return res;
1788 }
1789
1790 struct f_val
1791 f_eval(struct f_inst *expr, struct linpool *tmp_pool)
1792 {
1793   f_flags = 0;
1794   f_tmp_attrs = NULL;
1795   f_rte = NULL;
1796   f_pool = tmp_pool;
1797
1798   LOG_BUFFER_INIT(f_buf);
1799
1800   return interpret(expr);
1801 }
1802
1803 uint
1804 f_eval_int(struct f_inst *expr)
1805 {
1806   /* Called independently in parse-time to eval expressions */
1807   struct f_val res = f_eval(expr, cfg_mem);
1808
1809   if (res.type != T_INT)
1810     cf_error("Integer expression expected");
1811
1812   return res.val.i;
1813 }
1814
1815 /**
1816  * filter_same - compare two filters
1817  * @new: first filter to be compared
1818  * @old: second filter to be compared, notice that this filter is
1819  * damaged while comparing.
1820  *
1821  * Returns 1 in case filters are same, otherwise 0. If there are
1822  * underlying bugs, it will rather say 0 on same filters than say
1823  * 1 on different.
1824  */
1825 int
1826 filter_same(struct filter *new, struct filter *old)
1827 {
1828   if (old == new)       /* Handle FILTER_ACCEPT and FILTER_REJECT */
1829     return 1;
1830   if (old == FILTER_ACCEPT || old == FILTER_REJECT ||
1831       new == FILTER_ACCEPT || new == FILTER_REJECT)
1832     return 0;
1833   return i_same(new->root, old->root);
1834 }