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 P(a,b) ((a<<8) | b)
  50
  51 #define CMP_ERROR 999
  52
  53 struct adata *
  54 adata_empty(struct linpool *pool)
  55 {
  56   struct adata *res = lp_alloc(pool, sizeof(struct adata));
  57   res->length = 0;
  58   return res;
  59 }
  60
  61 static int
  62 pm_path_compare(struct f_path_mask *m1, struct f_path_mask *m2)
  63 {
  64   while (1) {
  65     if ((!m1) || (!m2))
  66       return !((!m1) && (!m2));
  67     m1 = m1->next;
  68     m2 = m2->next;
  69   }
  70 }
  71
  72 /**
  73  * val_compare - compare two values
  74  * @v1: first value
  75  * @v2: second value
  76  *
  77  * Compares two values and returns -1, 0, 1 on <, =, > or 999 on error.
  78  * Tree module relies on this giving consistent results so that it can
  79  * build balanced trees.
  80  */
  81 int
  82 val_compare(struct f_val v1, struct f_val v2)
  83 {
  84   if ((v1.type == T_VOID) && (v2.type == T_VOID))
  85     return 0;
  86   if (v1.type == T_VOID)        /* Hack for else */
  87     return -1;
  88   if (v2.type == T_VOID)
  89     return 1;
  90
  91   if (v1.type != v2.type) {
  92     debug( "Types do not match in val_compare\n" );
  93     return CMP_ERROR;
  94   }
  95   switch (v1.type) {
  96   case T_ENUM:
  97   case T_INT:
  98   case T_PAIR:
  99     if (v1.val.i == v2.val.i) return 0;
 100     if (v1.val.i < v2.val.i) return -1;
 101     return 1;
 102   case T_IP:
 103   case T_PREFIX:
 104     return ipa_compare(v1.val.px.ip, v2.val.px.ip);
 105   case T_PATH_MASK:
 106     return pm_path_compare(v1.val.path_mask, v2.val.path_mask);
 107   default:
 108     debug( "Compare of unkown entities: %x\n", v1.type );
 109     return CMP_ERROR;
 110   }
 111 }
 112
 113 /*
 114  * val_simple_in_range - check if @v1 ~ @v2 for everything except sets
 115  */
 116 int
 117 val_simple_in_range(struct f_val v1, struct f_val v2)
 118 {
 119   if ((v1.type == T_PATH) && (v2.type == T_PATH_MASK))
 120     return as_path_match(v1.val.ad, v2.val.path_mask);
 121   if ((v1.type == T_PAIR) && (v2.type == T_CLIST))
 122     return int_set_contains(v2.val.ad, v1.val.i);
 123
 124   if ((v1.type == T_IP) && (v2.type == T_PREFIX))
 125     return !(ipa_compare(ipa_and(v2.val.px.ip, ipa_mkmask(v2.val.px.len)), ipa_and(v1.val.px.ip, ipa_mkmask(v2.val.px.len))));
 126
 127   if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX)) {
 128     ip_addr mask;
 129     if (v1.val.px.len & (LEN_PLUS | LEN_MINUS | LEN_RANGE))
 130       return CMP_ERROR;
 131     mask = ipa_mkmask( v2.val.px.len & LEN_MASK );
 132     if (ipa_compare(ipa_and(v2.val.px.ip, mask), ipa_and(v1.val.px.ip, mask)))
 133       return 0;
 134
 135     if ((v2.val.px.len & LEN_MINUS) && (v1.val.px.len <= (v2.val.px.len & LEN_MASK)))
 136       return 0;
 137     if ((v2.val.px.len & LEN_PLUS) && (v1.val.px.len < (v2.val.px.len & LEN_MASK)))
 138       return 0;
 139     if ((v2.val.px.len & LEN_RANGE) && ((v1.val.px.len < (0xff & (v2.val.px.len >> 16)))
 140                                         || (v1.val.px.len > (0xff & (v2.val.px.len >> 8)))))
 141       return 0;
 142     return 1;
 143   }
 144   return CMP_ERROR;
 145 }
 146
 147 /**
 148  * val_in_range - implement |~| operator
 149  * @v1: element
 150  * @v2: set
 151  *
 152  * Checks if @v1 is element (|~| operator) of @v2. Sets are internally represented as balanced trees, see
 153  * |tree.c| module (this is not limited to sets, but for non-set cases, val_simple_in_range() is called early).
 154  */
 155 int
 156 val_in_range(struct f_val v1, struct f_val v2)
 157 {
 158   int res;
 159
 160   res = val_simple_in_range(v1, v2);
 161
 162   if (res != CMP_ERROR)
 163     return res;
 164
 165   if (v2.type == T_SET)
 166     switch (v1.type) {
 167     case T_ENUM:
 168     case T_INT:
 169     case T_IP:
 170     case T_PREFIX:
 171       {
 172         struct f_tree *n;
 173         n = find_tree(v2.val.t, v1);
 174         if (!n)
 175           return 0;
 176         return !! (val_simple_in_range(v1, n->from));   /* We turn CMP_ERROR into compared ok, and that's fine */
 177       }
 178     }
 179   return CMP_ERROR;
 180 }
 181
 182 static void
 183 tree_print(struct f_tree *t)
 184 {
 185   if (!t) {
 186     debug( "() " );
 187     return;
 188   }
 189   debug( "[ " );
 190   tree_print( t->left );
 191   debug( ", " ); val_print( t->from ); debug( ".." ); val_print( t->to ); debug( ", " );
 192   tree_print( t->right );
 193   debug( "] " );
 194 }
 195
 196 /*
 197  * val_print - format filter value
 198  */
 199 void
 200 val_print(struct f_val v)
 201 {
 202   char buf[2048];
 203   char buf2[1024];
 204 #define PRINTF(a...) bsnprintf( buf, 2040, a )
 205   buf[0] = 0;
 206   switch (v.type) {
 207   case T_VOID: PRINTF( "(void)" ); break;
 208   case T_BOOL: PRINTF( v.val.i ? "TRUE" : "FALSE" ); break;
 209   case T_INT: PRINTF( "%d ", v.val.i ); break;
 210   case T_STRING: PRINTF( "%s", v.val.s ); break;
 211   case T_IP: PRINTF( "%I", v.val.px.ip ); break;
 212   case T_PREFIX: PRINTF( "%I/%d", v.val.px.ip, v.val.px.len ); break;
 213   case T_PAIR: PRINTF( "(%d,%d)", v.val.i >> 16, v.val.i & 0xffff ); break;
 214   case T_SET: tree_print( v.val.t ); PRINTF( "\n" ); break;
 215   case T_ENUM: PRINTF( "(enum %x)%d", v.type, v.val.i ); break;
 216   case T_PATH: as_path_format(v.val.ad, buf2, 1020); PRINTF( "(path %s)", buf2 ); break;
 217   case T_CLIST: int_set_format(v.val.ad, buf2, 1020); PRINTF( "(clist %s)", buf2 ); break;
 218   case T_PATH_MASK: debug( "(pathmask " ); { struct f_path_mask *p = v.val.path_mask; while (p) { debug("%d ", p->val); p=p->next; } debug(")" ); } break;
 219   default: PRINTF( "[unknown type %x]", v.type );
 220 #undef PRINTF
 221   }
 222   debug( buf );
 223 }
 224
 225 static struct rte **f_rte, *f_rte_old;
 226 static struct linpool *f_pool;
 227 static struct ea_list **f_tmp_attrs;
 228 static int f_flags;
 229 static rta *f_rta_copy;
 230
 231 /*
 232  * rta_cow - prepare rta for modification by filter
 233  */
 234 void
 235 rta_cow(void)
 236 {
 237   if (!f_rta_copy) {
 238     f_rta_copy = lp_alloc(f_pool, sizeof(rta));
 239     memcpy(f_rta_copy, (*f_rte)->attrs, sizeof(rta));
 240     f_rta_copy->aflags = 0;
 241     *f_rte = rte_cow(*f_rte);
 242     rta_free((*f_rte)->attrs);
 243     (*f_rte)->attrs = f_rta_copy;
 244   }
 245 }
 246
 247 #define runtime(x) do { \
 248     log( L_ERR "filters, line %d: %s", what->lineno, x); \
 249     res.type = T_RETURN; \
 250     res.val.i = F_ERROR; \
 251     return res; \
 252   } while(0)
 253
 254 #define ARG(x,y) \
 255         x = interpret(what->y); \
 256         if (x.type & T_RETURN) \
 257                 return x;
 258
 259 #define ONEARG ARG(v1, a1.p)
 260 #define TWOARGS ARG(v1, a1.p) \
 261                 ARG(v2, a2.p)
 262 #define TWOARGS_C TWOARGS \
 263                   if (v1.type != v2.type) \
 264                     runtime( "Can't operate with values of incompatible types" );
 265
 266 /**
 267  * interpret
 268  * @what: filter to interpret
 269  *
 270  * Interpret given tree of filter instructions. This is core function
 271  * of filter system and does all the hard work.
 272  *
 273  * Each instruction has 4 fields: code (which is instruction code),
 274  * aux (which is extension to instruction code, typically type),
 275  * arg1 and arg2 - arguments. Depending on instruction, arguments
 276  * are either integers, or pointers to instruction trees. Common
 277  * instructions like +, that have two expressions as arguments use
 278  * TWOARGS macro to get both of them evaluated.
 279  *
 280  * &f_val structures are copied around, so there are no problems with
 281  * memory managment.
 282  */
 283 static struct f_val
 284 interpret(struct f_inst *what)
 285 {
 286   struct symbol *sym;
 287   struct f_val v1, v2, res;
 288   int i,j,k;
 289
 290   res.type = T_VOID;
 291   if (!what)
 292     return res;
 293
 294   switch(what->code) {
 295   case ',':
 296     TWOARGS;
 297     break;
 298
 299 /* Binary operators */
 300   case '+':
 301     TWOARGS_C;
 302     switch (res.type = v1.type) {
 303     case T_VOID: runtime( "Can't operate with values of type void" );
 304     case T_INT: res.val.i = v1.val.i + v2.val.i; break;
 305     default: runtime( "Usage of unknown type" );
 306     }
 307     break;
 308   case '-':
 309     TWOARGS_C;
 310     switch (res.type = v1.type) {
 311     case T_VOID: runtime( "Can't operate with values of type void" );
 312     case T_INT: res.val.i = v1.val.i - v2.val.i; break;
 313     default: runtime( "Usage of unknown type" );
 314     }
 315     break;
 316   case '*':
 317     TWOARGS_C;
 318     switch (res.type = v1.type) {
 319     case T_VOID: runtime( "Can't operate with values of type void" );
 320     case T_INT: res.val.i = v1.val.i * v2.val.i; break;
 321     default: runtime( "Usage of unknown type" );
 322     }
 323     break;
 324   case '/':
 325     TWOARGS_C;
 326     switch (res.type = v1.type) {
 327     case T_VOID: runtime( "Can't operate with values of type void" );
 328     case T_INT: if (v2.val.i == 0) runtime( "Mother told me not to divide by 0" );
 329                 res.val.i = v1.val.i / v2.val.i; break;
 330     case T_IP: if (v2.type != T_INT)
 331                  runtime( "Incompatible types in / operator" );
 332                break;
 333     default: runtime( "Usage of unknown type" );
 334     }
 335     break;
 336
 337   case '&':
 338     TWOARGS_C;
 339     res.type = v1.type;
 340     if (res.type != T_BOOL) runtime( "Can't do boolean operation on non-booleans" );
 341     res.val.i = v1.val.i && v2.val.i;
 342     break;
 343   case '|':
 344     TWOARGS_C;
 345     res.type = v1.type;
 346     if (res.type != T_BOOL) runtime( "Can't do boolean operation on non-booleans" );
 347     res.val.i = v1.val.i || v2.val.i;
 348     break;
 349
 350 /* Relational operators */
 351
 352 #define COMPARE(x) \
 353     TWOARGS_C; \
 354     res.type = T_BOOL; \
 355     i = val_compare(v1, v2); \
 356     if (i==CMP_ERROR) \
 357       runtime( "Error in comparison" ); \
 358     res.val.i = (x); \
 359     break;
 360
 361   case P('!','='): COMPARE(i!=0);
 362   case P('=','='): COMPARE(i==0);
 363   case '<': COMPARE(i==-1);
 364   case P('<','='): COMPARE(i!=1);
 365
 366   case '!':
 367     ONEARG;
 368     if (v1.type != T_BOOL)
 369       runtime( "Not applied to non-boolean" );
 370     res = v1;
 371     res.val.i = !res.val.i;
 372     break;
 373
 374   case '~':
 375     TWOARGS;
 376     res.type = T_BOOL;
 377     res.val.i = val_in_range(v1, v2);
 378     if (res.val.i == CMP_ERROR)
 379       runtime( "~ applied on unknown type pair" );
 380     break;
 381   case P('d','e'):
 382     ONEARG;
 383     res.type = T_BOOL;
 384     res.val.i = (v1.type != T_VOID);
 385     break;
 386
 387   /* Set to indirect value, a1 = variable, a2 = value */
 388   case 's':
 389     ARG(v2, a2.p);
 390     sym = what->a1.p;
 391     switch (res.type = v2.type) {
 392     case T_VOID: runtime( "Can't assign void values" );
 393     case T_ENUM:
 394     case T_INT:
 395     case T_IP:
 396     case T_PREFIX:
 397     case T_PAIR:
 398     case T_PATH:
 399     case T_CLIST:
 400     case T_PATH_MASK:
 401       if (sym->class != (SYM_VARIABLE | v2.type))
 402         runtime( "Assigning to variable of incompatible type" );
 403       * (struct f_val *) sym->aux2 = v2;
 404       break;
 405     default:
 406       bug( "Set to invalid type" );
 407     }
 408     break;
 409
 410   case 'c':     /* integer (or simple type) constant */
 411     res.type = what->aux;
 412     res.val.i = what->a2.i;
 413     break;
 414   case 'C':
 415     res = * ((struct f_val *) what->a1.p);
 416     break;
 417   case 'p':
 418     ONEARG;
 419     val_print(v1);
 420     break;
 421   case '?':     /* ? has really strange error value, so we can implement if ... else nicely :-) */
 422     ONEARG;
 423     if (v1.type != T_BOOL)
 424       runtime( "If requires boolean expression" );
 425     if (v1.val.i) {
 426       ARG(res,a2.p);
 427       res.val.i = 0;
 428     } else res.val.i = 1;
 429     res.type = T_BOOL;
 430     break;
 431   case '0':
 432     debug( "No operation\n" );
 433     break;
 434   case P('p',','):
 435     ONEARG;
 436     if (what->a2.i == F_NOP || (what->a2.i != F_NONL && what->a1.p))
 437       debug( "\n" );
 438
 439     switch (what->a2.i) {
 440     case F_QUITBIRD:
 441       die( "Filter asked me to die" );
 442     case F_ACCEPT:
 443       /* Should take care about turning ACCEPT into MODIFY */
 444     case F_ERROR:
 445     case F_REJECT:      /* FIXME (noncritical) Should print complete route along with reason to reject route */
 446       res.type = T_RETURN;
 447       res.val.i = what->a2.i;
 448       return res;       /* We have to return now, no more processing. */
 449     case F_NONL:
 450     case F_NOP:
 451       break;
 452     default:
 453       bug( "unknown return type: Can't happen");
 454     }
 455     break;
 456   case 'a':     /* rta access */
 457     {
 458       struct rta *rta = (*f_rte)->attrs;
 459       res.type = what->aux;
 460       switch(res.type) {
 461       case T_IP:
 462         res.val.px.ip = * (ip_addr *) ((char *) rta + what->a2.i);
 463         break;
 464       case T_ENUM:
 465         res.val.i = * ((char *) rta + what->a2.i);
 466         break;
 467       case T_PREFIX:    /* Warning: this works only for prefix of network */
 468         {
 469           res.val.px.ip = (*f_rte)->net->n.prefix;
 470           res.val.px.len = (*f_rte)->net->n.pxlen;
 471           break;
 472         }
 473       default:
 474         bug( "Invalid type for rta access (%x)", res.type );
 475       }
 476     }
 477     break;
 478   case P('a','S'):
 479     ONEARG;
 480     if (what->aux != v1.type)
 481       runtime( "Attempt to set static attribute to incompatible type" );
 482     rta_cow();
 483     {
 484       struct rta *rta = (*f_rte)->attrs;
 485       switch (what->aux) {
 486       case T_ENUM:
 487         * ((char *) rta + what->a2.i) = v1.val.i;
 488         break;
 489       case T_IP:
 490         * (ip_addr *) ((char *) rta + what->a2.i) = v1.val.px.ip;
 491         break;
 492       default:
 493         bug( "Unknown type in set of static attribute" );
 494       }
 495     }
 496     break;
 497   case P('e','a'):      /* Access to extended attributes */
 498     {
 499       eattr *e = NULL;
 500       if (!(f_flags & FF_FORCE_TMPATTR))
 501         e = ea_find( (*f_rte)->attrs->eattrs, what->a2.i );
 502       if (!e)
 503         e = ea_find( (*f_tmp_attrs), what->a2.i );
 504       if ((!e) && (f_flags & FF_FORCE_TMPATTR))
 505         e = ea_find( (*f_rte)->attrs->eattrs, what->a2.i );
 506
 507       switch (what->aux & EAF_TYPE_MASK) {
 508       case EAF_TYPE_INT:
 509         if (!e) {
 510           res.type = T_VOID;
 511           break;
 512         }
 513         res.type = T_INT;
 514         res.val.i = e->u.data;
 515         break;
 516       case EAF_TYPE_AS_PATH:
 517         if (!e) {
 518           res.type = T_VOID;
 519           break;
 520         }
 521         res.type = T_PATH;
 522         res.val.ad = e->u.ptr;
 523         break;
 524       case EAF_TYPE_INT_SET:
 525         if (!e) {
 526           res.type = T_CLIST;
 527           res.val.ad = adata_empty(f_pool);
 528           break;
 529         }
 530         res.type = T_CLIST;
 531         res.val.ad = e->u.ptr;
 532         break;
 533       default:
 534         bug("Unknown type in e,a");
 535       }
 536     }
 537     break;
 538   case P('e','S'):
 539     ONEARG;
 540     {
 541       struct ea_list *l = lp_alloc(f_pool, sizeof(struct ea_list) + sizeof(eattr));
 542
 543       l->next = NULL;
 544       l->flags = EALF_SORTED;
 545       l->count = 1;
 546       l->attrs[0].id = what->a2.i;
 547       l->attrs[0].flags = 0;
 548       l->attrs[0].type = what->aux | EAF_ORIGINATED;
 549       switch (what->aux & EAF_TYPE_MASK) {
 550       case EAF_TYPE_INT:
 551         if (v1.type != T_INT)
 552           runtime( "Setting int attribute to non-int value" );
 553         l->attrs[0].u.data = v1.val.i;
 554         break;
 555       case EAF_TYPE_AS_PATH:
 556         if (v1.type != T_PATH)
 557           runtime( "Setting path attribute to non-path value" );
 558         l->attrs[0].u.ptr = v1.val.ad;
 559         break;
 560       case EAF_TYPE_INT_SET:
 561         if (v1.type != T_CLIST)
 562           runtime( "Setting int set attribute to non-clist value" );
 563         l->attrs[0].u.ptr = v1.val.ad;
 564         break;
 565       case EAF_TYPE_UNDEF:
 566         if (v1.type != T_VOID)
 567           runtime( "Setting void attribute to non-void value" );
 568         l->attrs[0].u.data = 0;
 569         break;
 570       default: bug("Unknown type in e,S");
 571       }
 572
 573       if (!(what->aux & EAF_TEMP) && (!(f_flags & FF_FORCE_TMPATTR))) {
 574         rta_cow();
 575         l->next = f_rta_copy->eattrs;
 576         f_rta_copy->eattrs = l;
 577       } else {
 578         l->next = (*f_tmp_attrs);
 579         (*f_tmp_attrs) = l;
 580       }
 581     }
 582     break;
 583   case 'P':
 584     res.type = T_INT;
 585     res.val.i = (*f_rte)->pref;
 586     break;
 587   case P('P','S'):
 588     ONEARG;
 589     if (v1.type != T_INT)
 590       runtime( "Can't set preference to non-integer" );
 591     *f_rte = rte_cow(*f_rte);
 592     (*f_rte)->pref = v1.val.i;
 593     break;
 594   case 'L':     /* Get length of */
 595     ONEARG;
 596     res.type = T_INT;
 597     switch(v1.type) {
 598     case T_PREFIX: res.val.i = v1.val.px.len; break;
 599     case T_PATH:   res.val.i = as_path_getlen(v1.val.ad); break;
 600     default: bug( "Length of what?" );
 601     }
 602     break;
 603   case P('c','p'):      /* Convert prefix to ... */
 604     ONEARG;
 605     if (v1.type != T_PREFIX)
 606       runtime( "Prefix expected" );
 607     res.type = what->aux;
 608     switch(res.type) {
 609       /*    case T_INT: res.val.i = v1.val.px.len; break; Not needed any more */
 610     case T_IP: res.val.px.ip = v1.val.px.ip; break;
 611     default: bug( "Unknown prefix to conversion" );
 612     }
 613     break;
 614   case 'r':
 615     ONEARG;
 616     res = v1;
 617     res.type |= T_RETURN;
 618     break;
 619   case P('c','a'): /* CALL: this is special: if T_RETURN and returning some value, mask it out  */
 620     ONEARG;
 621     res = interpret(what->a2.p);
 622     if (res.type == T_RETURN)
 623       return res;
 624     res.type &= ~T_RETURN;
 625     break;
 626   case P('S','W'):
 627     ONEARG;
 628     {
 629       struct f_tree *t = find_tree(what->a2.p, v1);
 630       if (!t) {
 631         v1.type = T_VOID;
 632         t = find_tree(what->a2.p, v1);
 633         if (!t) {
 634           debug( "No else statement?\n");
 635           break;
 636         }
 637       }
 638       /* It is actually possible to have t->data NULL */
 639       return interpret(t->data);
 640     }
 641     break;
 642   case P('i','M'): /* IP.MASK(val) */
 643     TWOARGS;
 644     if (v2.type != T_INT)
 645       runtime( "Integer expected");
 646     if (v1.type != T_IP)
 647       runtime( "You can mask only IP addresses" );
 648     {
 649       ip_addr mask = ipa_mkmask(v2.val.i);
 650       res.type = T_IP;
 651       res.val.px.ip = ipa_and(mask, v1.val.px.ip);
 652     }
 653     break;
 654
 655   case 'E':     /* Create empty attribute */
 656     res.type = what->aux;
 657     res.val.ad = adata_empty(f_pool);
 658     break;
 659   case P('A','p'):      /* Path prepend */
 660     TWOARGS;
 661     if (v1.type != T_PATH)
 662       runtime("Can't prepend to non-path");
 663     if (v2.type != T_INT)
 664       runtime("Can't prepend non-integer");
 665
 666     res.type = T_PATH;
 667     res.val.ad = as_path_prepend(f_pool, v1.val.ad, v2.val.i);
 668     break;
 669
 670   case P('C','a'):      /* Community list add or delete */
 671     TWOARGS;
 672     if (v1.type != T_CLIST)
 673       runtime("Can't add/delete to non-clist");
 674     if (v2.type != T_PAIR)
 675       runtime("Can't add/delete non-pair");
 676
 677     res.type = T_CLIST;
 678     switch (what->aux) {
 679     case 'a': res.val.ad = int_set_add(f_pool, v1.val.ad, v2.val.i); break;
 680     case 'd': res.val.ad = int_set_del(f_pool, v1.val.ad, v2.val.i); break;
 681     default: bug("unknown Ca operation");
 682     }
 683     break;
 684
 685   default:
 686     bug( "Unknown instruction %d (%c)", what->code, what->code & 0xff);
 687   }
 688   if (what->next)
 689     return interpret(what->next);
 690   return res;
 691 }
 692
 693 #undef ARG
 694 #define ARG(x,y) \
 695         if (!i_same(f1->y, f2->y)) \
 696                 return 0;
 697
 698 #define ONEARG ARG(v1, a1.p)
 699 #define TWOARGS ARG(v1, a1.p) \
 700                 ARG(v2, a2.p)
 701
 702 #define A2_SAME if (f1->a2.i != f2->a2.i) return 0;
 703
 704 /*
 705  * i_same - function that does real comparing of instruction trees, you should call filter_same from outside
 706  */
 707 int
 708 i_same(struct f_inst *f1, struct f_inst *f2)
 709 {
 710   if ((!!f1) != (!!f2))
 711     return 0;
 712   if (!f1)
 713     return 1;
 714   if (f1->aux != f2->aux)
 715     return 0;
 716   if (f1->code != f2->code)
 717     return 0;
 718   if (f1 == f2)         /* It looks strange, but it is possible with call rewriting trickery */
 719     return 1;
 720
 721   switch(f1->code) {
 722   case ',': /* fall through */
 723   case '+':
 724   case '-':
 725   case '*':
 726   case '/':
 727   case '|':
 728   case '&':
 729   case P('!','='):
 730   case P('=','='):
 731   case '<':
 732   case P('<','='): TWOARGS; break;
 733
 734   case '!': ONEARG; break;
 735   case '~': TWOARGS; break;
 736   case P('d','e'): ONEARG; break;
 737
 738   case 's':
 739     ARG(v2, a2.p);
 740     {
 741       struct symbol *s1, *s2;
 742       s1 = f1->a1.p;
 743       s2 = f2->a1.p;
 744       if (strcmp(s1->name, s2->name))
 745         return 0;
 746       if (s1->class != s2->class)
 747         return 0;
 748     }
 749     break;
 750
 751   case 'c': A2_SAME; break;
 752   case 'C':
 753     if (val_compare(* (struct f_val *) f1->a1.p, * (struct f_val *) f2->a1.p))
 754       return 0;
 755     break;
 756   case 'p': case 'L': ONEARG; break;
 757   case '?': TWOARGS; break;
 758   case '0': case 'E': break;
 759   case P('p',','): ONEARG; A2_SAME; break;
 760   case 'P':
 761   case 'a': A2_SAME; break;
 762   case P('e','a'): A2_SAME; break;
 763   case P('P','S'):
 764   case P('a','S'):
 765   case P('e','S'): ONEARG; A2_SAME; break;
 766
 767   case 'r': ONEARG; break;
 768   case P('c','p'): ONEARG; break;
 769   case P('c','a'): /* Call rewriting trickery to avoid exponential behaviour */
 770              ONEARG;
 771              if (!i_same(f1->a2.p, f2->a2.p))
 772                return 0;
 773              f2->a2.p = f1->a2.p;
 774              break;
 775   case P('S','W'): ONEARG; if (!same_tree(f1->a2.p, f2->a2.p)) return 0; break;
 776   case P('i','M'): TWOARGS; break;
 777   case P('A','p'): TWOARGS; break;
 778   case P('C','a'): TWOARGS; break;
 779   default:
 780     bug( "Unknown instruction %d in same (%c)", f1->code, f1->code & 0xff);
 781   }
 782   return i_same(f1->next, f2->next);
 783 }
 784
 785 /**
 786  * f_run - external entry point to filters
 787  * @filter: pointer to filter to run
 788  * @tmp_attrs: where to store newly generated temporary attributes
 789  * @rte: pointer to pointer to &rte being filtered. When route is modified, this is changed with rte_cow().
 790  * @tmp_pool: all filter allocations go from this pool
 791  * @flags: flags
 792  */
 793 int
 794 f_run(struct filter *filter, struct rte **rte, struct ea_list **tmp_attrs, struct linpool *tmp_pool, int flags)
 795 {
 796   struct f_inst *inst;
 797   struct f_val res;
 798   DBG( "Running filter `%s'...", filter->name );
 799
 800   f_flags = flags;
 801   f_tmp_attrs = tmp_attrs;
 802   f_rte = rte;
 803   f_rte_old = *rte;
 804   f_rta_copy = NULL;
 805   f_pool = tmp_pool;
 806   inst = filter->root;
 807   res = interpret(inst);
 808   if (res.type != T_RETURN) {
 809     log( L_ERR "Filter %s did not return accept nor reject. Make up your mind", filter->name);
 810     return F_ERROR;
 811   }
 812   DBG( "done (%d)\n", res.val.i );
 813   return res.val.i;
 814 }
 815
 816 int
 817 f_eval_int(struct f_inst *expr)
 818 {
 819   struct f_val res;
 820
 821   f_flags = 0;
 822   f_tmp_attrs = NULL;
 823   f_rte = NULL;
 824   f_rte_old = NULL;
 825   f_rta_copy = NULL;
 826   f_pool = cfg_mem;
 827   res = interpret(expr);
 828   if (res.type != T_INT)
 829     cf_error("Integer expression expected");
 830   return res.val.i;
 831 }
 832
 833 /**
 834  * filter_same - compare two filters
 835  * @new: first filter to be compared
 836  * @old: second filter to be compared, notice that this filter is
 837  * damaged while comparing.
 838  *
 839  * Returns 1 in case filters are same, otherwise 0. If there are
 840  * underlying bugs, it will rather say 0 on same filters than say
 841  * 1 on different.
 842  */
 843 int
 844 filter_same(struct filter *new, struct filter *old)
 845 {
 846   if (old == new)       /* Handle FILTER_ACCEPT and FILTER_REJECT */
 847     return 1;
 848   if (old == FILTER_ACCEPT || old == FILTER_REJECT ||
 849       new == FILTER_ACCEPT || new == FILTER_REJECT)
 850     return 0;
 851   return i_same(new->root, old->root);
 852 }