Statistics
| Branch: | Revision:

iof-bird-daemon / filter / filter.c @ e29fa06e

History | View | Annotate | Download (23 KB)

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
    m1 = m1->next;
68
    m2 = m2->next;
69
  }
70
}
71

    
72
static void
73
pm_format(struct f_path_mask *p, byte *buf, unsigned int size)
74
{
75
  byte *end = buf + size - 16;
76

    
77
  while (p)
78
    {
79
      if (buf > end)
80
        {
81
          strcpy(buf, " ...");
82
          return;
83
        }
84

    
85
      if (p->any)
86
        buf += bsprintf(buf, "? ");
87
      else
88
        buf += bsprintf(buf, "%u ", p->val);
89

    
90
      p = p->next;
91
    }
92

    
93
  *buf = 0;
94
}
95

    
96
/**
97
 * val_compare - compare two values
98
 * @v1: first value
99
 * @v2: second value
100
 *
101
 * Compares two values and returns -1, 0, 1 on <, =, > or 999 on error.
102
 * Tree module relies on this giving consistent results so that it can
103
 * build balanced trees.
104
 */
105
int
106
val_compare(struct f_val v1, struct f_val v2)
107
{
108
  int rc;
109

    
110
  if ((v1.type == T_VOID) && (v2.type == T_VOID))
111
    return 0;
112
  if (v1.type == T_VOID)        /* Hack for else */
113
    return -1;
114
  if (v2.type == T_VOID)
115
    return 1;
116

    
117
  if (v1.type != v2.type) {
118
    debug( "Types do not match in val_compare\n" );
119
    return CMP_ERROR;
120
  }
121
  switch (v1.type) {
122
  case T_ENUM:
123
  case T_INT: 
124
  case T_PAIR:
125
    if (v1.val.i == v2.val.i) return 0;
126
    if (v1.val.i < v2.val.i) return -1;
127
    return 1;
128
  case T_IP:
129
    return ipa_compare(v1.val.px.ip, v2.val.px.ip);
130
  case T_PREFIX:
131
    if (rc = ipa_compare(v1.val.px.ip, v2.val.px.ip))
132
      return rc;
133
    if (v1.val.px.len < v2.val.px.len)
134
      return -1;
135
    if (v1.val.px.len > v2.val.px.len)
136
      return 1;
137
    return 0;
138
  case T_PATH_MASK:
139
    return pm_path_compare(v1.val.path_mask, v2.val.path_mask);
140
  case T_STRING:
141
    return strcmp(v1.val.s, v2.val.s);
142
  default:
143
    debug( "Compare of unkown entities: %x\n", v1.type );
144
    return CMP_ERROR;
145
  }
146
}
147

    
148
/*
149
 * val_simple_in_range - check if @v1 ~ @v2 for everything except sets
150
 */ 
151
static int
152
val_simple_in_range(struct f_val v1, struct f_val v2)
153
{
154
  if ((v1.type == T_PATH) && (v2.type == T_PATH_MASK))
155
    return as_path_match(v1.val.ad, v2.val.path_mask);
156
  if ((v1.type == T_PAIR) && (v2.type == T_CLIST))
157
    return int_set_contains(v2.val.ad, v1.val.i);
158
  if ((v1.type == T_STRING) && (v2.type == T_STRING))
159
    return patmatch(v2.val.s, v1.val.s);
160

    
161
  if ((v1.type == T_IP) && (v2.type == T_PREFIX))
162
    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))));
