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