163

    
164
  if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX)) {
165
    ip_addr mask;
166
    if (v1.val.px.len & (LEN_PLUS | LEN_MINUS | LEN_RANGE))
167
      return CMP_ERROR;
168
    mask = ipa_mkmask( v2.val.px.len & LEN_MASK );
169
    if (ipa_compare(ipa_and(v2.val.px.ip, mask), ipa_and(v1.val.px.ip, mask)))
170
      return 0;
171

    
172
    if ((v2.val.px.len & LEN_MINUS) && (v1.val.px.len <= (v2.val.px.len & LEN_MASK)))
173
      return 0;
174
    if ((v2.val.px.len & LEN_PLUS) && (v1.val.px.len < (v2.val.px.len & LEN_MASK)))
175
      return 0;
176
    if ((v2.val.px.len & LEN_RANGE) && ((v1.val.px.len < (0xff & (v2.val.px.len >> 16)))
177
                                        || (v1.val.px.len > (0xff & (v2.val.px.len >> 8)))))
178
      return 0;
179
    return 1;    
180
  }
181
  return CMP_ERROR;
182
}
183

    
184
/**
185
 * val_in_range - implement |~| operator
186
 * @v1: element
187
 * @v2: set
188
 *
189
 * Checks if @v1 is element (|~| operator) of @v2. Sets are internally represented as balanced trees, see
190
 * |tree.c| module (this is not limited to sets, but for non-set cases, val_simple_in_range() is called early).
191
 */
192
static int
193
val_in_range(struct f_val v1, struct f_val v2)
194
{
195
  int res;
196

    
197
  res = val_simple_in_range(v1, v2);
198

    
199
  if (res != CMP_ERROR)
200
    return res;
201
  
202
  if (v2.type == T_SET)
203
    switch (v1.type) {
204
    case T_ENUM:
205
    case T_INT:
206
    case T_IP:
207
    case T_PREFIX:
208
      {
209
        struct f_tree *n;
210
        n = find_tree(v2.val.t, v1);
211
        if (!n)
212
          return 0;
213
        return !! (val_simple_in_range(v1, n->from));        /* We turn CMP_ERROR into compared ok, and that's fine */
214
      }
215
    }
216
  return CMP_ERROR;
217
}
218

    
219
static void
220
tree_print(struct f_tree *t)
221
{
222
  if (!t) {
223
    debug( "() " );
224
    return;
225
  }
226
  debug( "[ " );
227
  tree_print( t->left );
228
  debug( ", " ); val_print( t->from ); debug( ".." ); val_print( t->to ); debug( ", " );
229
  tree_print( t->right );
230
  debug( "] " );
231
}
232

    
233
/*
234
 * val_print - format filter value
235
 */
236
void
237
val_print(struct f_val v)
238
{
239
  char buf[2048];
240
  char buf2[1024];
241
#define PRINTF(a...) bsnprintf( buf, 2040, a )
242
  buf[0] = 0;
243
  switch (v.type) {
244
  case T_VOID: PRINTF( "(void)" ); break;
245
  case T_BOOL: PRINTF( v.val.i ? "TRUE" : "FALSE" ); break;
246
  case T_INT: PRINTF( "%d ", v.val.i ); break;
247
  case T_STRING: PRINTF( "%s", v.val.s ); break;
248
  case T_IP: PRINTF( "%I", v.val.px.ip ); break;
249
  case T_PREFIX: PRINTF( "%I/%d", v.val.px.ip, v.val.px.len ); break;
250
  case T_PAIR: PRINTF( "(%d,%d)", v.val.i >> 16, v.val.i & 0xffff ); break;
251
  case T_SET: tree_print( v.val.t ); PRINTF( "\n" ); break;
252
  case T_ENUM: PRINTF( "(enum %x)%d", v.type, v.val.i ); break;
253
  case T_PATH: as_path_format(v.val.ad, buf2, 1020); PRINTF( "(path %s)", buf2 ); break;
254
  case T_CLIST: int_set_format(v.val.ad, 1, buf2, 1020); PRINTF( "(clist %s)", buf2 ); break;
255
  case T_PATH_MASK: pm_format(v.val.path_mask, buf2, 1020); PRINTF( "(pathmask %s)", buf2 ); break;
256
  default: PRINTF( "[unknown type %x]", v.type );
257
#undef PRINTF
258
  }
259
  debug( buf );
260
}
261

    
262
static struct rte **f_rte, *f_rte_old;
263
static struct linpool *f_pool;
264
static struct ea_list **f_tmp_attrs;
265
static int f_flags;
266
static rta *f_rta_copy;
267

    
268
/*
269
 * rta_cow - prepare rta for modification by filter
270
 */
271
static void
272
rta_cow(void)
273
{
274
  if (!f_rta_copy) {
275
    f_rta_copy = lp_alloc(f_pool, sizeof(rta));
276
    memcpy(f_rta_copy, (*f_rte)->attrs, sizeof(rta));
277
    f_rta_copy->aflags = 0;
278
    *f_rte = rte_cow(*f_rte);
279
    rta_free((*f_rte)->attrs);
280
    (*f_rte)->attrs = f_rta_copy;
281
  }
282
}
283

    
284
#define runtime(x) do { \
285
    log( L_ERR "filters, line %d: %s", what->lineno, x); \
286
    res.type = T_RETURN; \
287
    res.val.i = F_ERROR; \
288
    return res; \
289
  } while(0)
290

    
291
#define ARG(x,y) \
292
        x = interpret(what->y); \
293
        if (x.type & T_RETURN) \
294
                return x;
295

    
296
#define ONEARG ARG(v1, a1.p)
297
#define TWOARGS ARG(v1, a1.p) \
298
                ARG(v2, a2.p)
299
#define TWOARGS_C TWOARGS \
300
                  if (v1.type != v2.type) \
301
                    runtime( "Can't operate with values of incompatible types" );
302

    
303
/**
304
 * interpret
305
 * @what: filter to interpret
306
 *
307
 * Interpret given tree of filter instructions. This is core function
308
 * of filter system and does all the hard work.
309
 *
310
 * Each instruction has 4 fields: code (which is instruction code),
311
 * aux (which is extension to instruction code, typically type),
312
 * arg1 and arg2 - arguments. Depending on instruction, arguments
313
 * are either integers, or pointers to instruction trees. Common 
314
 * instructions like +, that have two expressions as arguments use
315
 * TWOARGS macro to get both of them evaluated.
316
 *
317
 * &f_val structures are copied around, so there are no problems with
318
 * memory managment.
319
 */
320
static struct f_val
321
interpret(struct f_inst *what)
322
{
323
  struct symbol *sym;
324
  struct f_val v1, v2, res;
325
  int i;
326

    
327
  res.type = T_VOID;
328
  if (!what)
329
    return res;
330

    
331
  switch(what->code) {
332
  case ',':
333
    TWOARGS;
334
    break;
335

    
336
/* Binary operators */
337
  case '+':
338
    TWOARGS_C;
339
    switch (res.type = v1.type) {
340
    case T_VOID: runtime( "Can't operate with values of type void" );
341
    case T_INT: res.val.i = v1.val.i + v2.val.i; break;
342
    default: runtime( "Usage of unknown type" );
343
    }
344
    break;
345
  case '-':
346
    TWOARGS_C;
347
    switch (res.type = v1.type) {
348
    case T_VOID: runtime( "Can't operate with values of type void" );
349
    case T_INT: res.val.i = v1.val.i - v2.val.i; break;
350
    default: runtime( "Usage of unknown type" );
351
    }
352
    break;
353
  case '*':
354
    TWOARGS_C;
355
    switch (res.type = v1.type) {
356
    case T_VOID: runtime( "Can't operate with values of type void" );
357
    case T_INT: res.val.i = v1.val.i * v2.val.i; break;
358
    default: runtime( "Usage of unknown type" );
359
    }
360
    break;
361
  case '/':
362
    TWOARGS_C;
363
    switch (res.type = v1.type) {
364
    case T_VOID: runtime( "Can't operate with values of type void" );
365
    case T_INT: if (v2.val.i == 0) runtime( "Mother told me not to divide by 0" );
366
                      res.val.i = v1.val.i / v2.val.i; break;
367
    case T_IP: if (v2.type != T_INT)
368
                 runtime( "Incompatible types in / operator" );
369
               break;
370
    default: runtime( "Usage of unknown type" );
371
    }
372
    break;
373
    
374
  case '&':
375
    TWOARGS_C;
376
    res.type = v1.type;
377
    if (res.type != T_BOOL) runtime( "Can't do boolean operation on non-booleans" );
378
    res.val.i = v1.val.i && v2.val.i;
379
    break;
380
  case '|':
381
    TWOARGS_C;
382
    res.type = v1.type;
383
    if (res.type != T_BOOL) runtime( "Can't do boolean operation on non-booleans" );
384
    res.val.i = v1.val.i || v2.val.i;
385
    break;
386

    
387
/* Relational operators */
388

    
389
#define COMPARE(x) \
390
    TWOARGS_C; \
391
    res.type = T_BOOL; \
392
    i = val_compare(v1, v2); \
393
    if (i==CMP_ERROR) \
394
      runtime( "Error in comparison" ); \
395
    res.val.i = (x); \
396
    break;
397

    
398
  case P('!','='): COMPARE(i!=0);
399
  case P('=','='): COMPARE(i==0);
400
  case '<': COMPARE(i==-1);
401
  case P('<','='): COMPARE(i!=1);
402

    
403
  case '!':
404
    ONEARG;
405
    if (v1.type != T_BOOL)
406
      runtime( "Not applied to non-boolean" );
407
    res = v1;
408
    res.val.i = !res.val.i;
409
    break;
410

    
411
  case '~':
412
    TWOARGS;
413
    res.type = T_BOOL;
414
    res.val.i = val_in_range(v1, v2);
415
    if (res.val.i == CMP_ERROR)
416
      runtime( "~ applied on unknown type pair" );
417
    break;
418
  case P('d','e'):
419
    ONEARG;
420
    res.type = T_BOOL;
421
    res.val.i = (v1.type != T_VOID);
422
    break;
423

    
424
  /* Set to indirect value, a1 = variable, a2 = value */
425
  case 's':
426
    ARG(v2, a2.p);
427
    sym = what->a1.p;
428
    switch (res.type = v2.type) {
429
    case T_VOID: runtime( "Can't assign void values" );
430
    case T_ENUM:
431
    case T_INT: 
432
    case T_IP: 
433
    case T_PREFIX: 
434
    case T_PAIR: 
435
    case T_PATH:
436
    case T_CLIST:
437
    case T_PATH_MASK:
438
      if (sym->class != (SYM_VARIABLE | v2.type))
439
        runtime( "Assigning to variable of incompatible type" );
440
      * (struct f_val *) sym->aux2 = v2; 
441
      break;
442
    default:
443
      bug( "Set to invalid type" );
444
    }
445
    break;
446

    
447
  case 'c':        /* integer (or simple type) constant */
448
    res.type = what->aux;
449
    res.val.i = what->a2.i;
450
    break;
451
  case 'C':
452
    res = * ((struct f_val *) what->a1.p);
453
    break;
454
  case 'p':
455
    ONEARG;
456
    val_print(v1);
457
    break;
458
  case '?':        /* ? has really strange error value, so we can implement if ... else nicely :-) */
459
    ONEARG;
460
    if (v1.type != T_BOOL)
461
      runtime( "If requires boolean expression" );
462
    if (v1.val.i) {
463
      ARG(res,a2.p);
464
      res.val.i = 0;
465
    } else res.val.i = 1;
466
    res.type = T_BOOL;
467
    break;
468
  case '0':
469
    debug( "No operation\n" );
470
    break;
471
  case P('p',','):
472
    ONEARG;
473
    if (what->a2.i == F_NOP || (what->a2.i != F_NONL && what->a1.p))
474
      debug( "\n" );
475

    
476
    switch (what->a2.i) {
477
    case F_QUITBIRD:
478
      die( "Filter asked me to die" );
479
    case F_ACCEPT:
480
      /* Should take care about turning ACCEPT into MODIFY */
481
    case F_ERROR:
482
    case F_REJECT:        /* FIXME (noncritical) Should print complete route along with reason to reject route */
483
      res.type = T_RETURN;
484
      res.val.i = what->a2.i;
485
      return res;        /* We have to return now, no more processing. */
486
    case F_NONL:
487
    case F_NOP:
488
      break;
489
    default:
490
      bug( "unknown return type: Can't happen");
491
    }
492
    break;
493
  case 'a':        /* rta access */
494
    {
495
      struct rta *rta = (*f_rte)->attrs;
496
      res.type = what->aux;
497
      switch(res.type) {
498
      case T_IP:
499
        res.val.px.ip = * (ip_addr *) ((char *) rta + what->a2.i);
500
        break;
501
      case T_ENUM:
502
        res.val.i = * ((char *) rta + what->a2.i);
503
        break;
504
      case T_STRING:        /* Warning: this is a special case for proto attribute */
505
        res.val.s = rta->proto->name;
506
        break;
507
      case T_PREFIX:        /* Warning: this works only for prefix of network */
508
        {
509
          res.val.px.ip = (*f_rte)->net->n.prefix;
510
          res.val.px.len = (*f_rte)->net->n.pxlen;
511
          break;
512
        }
513
      default:
514
        bug( "Invalid type for rta access (%x)", res.type );
515
      }
516
    }
517
    break;
518
  case P('a','S'):
519
    ONEARG;
520
    if (what->aux != v1.type)
521
      runtime( "Attempt to set static attribute to incompatible type" );
522
    rta_cow();
523
    {
524
      struct rta *rta = (*f_rte)->attrs;
525
      switch (what->aux) {
526
      case T_ENUM:
527
        * ((char *) rta + what->a2.i) = v1.val.i;
528
        break;
529
      case T_IP:
530
        * (ip_addr *) ((char *) rta + what->a2.i) = v1.val.px.ip;
531
        break;
532
      default:
533
        bug( "Unknown type in set of static attribute" );
534
      }
535
    }
536
    break;
537
  case P('e','a'):        /* Access to extended attributes */
538
    {
539
      eattr *e = NULL;
540
      if (!(f_flags & FF_FORCE_TMPATTR))
541
        e = ea_find( (*f_rte)->attrs->eattrs, what->a2.i );
542
      if (!e) 
543
        e = ea_find( (*f_tmp_attrs), what->a2.i );
544
      if ((!e) && (f_flags & FF_FORCE_TMPATTR))
545
        e = ea_find( (*f_rte)->attrs->eattrs, what->a2.i );
546
      
547
      switch (what->aux & EAF_TYPE_MASK) {
548
      case EAF_TYPE_INT:
549
        if (!e) {
550
          res.type = T_VOID;
551
          break;
552
        }
553
        res.type = T_INT;
554
        res.val.i = e->u.data;
555
        break;
556
      case EAF_TYPE_AS_PATH:
557
        if (!e) {
558
          res.type = T_VOID;
559
          break;
560
        }
561
        res.type = T_PATH;
562
        res.val.ad = e->u.ptr;
563
        break;
564
      case EAF_TYPE_INT_SET:
565
        if (!e) {
566
          res.type = T_CLIST;
567
          res.val.ad = adata_empty(f_pool);
568
          break;
569
        }
570
        res.type = T_CLIST;
571
        res.val.ad = e->u.ptr;
572
        break;
573
      default:
574
        bug("Unknown type in e,a");
575
      }
576
    }
577
    break;
578
  case P('e','S'):
579
    ONEARG;
580
    {
581
      struct ea_list *l = lp_alloc(f_pool, sizeof(struct ea_list) + sizeof(eattr));
582

    
583
      l->next = NULL;
584
      l->flags = EALF_SORTED;
585
      l->count = 1;
586
      l->attrs[0].id = what->a2.i;
587
      l->attrs[0].flags = 0;
588
      l->attrs[0].type = what->aux | EAF_ORIGINATED;
589
      switch (what->aux & EAF_TYPE_MASK) {
590
      case EAF_TYPE_INT:
591
        if (v1.type != T_INT)
592
          runtime( "Setting int attribute to non-int value" );
593
        l->attrs[0].u.data = v1.val.i;
594
        break;
595
      case EAF_TYPE_AS_PATH:
596
        if (v1.type != T_PATH)
597
          runtime( "Setting path attribute to non-path value" );
598
        l->attrs[0].u.ptr = v1.val.ad;
599
        break;
600
      case EAF_TYPE_INT_SET:
601
        if (v1.type != T_CLIST)
602
          runtime( "Setting int set attribute to non-clist value" );
603
        l->attrs[0].u.ptr = v1.val.ad;
604
        break;
605
      case EAF_TYPE_UNDEF:
606
        if (v1.type != T_VOID)
607
          runtime( "Setting void attribute to non-void value" );
608
        l->attrs[0].u.data = 0;
609
        break;
610
      default: bug("Unknown type in e,S");
611
      }
612

    
613
      if (!(what->aux & EAF_TEMP) && (!(f_flags & FF_FORCE_TMPATTR))) {
614
        rta_cow();
615
        l->next = f_rta_copy->eattrs;
616
        f_rta_copy->eattrs = l;
617
      } else {
618
        l->next = (*f_tmp_attrs);
619
        (*f_tmp_attrs) = l;
620
      }
621
    }
622
    break;
623
  case 'P':
624
    res.type = T_INT;
625
    res.val.i = (*f_rte)->pref;
626
    break;
627
  case P('P','S'):
628
    ONEARG;
629
    if (v1.type != T_INT)
630
      runtime( "Can't set preference to non-integer" );
631
    *f_rte = rte_cow(*f_rte);
632
    (*f_rte)->pref = v1.val.i;
633
    break;
634
  case 'L':        /* Get length of */
635
    ONEARG;
636
    res.type = T_INT;
637
    switch(v1.type) {
638
    case T_PREFIX: res.val.i = v1.val.px.len; break;
639
    case T_PATH:   res.val.i = as_path_getlen(v1.val.ad); break;
640
    default: bug( "Length of what?" );
641
    }
642
    break;
643
  case P('c','p'):        /* Convert prefix to ... */
644
    ONEARG;
645
    if (v1.type != T_PREFIX)
646
      runtime( "Prefix expected" );
647
    res.type = what->aux;
648
    switch(res.type) {
649
      /*    case T_INT:        res.val.i = v1.val.px.len; break; Not needed any more */
650
    case T_IP: res.val.px.ip = v1.val.px.ip; break;
651
    default: bug( "Unknown prefix to conversion" );
652
    }
653
    break;
654
  case 'r':
655
    ONEARG;
656
    res = v1;
657
    res.type |= T_RETURN;
658
    break;
659
  case P('c','a'): /* CALL: this is special: if T_RETURN and returning some value, mask it out  */
660
    ONEARG;
661
    res = interpret(what->a2.p);
662
    if (res.type == T_RETURN)
663
      return res;
664
    res.type &= ~T_RETURN;    
665
    break;
666
  case P('S','W'):
667
    ONEARG;
668
    {
669
      struct f_tree *t = find_tree(what->a2.p, v1);
670
      if (!t) {
671
        v1.type = T_VOID;
672
        t = find_tree(what->a2.p, v1);
673
        if (!t) {
674
          debug( "No else statement?\n");
675
          break;
676
        }
677
      }        
678
      /* It is actually possible to have t->data NULL */
679
      return interpret(t->data);
680
    }
681
    break;
682
  case P('i','M'): /* IP.MASK(val) */
683
    TWOARGS;
684
    if (v2.type != T_INT)
685
      runtime( "Integer expected");
686
    if (v1.type != T_IP)
687
      runtime( "You can mask only IP addresses" );
688
    {
689
      ip_addr mask = ipa_mkmask(v2.val.i);
690
      res.type = T_IP;
691
      res.val.px.ip = ipa_and(mask, v1.val.px.ip);
692
    }
693
    break;
694

    
695
  case 'E':        /* Create empty attribute */
696
    res.type = what->aux;
697
    res.val.ad = adata_empty(f_pool);
698
    break;
699
  case P('A','p'):        /* Path prepend */
700
    TWOARGS;
701
    if (v1.type != T_PATH)
702
      runtime("Can't prepend to non-path");
703
    if (v2.type != T_INT)
704
      runtime("Can't prepend non-integer");
705

    
706
    res.type = T_PATH;
707
    res.val.ad = as_path_prepend(f_pool, v1.val.ad, v2.val.i);
708
    break;
709

    
710
  case P('C','a'):        /* Community list add or delete */
711
    TWOARGS;
712
    if (v1.type != T_CLIST)
713
      runtime("Can't add/delete to non-clist");
714
    if (v2.type != T_PAIR)
715
      runtime("Can't add/delete non-pair");
716

    
717
    res.type = T_CLIST;
718
    switch (what->aux) {
719
    case 'a': res.val.ad = int_set_add(f_pool, v1.val.ad, v2.val.i); break;
720
    case 'd': res.val.ad = int_set_del(f_pool, v1.val.ad, v2.val.i); break;
721
    default: bug("unknown Ca operation");
722
    }
723
    break;
724

    
725
  default:
726
    bug( "Unknown instruction %d (%c)", what->code, what->code & 0xff);
727
  }
728
  if (what->next)
729
    return interpret(what->next);
730
  return res;
731
}
732

    
733
#undef ARG
734
#define ARG(x,y) \
735
        if (!i_same(f1->y, f2->y)) \
736
                return 0;
737

    
738
#define ONEARG ARG(v1, a1.p)
739
#define TWOARGS ARG(v1, a1.p) \
740
                ARG(v2, a2.p)
741

    
742
#define A2_SAME if (f1->a2.i != f2->a2.i) return 0;
743

    
744
/*
745
 * i_same - function that does real comparing of instruction trees, you should call filter_same from outside
746
 */
747
int
748
i_same(struct f_inst *f1, struct f_inst *f2)
749
{
750
  if ((!!f1) != (!!f2))
751
    return 0;
752
  if (!f1)
753
    return 1;
754
  if (f1->aux != f2->aux)
755
    return 0;
756
  if (f1->code != f2->code)
757
    return 0;
758
  if (f1 == f2)                /* It looks strange, but it is possible with call rewriting trickery */
759
    return 1;
760

    
761
  switch(f1->code) {
762
  case ',': /* fall through */
763
  case '+':
764
  case '-':
765
  case '*':
766
  case '/':
767
  case '|':
768
  case '&':
769
  case P('!','='):
770
  case P('=','='):
771
  case '<':
772
  case P('<','='): TWOARGS; break;
773

    
774
  case '!': ONEARG; break;
775
  case '~': TWOARGS; break;
776
  case P('d','e'): ONEARG; break;
777

    
778
  case 's':
779
    ARG(v2, a2.p);
780
    {
781
      struct symbol *s1, *s2;
782
      s1 = f1->a1.p;
783
      s2 = f2->a1.p;
784
      if (strcmp(s1->name, s2->name))
785
        return 0;
786
      if (s1->class != s2->class)
787
        return 0;
788
    }
789
    break;
790

    
791
  case 'c': 
792
    if (f1->aux & T_SET) {
793
      if (!same_tree(f1->a2.p, f2->a2.p))
794
        return 0;
795
      break;
796
    } 
797
    switch (f1->aux) {
798
    case T_STRING:
799
      if (strcmp(f1->a2.p, f2->a2.p))
800
        return 0;
801
      break;
802
    default:
803
      A2_SAME;
804
    }
805
    break;
806
  case 'C': 
807
    if (val_compare(* (struct f_val *) f1->a1.p, * (struct f_val *) f2->a1.p))
808
      return 0;
809
    break;
810
  case 'p': case 'L': ONEARG; break;
811
  case '?': TWOARGS; break;
812
  case '0': case 'E': break;
813
  case P('p',','): ONEARG; A2_SAME; break;
814
  case 'P':
815
  case 'a': A2_SAME; break;
816
  case P('e','a'): A2_SAME; break;
817
  case P('P','S'):
818
  case P('a','S'):
819
  case P('e','S'): ONEARG; A2_SAME; break;
820

    
821
  case 'r': ONEARG; break;
822
  case P('c','p'): ONEARG; break;
823
  case P('c','a'): /* Call rewriting trickery to avoid exponential behaviour */
824
             ONEARG; 
825
             if (!i_same(f1->a2.p, f2->a2.p))
826
               return 0; 
827
             f2->a2.p = f1->a2.p;
828
             break;
829
  case P('S','W'): ONEARG; if (!same_tree(f1->a2.p, f2->a2.p)) return 0; break;
830
  case P('i','M'): TWOARGS; break;
831
  case P('A','p'): TWOARGS; break;
832
  case P('C','a'): TWOARGS; break;
833
  default:
834
    bug( "Unknown instruction %d in same (%c)", f1->code, f1->code & 0xff);
835
  }
836
  return i_same(f1->next, f2->next);
837
}
838

    
839
/**
840
 * f_run - external entry point to filters
841
 * @filter: pointer to filter to run
842
 * @tmp_attrs: where to store newly generated temporary attributes
843
 * @rte: pointer to pointer to &rte being filtered. When route is modified, this is changed with rte_cow().
844
 * @tmp_pool: all filter allocations go from this pool
845
 * @flags: flags
846
 */
847
int
848
f_run(struct filter *filter, struct rte **rte, struct ea_list **tmp_attrs, struct linpool *tmp_pool, int flags)
849
{
850
  struct f_inst *inst;
851
  struct f_val res;
852
  DBG( "Running filter `%s'...", filter->name );
853

    
854
  f_flags = flags;
855
  f_tmp_attrs = tmp_attrs;
856
  f_rte = rte;
857
  f_rte_old = *rte;
858
  f_rta_copy = NULL;
859
  f_pool = tmp_pool;
860
  inst = filter->root;
861
  res = interpret(inst);
862
  if (res.type != T_RETURN) {
863
    log( L_ERR "Filter %s did not return accept nor reject. Make up your mind", filter->name); 
864
    return F_ERROR;
865
  }
866
  DBG( "done (%d)\n", res.val.i );
867
  return res.val.i;
868
}
869

    
870
int
871
f_eval_int(struct f_inst *expr)
872
{
873
  struct f_val res;
874

    
875
  f_flags = 0;
876
  f_tmp_attrs = NULL;
877
  f_rte = NULL;
878
  f_rte_old = NULL;
879
  f_rta_copy = NULL;
880
  f_pool = cfg_mem;
881
  res = interpret(expr);
882
  if (res.type != T_INT)
883
    cf_error("Integer expression expected");
884
  return res.val.i;
885
}
886

    
887
/**
888
 * filter_same - compare two filters
889
 * @new: first filter to be compared
890
 * @old: second filter to be compared, notice that this filter is
891
 * damaged while comparing.
892
 *
893
 * Returns 1 in case filters are same, otherwise 0. If there are
894
 * underlying bugs, it will rather say 0 on same filters than say
895
 * 1 on different.
896
 */
897
int
898
filter_same(struct filter *new, struct filter *old)
899
{
900
  if (old == new)        /* Handle FILTER_ACCEPT and FILTER_REJECT */
901
    return 1;
902
  if (old == FILTER_ACCEPT || old == FILTER_REJECT ||
903
      new == FILTER_ACCEPT || new == FILTER_REJECT)
904
    return 0;
905
  return i_same(new->root, old->root);
906
}