filter.c 25.1 KB
Newer Older
1
2
3
4
5
6
/*
 *	Filters: utility functions
 *
 *	Copyright 1998 Pavel Machek <pavel@ucw.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
7
 *
8
9
 */

10
11
12
/**
 * DOC: Filters
 *
13
14
15
16
 * You can find sources of the filter language in |filter/|
 * directory. File |filter/config.Y| contains filter grammar and basically translates
 * the source from user into a tree of &f_inst structures. These trees are
 * later interpreted using code in |filter/filter.c|.
17
 *
18
19
20
21
22
 * A filter is represented by a tree of &f_inst structures, one structure per
 * "instruction". Each &f_inst contains @code, @aux value which is
 * usually the data type this instruction operates on and two generic
 * arguments (@a1, @a2). Some instructions contain pointer(s) to other
 * instructions in their (@a1, @a2) fields.
23
 *
24
25
26
27
28
29
 * Filters use a &f_val structure for their data. Each &f_val
 * contains type and value (types are constants prefixed with %T_). Few
 * of the types are special; %T_RETURN can be or-ed with a type to indicate
 * that return from a function or from the whole filter should be
 * forced. Important thing about &f_val's is that they may be copied
 * 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
32
 * operation (okay too).
 */
33

34
#undef LOCAL_DEBUG
35

36
37
38
39
#include "nest/bird.h"
#include "lib/lists.h"
#include "lib/resource.h"
#include "lib/socket.h"
40
#include "lib/string.h"
41
#include "lib/unaligned.h"
42
43
44
#include "nest/route.h"
#include "nest/protocol.h"
#include "nest/iface.h"
45
#include "nest/attrs.h"
46
47
48
#include "conf/conf.h"
#include "filter/filter.h"

49
50
#define P(a,b) ((a<<8) | b)

51
52
#define CMP_ERROR 999

53
static struct adata *
Pavel Machek's avatar
Pavel Machek committed
54
55
56
57
58
59
60
adata_empty(struct linpool *pool)
{
  struct adata *res = lp_alloc(pool, sizeof(struct adata));
  res->length = 0;
  return res;
}

Pavel Machek's avatar
Pavel Machek committed
61
static int
62
63
64
65
66
pm_path_compare(struct f_path_mask *m1, struct f_path_mask *m2)
{
  while (1) {
    if ((!m1) || (!m2))
      return !((!m1) && (!m2));
67
68

    if ((m1->kind != m2->kind) || (m1->val != m2->val)) return 1;
69
70
71
72
73
    m1 = m1->next;
    m2 = m2->next;
  }
}

74
75
u32 f_eval_asn(struct f_inst *expr);

76
77
78
79
80
81
82
83
84
85
86
87
88
static void
pm_format(struct f_path_mask *p, byte *buf, unsigned int size)
{
  byte *end = buf + size - 16;

  while (p)
    {
      if (buf > end)
	{
	  strcpy(buf, " ...");
	  return;
	}

89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
      switch(p->kind)
	{
	case PM_ASN:
	  buf += bsprintf(buf, " %u", p->val);
	  break;

	case PM_QUESTION:
	  buf += bsprintf(buf, " ?");
	  break;

	case PM_ASTERISK:
	  buf += bsprintf(buf, " *");
	  break;

	case PM_ASN_EXPR:
	  buf += bsprintf(buf, " %u", f_eval_asn((struct f_inst *) p->val));
	  break;
	}
107
108
109
110
111
112
113

      p = p->next;
    }

  *buf = 0;
}

114
/**
Pavel Machek's avatar
Pavel Machek committed
115
 * val_compare - compare two values
116
117
118
119
120
121
 * @v1: first value
 * @v2: second value
 *
 * Compares two values and returns -1, 0, 1 on <, =, > or 999 on error.
 * Tree module relies on this giving consistent results so that it can
 * build balanced trees.
122
 */
123
124
125
int
val_compare(struct f_val v1, struct f_val v2)
{
126
127
  int rc;

Pavel Machek's avatar
Pavel Machek committed
128
129
130
131
132
133
134
  if ((v1.type == T_VOID) && (v2.type == T_VOID))
    return 0;
  if (v1.type == T_VOID)	/* Hack for else */
    return -1;
  if (v2.type == T_VOID)
    return 1;

135
136
  if (v1.type != v2.type) {
    debug( "Types do not match in val_compare\n" );
137
    return CMP_ERROR;
138
  }
139
  switch (v1.type) {
140
  case T_ENUM:
141
142
  case T_INT:
  case T_BOOL:
143
  case T_PAIR:
144
145
146
    if (v1.val.i == v2.val.i) return 0;
    if (v1.val.i < v2.val.i) return -1;
    return 1;
147
  case T_IP:
148
    return ipa_compare(v1.val.px.ip, v2.val.px.ip);
149
150
151
152
153
154
155
156
  case T_PREFIX:
    if (rc = ipa_compare(v1.val.px.ip, v2.val.px.ip))
      return rc;
    if (v1.val.px.len < v2.val.px.len)
      return -1;
    if (v1.val.px.len > v2.val.px.len)
      return 1;
    return 0;
157
158
  case T_PATH_MASK:
    return pm_path_compare(v1.val.path_mask, v2.val.path_mask);
159
160
  case T_STRING:
    return strcmp(v1.val.s, v2.val.s);
161
  default:
Ondrej Filip's avatar
Ondrej Filip committed
162
    debug( "Compare of unknown entities: %x\n", v1.type );
163
    return CMP_ERROR;
164
165
166
  }
}

167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185

void
f_prefix_get_bounds(struct f_prefix *px, int *l, int *h)
{
  *l = *h = px->len & LEN_MASK;

  if (px->len & LEN_MINUS)
    *l = 0;

  else if (px->len & LEN_PLUS)
    *h = MAX_PREFIX_LENGTH;

  else if (px->len & LEN_RANGE)
    {
      *l = 0xff & (px->len >> 16);
      *h = 0xff & (px->len >> 8);
    }
}

186
/*
187
188
 * val_simple_in_range - check if @v1 ~ @v2 for everything except sets
 */ 
189
static int
190
191
val_simple_in_range(struct f_val v1, struct f_val v2)
{
192
  if ((v1.type == T_PATH) && (v2.type == T_PATH_MASK))
Pavel Machek's avatar
Pavel Machek committed
193
    return as_path_match(v1.val.ad, v2.val.path_mask);
194
195
  if ((v1.type == T_PAIR) && (v2.type == T_CLIST))
    return int_set_contains(v2.val.ad, v1.val.i);
196
197
  if ((v1.type == T_STRING) && (v2.type == T_STRING))
    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
203
  if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX))
    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
206
207
  return CMP_ERROR;
}

208
/**
Pavel Machek's avatar
Pavel Machek committed
209
 * val_in_range - implement |~| operator
210
211
212
213
 * @v1: element
 * @v2: set
 *
 * Checks if @v1 is element (|~| operator) of @v2. Sets are internally represented as balanced trees, see
Pavel Machek's avatar
Pavel Machek committed
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
218
val_in_range(struct f_val v1, struct f_val v2)
{
219
220
221
222
223
224
  int res;

  res = val_simple_in_range(v1, v2);

  if (res != CMP_ERROR)
    return res;
Pavel Machek's avatar
Pavel Machek committed
225
  
226
227
228
  if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX_SET))
    return trie_match_prefix(v2.val.ti, &v1.val.px);

Pavel Machek's avatar
Pavel Machek committed
229
230
231
232
233
234
235
236
237
238
239
240
241
242
  if (v2.type == T_SET)
    switch (v1.type) {
    case T_ENUM:
    case T_INT:
    case T_IP:
    case T_PREFIX:
      {
	struct f_tree *n;
	n = find_tree(v2.val.t, v1);
	if (!n)
	  return 0;
	return !! (val_simple_in_range(v1, n->from));	/* We turn CMP_ERROR into compared ok, and that's fine */
      }
    }
243
244
245
  return CMP_ERROR;
}

246
247
248
249
static void
tree_print(struct f_tree *t)
{
  if (!t) {
250
    debug( "() " );
251
252
    return;
  }
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
262
 * val_print - format filter value
 */
263
264
265
266
void
val_print(struct f_val v)
{
  char buf[2048];
267
  char buf2[1024];
268
269
270
271
272
273
274
#define PRINTF(a...) bsnprintf( buf, 2040, a )
  buf[0] = 0;
  switch (v.type) {
  case T_VOID: PRINTF( "(void)" ); break;
  case T_BOOL: PRINTF( v.val.i ? "TRUE" : "FALSE" ); break;
  case T_INT: PRINTF( "%d ", v.val.i ); break;
  case T_STRING: PRINTF( "%s", v.val.s ); break;
275
  case T_IP: PRINTF( "%I", v.val.px.ip ); break;
276
277
  case T_PREFIX: PRINTF( "%I/%d", v.val.px.ip, v.val.px.len ); break;
  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;
Pavel Machek's avatar
Pavel Machek committed
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;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
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;
Pavel Machek's avatar
Pavel Machek committed
292
static struct ea_list **f_tmp_attrs;
293
static int f_flags;
294
static rta *f_rta_copy;
295

296
/*
297
298
 * rta_cow - prepare rta for modification by filter
 */
299
static void
300
301
302
303
304
305
306
rta_cow(void)
{
  if (!f_rta_copy) {
    f_rta_copy = lp_alloc(f_pool, sizeof(rta));
    memcpy(f_rta_copy, (*f_rte)->attrs, sizeof(rta));
    f_rta_copy->aflags = 0;
    *f_rte = rte_cow(*f_rte);
307
    rta_free((*f_rte)->attrs);
308
309
310
311
    (*f_rte)->attrs = f_rta_copy;
  }
}

312
313
static struct rate_limit rl_runtime_err;

314
#define runtime(x) do { \
315
    log_rl(&rl_runtime_err, L_ERR "filters, line %d: %s", what->lineno, x); \
316
317
318
319
320
321
322
    res.type = T_RETURN; \
    res.val.i = F_ERROR; \
    return res; \
  } while(0)

#define ARG(x,y) \
	x = interpret(what->y); \
323
	if (x.type & T_RETURN) \
324
325
326
327
328
329
330
		return x;

#define ONEARG ARG(v1, a1.p)
#define TWOARGS ARG(v1, a1.p) \
		ARG(v2, a2.p)
#define TWOARGS_C TWOARGS \
                  if (v1.type != v2.type) \
Pavel Machek's avatar
Pavel Machek committed
331
		    runtime( "Can't operate with values of incompatible types" );
332

333
334
/**
 * interpret
Martin Mareš's avatar
Martin Mareš committed
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.
Pavel Machek's avatar
Pavel Machek committed
339
340
341
342
343
344
345
346
347
348
 *
 * Each instruction has 4 fields: code (which is instruction code),
 * aux (which is extension to instruction code, typically type),
 * arg1 and arg2 - arguments. Depending on instruction, arguments
 * are either integers, or pointers to instruction trees. Common 
 * instructions like +, that have two expressions as arguments use
 * TWOARGS macro to get both of them evaluated.
 *
 * &f_val structures are copied around, so there are no problems with
 * memory managment.
349
 */
350
351
352
353
354
static struct f_val
interpret(struct f_inst *what)
{
  struct symbol *sym;
  struct f_val v1, v2, res;
355
  unsigned u1, u2;
356
  int i;
357
358
359
360
361
362
363
364
365
366
367
368
369
370

  res.type = T_VOID;
  if (!what)
    return res;

  switch(what->code) {
  case ',':
    TWOARGS;
    break;

/* Binary operators */
  case '+':
    TWOARGS_C;
    switch (res.type = v1.type) {
Pavel Machek's avatar
Pavel Machek committed
371
    case T_VOID: runtime( "Can't operate with values of type void" );
372
373
374
375
    case T_INT: res.val.i = v1.val.i + v2.val.i; break;
    default: runtime( "Usage of unknown type" );
    }
    break;
376
377
378
  case '-':
    TWOARGS_C;
    switch (res.type = v1.type) {
Pavel Machek's avatar
Pavel Machek committed
379
    case T_VOID: runtime( "Can't operate with values of type void" );
380
381
382
383
384
385
386
    case T_INT: res.val.i = v1.val.i - v2.val.i; break;
    default: runtime( "Usage of unknown type" );
    }
    break;
  case '*':
    TWOARGS_C;
    switch (res.type = v1.type) {
Pavel Machek's avatar
Pavel Machek committed
387
    case T_VOID: runtime( "Can't operate with values of type void" );
388
389
390
391
    case T_INT: res.val.i = v1.val.i * v2.val.i; break;
    default: runtime( "Usage of unknown type" );
    }
    break;
392
393
394
  case '/':
    TWOARGS_C;
    switch (res.type = v1.type) {
Pavel Machek's avatar
Pavel Machek committed
395
    case T_VOID: runtime( "Can't operate with values of type void" );
Pavel Machek's avatar
Pavel Machek committed
396
397
    case T_INT: if (v2.val.i == 0) runtime( "Mother told me not to divide by 0" );
      	        res.val.i = v1.val.i / v2.val.i; break;
398
    case T_IP: if (v2.type != T_INT)
Pavel Machek's avatar
Pavel Machek committed
399
                 runtime( "Incompatible types in / operator" );
400
401
402
403
               break;
    default: runtime( "Usage of unknown type" );
    }
    break;
Pavel Machek's avatar
Pavel Machek committed
404
405
406
407
    
  case '&':
    TWOARGS_C;
    res.type = v1.type;
Pavel Machek's avatar
Pavel Machek committed
408
    if (res.type != T_BOOL) runtime( "Can't do boolean operation on non-booleans" );
Pavel Machek's avatar
Pavel Machek committed
409
410
411
412
413
    res.val.i = v1.val.i && v2.val.i;
    break;
  case '|':
    TWOARGS_C;
    res.type = v1.type;
Pavel Machek's avatar
Pavel Machek committed
414
    if (res.type != T_BOOL) runtime( "Can't do boolean operation on non-booleans" );
Pavel Machek's avatar
Pavel Machek committed
415
416
    res.val.i = v1.val.i || v2.val.i;
    break;
417

418
419
420
421
422
423
424
425
426
427
428
429
  case P('m','p'):
    TWOARGS_C;
    if ((v1.type != T_INT) || (v2.type != T_INT))
      runtime( "Can't operate with value of non-integer type in pair constructor" );
    u1 = v1.val.i;
    u2 = v2.val.i;
    if ((u1 > 0xFFFF) || (u2 > 0xFFFF))
      runtime( "Can't operate with value out of bounds in pair constructor" );
    res.val.i = (u1 << 16) | u2;
    res.type = T_PAIR;
    break;

430
/* Relational operators */
431
432
433
434
435
436

#define COMPARE(x) \
    TWOARGS_C; \
    res.type = T_BOOL; \
    i = val_compare(v1, v2); \
    if (i==CMP_ERROR) \
Pavel Machek's avatar
Pavel Machek committed
437
      runtime( "Error in comparison" ); \
438
    res.val.i = (x); \
439
    break;
440

441
442
  case P('!','='): COMPARE(i!=0);
  case P('=','='): COMPARE(i==0);
443
  case '<': COMPARE(i==-1);
444
  case P('<','='): COMPARE(i!=1);
445

Pavel Machek's avatar
Pavel Machek committed
446
447
448
  case '!':
    ONEARG;
    if (v1.type != T_BOOL)
Pavel Machek's avatar
Pavel Machek committed
449
      runtime( "Not applied to non-boolean" );
Pavel Machek's avatar
Pavel Machek committed
450
451
452
453
    res = v1;
    res.val.i = !res.val.i;
    break;

454
455
  case '~':
    TWOARGS;
456
    res.type = T_BOOL;
457
458
459
    res.val.i = val_in_range(v1, v2);
    if (res.val.i == CMP_ERROR)
      runtime( "~ applied on unknown type pair" );
460
    break;
461
  case P('d','e'):
462
463
464
465
    ONEARG;
    res.type = T_BOOL;
    res.val.i = (v1.type != T_VOID);
    break;
466

467
  /* Set to indirect value, a1 = variable, a2 = value */
468
  case 's':
Pavel Machek's avatar
Pavel Machek committed
469
470
    ARG(v2, a2.p);
    sym = what->a1.p;
471
    switch (res.type = v2.type) {
Pavel Machek's avatar
Pavel Machek committed
472
    case T_VOID: runtime( "Can't assign void values" );
473
    case T_ENUM:
474
475
476
477
478
479
480
481
    case T_BOOL:
    case T_INT:
    case T_PAIR:
    case T_STRING:
    case T_IP:
    case T_PREFIX:
    case T_PREFIX_SET:
    case T_SET:
482
    case T_PATH:
483
    case T_PATH_MASK:
484
    case T_CLIST:
485
      if (sym->class != (SYM_VARIABLE | v2.type))
Pavel Machek's avatar
Pavel Machek committed
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
493
    }
    break;

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
499
500
    if (res.type == T_PREFIX_SET)
      res.val.ti = what->a2.p;
    else if (res.type == T_SET)
501
502
503
504
505
      res.val.t = what->a2.p;
    else if (res.type == T_STRING)
      res.val.s = what->a2.p;
    else
      res.val.i = what->a2.i;
506
    break;
507
  case 'V':
508
509
510
  case 'C':
    res = * ((struct f_val *) what->a1.p);
    break;
511
512
  case 'p':
    ONEARG;
513
    val_print(v1);
514
515
516
517
    break;
  case '?':	/* ? has really strange error value, so we can implement if ... else nicely :-) */
    ONEARG;
    if (v1.type != T_BOOL)
Pavel Machek's avatar
Pavel Machek committed
518
      runtime( "If requires boolean expression" );
519
    if (v1.val.i) {
Pavel Machek's avatar
Pavel Machek committed
520
      ARG(res,a2.p);
521
522
523
524
525
      res.val.i = 0;
    } else res.val.i = 1;
    res.type = T_BOOL;
    break;
  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

Pavel Machek's avatar
Pavel Machek committed
533
    switch (what->a2.i) {
534
535
536
537
538
    case F_QUITBIRD:
      die( "Filter asked me to die" );
    case F_ACCEPT:
      /* Should take care about turning ACCEPT into MODIFY */
    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
545
546
    case F_NOP:
      break;
    default:
Pavel Machek's avatar
Pavel Machek committed
547
      bug( "unknown return type: Can't happen");
548
549
    }
    break;
550
551
552
  case 'a':	/* rta access */
    {
      struct rta *rta = (*f_rte)->attrs;
553
      res.type = what->aux;
554
555
      switch(res.type) {
      case T_IP:
556
	res.val.px.ip = * (ip_addr *) ((char *) rta + what->a2.i);
557
	break;
558
559
560
      case T_ENUM:
	res.val.i = * ((char *) rta + what->a2.i);
	break;
561
562
563
      case T_STRING:	/* Warning: this is a special case for proto attribute */
	res.val.s = rta->proto->name;
	break;
564
565
566
567
568
569
570
      case T_PREFIX:	/* Warning: this works only for prefix of network */
	{
	  res.val.px.ip = (*f_rte)->net->n.prefix;
	  res.val.px.len = (*f_rte)->net->n.pxlen;
	  break;
	}
      default:
571
	bug( "Invalid type for rta access (%x)", res.type );
572
573
574
      }
    }
    break;
575
576
577
  case P('a','S'):
    ONEARG;
    if (what->aux != v1.type)
Pavel Machek's avatar
Pavel Machek committed
578
      runtime( "Attempt to set static attribute to incompatible type" );
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
    rta_cow();
    {
      struct rta *rta = (*f_rte)->attrs;
      switch (what->aux) {
      case T_ENUM:
	* ((char *) rta + what->a2.i) = v1.val.i;
	break;
      case T_IP:
	* (ip_addr *) ((char *) rta + what->a2.i) = v1.val.px.ip;
	break;
      default:
	bug( "Unknown type in set of static attribute" );
      }
    }
    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 );
Pavel Machek's avatar
Pavel Machek committed
599
600
      if (!e) 
	e = ea_find( (*f_tmp_attrs), what->a2.i );
601
      if ((!e) && (f_flags & FF_FORCE_TMPATTR))
602
603
	e = ea_find( (*f_rte)->attrs->eattrs, what->a2.i );
      
604
605
      switch (what->aux & EAF_TYPE_MASK) {
      case EAF_TYPE_INT:
606
607
608
609
	if (!e) {
	  res.type = T_VOID;
	  break;
	}
610
	res.type = T_INT;
611
612
	res.val.i = e->u.data;
	break;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
613
614
615
616
617
618
619
620
621
      case EAF_TYPE_IP_ADDRESS:
	if (!e) {
	  res.type = T_VOID;
	  break;
	}
	res.type = T_IP;
	struct adata * ad = e->u.ptr;
	res.val.px.ip = * (ip_addr *) ad->data;
	break;
622
      case EAF_TYPE_AS_PATH:
623
624
625
626
	if (!e) {
	  res.type = T_VOID;
	  break;
	}
627
628
629
630
        res.type = T_PATH;
	res.val.ad = e->u.ptr;
	break;
      case EAF_TYPE_INT_SET:
631
632
633
634
635
	if (!e) {
	  res.type = T_CLIST;
	  res.val.ad = adata_empty(f_pool);
	  break;
	}
636
	res.type = T_CLIST;
637
638
	res.val.ad = e->u.ptr;
	break;
Martin Mareš's avatar
Martin Mareš committed
639
      default:
Pavel Machek's avatar
Pavel Machek committed
640
	bug("Unknown type in e,a");
641
642
      }
    }
643
    break;
644
  case P('e','S'):
645
646
647
648
649
650
651
652
    ONEARG;
    {
      struct ea_list *l = lp_alloc(f_pool, sizeof(struct ea_list) + sizeof(eattr));

      l->next = NULL;
      l->flags = EALF_SORTED;
      l->count = 1;
      l->attrs[0].id = what->a2.i;
Pavel Machek's avatar
Pavel Machek committed
653
654
      l->attrs[0].flags = 0;
      l->attrs[0].type = what->aux | EAF_ORIGINATED;
Pavel Machek's avatar
Pavel Machek committed
655
656
657
658
      switch (what->aux & EAF_TYPE_MASK) {
      case EAF_TYPE_INT:
	if (v1.type != T_INT)
	  runtime( "Setting int attribute to non-int value" );
659
660
	l->attrs[0].u.data = v1.val.i;
	break;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
661
662
663
664
665
666
667
668
      case EAF_TYPE_IP_ADDRESS:
	if (v1.type != T_IP)
	  runtime( "Setting ip attribute to non-ip value" );
	int len = sizeof(ip_addr);
	struct adata *ad = lp_alloc(f_pool, sizeof(struct adata) + len);
	ad->length = len;
	(* (ip_addr *) ad->data) = v1.val.px.ip;
	break;
669
670
671
672
673
      case EAF_TYPE_AS_PATH:
	if (v1.type != T_PATH)
	  runtime( "Setting path attribute to non-path value" );
	l->attrs[0].u.ptr = v1.val.ad;
	break;
674
675
      case EAF_TYPE_INT_SET:
	if (v1.type != T_CLIST)
Pavel Machek's avatar
Pavel Machek committed
676
	  runtime( "Setting int set attribute to non-clist value" );
677
678
	l->attrs[0].u.ptr = v1.val.ad;
	break;
Pavel Machek's avatar
Pavel Machek committed
679
680
681
      case EAF_TYPE_UNDEF:
	if (v1.type != T_VOID)
	  runtime( "Setting void attribute to non-void value" );
682
683
	l->attrs[0].u.data = 0;
	break;
684
      default: bug("Unknown type in e,S");
685
      }
Pavel Machek's avatar
Pavel Machek committed
686

687
      if (!(what->aux & EAF_TEMP) && (!(f_flags & FF_FORCE_TMPATTR))) {
688
	rta_cow();
689
690
	l->next = f_rta_copy->eattrs;
	f_rta_copy->eattrs = l;
Pavel Machek's avatar
Pavel Machek committed
691
692
693
694
      } else {
	l->next = (*f_tmp_attrs);
	(*f_tmp_attrs) = l;
      }
695
696
    }
    break;
697
698
699
700
701
702
703
  case 'P':
    res.type = T_INT;
    res.val.i = (*f_rte)->pref;
    break;
  case P('P','S'):
    ONEARG;
    if (v1.type != T_INT)
Pavel Machek's avatar
Pavel Machek committed
704
      runtime( "Can't set preference to non-integer" );
Ondřej Zajíček's avatar
Ondřej Zajíček committed
705
706
    if ((v1.val.i < 0) || (v1.val.i > 0xFFFF))
      runtime( "Setting preference value out of bounds" );
707
708
709
    *f_rte = rte_cow(*f_rte);
    (*f_rte)->pref = v1.val.i;
    break;
710
711
712
713
714
715
  case 'L':	/* Get length of */
    ONEARG;
    res.type = T_INT;
    switch(v1.type) {
    case T_PREFIX: res.val.i = v1.val.px.len; break;
    case T_PATH:   res.val.i = as_path_getlen(v1.val.ad); break;
716
    default: runtime( "Prefix or path expected" );
717
718
    }
    break;
719
  case P('c','p'):	/* Convert prefix to ... */
720
721
    ONEARG;
    if (v1.type != T_PREFIX)
Pavel Machek's avatar
Pavel Machek committed
722
      runtime( "Prefix expected" );
723
    res.type = what->aux;
724
    switch(res.type) {
725
      /*    case T_INT:	res.val.i = v1.val.px.len; break; Not needed any more */
726
    case T_IP: res.val.px.ip = v1.val.px.ip; break;
727
    default: bug( "Unknown prefix to conversion" );
728
729
    }
    break;
730
731
732
733
  case 'r':
    ONEARG;
    res = v1;
    res.type |= T_RETURN;
734
    return res;
735
  case P('c','a'): /* CALL: this is special: if T_RETURN and returning some value, mask it out  */
736
737
    ONEARG;
    res = interpret(what->a2.p);
738
739
740
    if (res.type == T_RETURN)
      return res;
    res.type &= ~T_RETURN;    
741
    break;
742
  case P('S','W'):
743
    ONEARG;
Pavel Machek's avatar
Pavel Machek committed
744
745
746
747
748
749
    {
      struct f_tree *t = find_tree(what->a2.p, v1);
      if (!t) {
	v1.type = T_VOID;
	t = find_tree(what->a2.p, v1);
	if (!t) {
Pavel Machek's avatar
Pavel Machek committed
750
	  debug( "No else statement?\n");
Pavel Machek's avatar
Pavel Machek committed
751
752
753
	  break;
	}
      }	
Pavel Machek's avatar
Allow    
Pavel Machek committed
754
      /* It is actually possible to have t->data NULL */
755
756
757
758

      res = interpret(t->data);
      if (res.type & T_RETURN)
	return res;
Pavel Machek's avatar
Pavel Machek committed
759
    }
760
    break;
761
  case P('i','M'): /* IP.MASK(val) */
762
763
    TWOARGS;
    if (v2.type != T_INT)
Pavel Machek's avatar
Pavel Machek committed
764
      runtime( "Integer expected");
765
    if (v1.type != T_IP)
Pavel Machek's avatar
Pavel Machek committed
766
      runtime( "You can mask only IP addresses" );
767
768
769
770
771
    {
      ip_addr mask = ipa_mkmask(v2.val.i);
      res.type = T_IP;
      res.val.px.ip = ipa_and(mask, v1.val.px.ip);
    }
772
    break;
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788

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

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

789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
  case P('C','a'):	/* Community list add or delete */
    TWOARGS;
    if (v1.type != T_CLIST)
      runtime("Can't add/delete to non-clist");
    if (v2.type != T_PAIR)
      runtime("Can't add/delete non-pair");

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

804
805
806
807
808
809
810
811
  default:
    bug( "Unknown instruction %d (%c)", what->code, what->code & 0xff);
  }
  if (what->next)
    return interpret(what->next);
  return res;
}

812
#undef ARG
813
814
815
816
817
818
819
820
821
822
#define ARG(x,y) \
	if (!i_same(f1->y, f2->y)) \
		return 0;

#define ONEARG ARG(v1, a1.p)
#define TWOARGS ARG(v1, a1.p) \
		ARG(v2, a2.p)

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

823
/*
824
825
 * i_same - function that does real comparing of instruction trees, you should call filter_same from outside
 */
826
827
828
829
830
int
i_same(struct f_inst *f1, struct f_inst *f2)
{
  if ((!!f1) != (!!f2))
    return 0;
831
832
  if (!f1)
    return 1;
833
834
835
836
  if (f1->aux != f2->aux)
    return 0;
  if (f1->code != f2->code)
    return 0;
837
838
  if (f1 == f2)		/* It looks strange, but it is possible with call rewriting trickery */
    return 1;
839
840
841
842

  switch(f1->code) {
  case ',': /* fall through */
  case '+':
843
844
  case '-':
  case '*':
845
  case '/':
Pavel Machek's avatar
Pavel Machek committed
846
847
  case '|':
  case '&':
848
  case P('m','p'):
849
850
  case P('!','='):
  case P('=','='):
851
  case '<':
852
  case P('<','='): TWOARGS; break;
853

Pavel Machek's avatar
Pavel Machek committed
854
  case '!': ONEARG; break;
855
  case '~': TWOARGS; break;
856
  case P('d','e'): ONEARG; break;
857
858
859
860
861
862
863
864
865
866
867
868
869
870

  case 's':
    ARG(v2, a2.p);
    {
      struct symbol *s1, *s2;
      s1 = f1->a1.p;
      s2 = f2->a1.p;
      if (strcmp(s1->name, s2->name))
	return 0;
      if (s1->class != s2->class)
	return 0;
    }
    break;

Pavel Machek's avatar
Pavel Machek committed
871
  case 'c': 
872
873
874
875
876
    switch (f1->aux) {

    case T_PREFIX_SET:
      if (!trie_same(f1->a2.p, f2->a2.p))
	return 0;
877
      break;
878
879

    case T_SET:
Pavel Machek's avatar
Pavel Machek committed
880
881
      if (!same_tree(f1->a2.p, f2->a2.p))
	return 0;
882
      break;
883

Pavel Machek's avatar
Pavel Machek committed
884
885
886
887
    case T_STRING:
      if (strcmp(f1->a2.p, f2->a2.p))
	return 0;
      break;
888

Pavel Machek's avatar
Pavel Machek committed
889
890
891
892
    default:
      A2_SAME;
    }
    break;
893
  case 'C': 
894
    if (val_compare(* (struct f_val *) f1->a1.p, * (struct f_val *) f2->a1.p))
895
896
      return 0;
    break;
897
898
899
900
  case 'V': 
    if (strcmp((char *) f1->a2.p, (char *) f2->a2.p))
      return 0;
    break;
901
  case 'p': case 'L': ONEARG; break;
902
  case '?': TWOARGS; break;
903
  case '0': case 'E': break;
904
  case P('p',','): ONEARG; A2_SAME; break;
905
  case 'P':
906
  case 'a': A2_SAME; break;
907
  case P('e','a'): A2_SAME; break;
908
909
  case P('P','S'):
  case P('a','S'):
910
  case P('e','S'): ONEARG; A2_SAME; break;
911

912
913
  case 'r': ONEARG; break;
  case P('c','p'): ONEARG; break;
914
915
916
917
918
919
  case P('c','a'): /* Call rewriting trickery to avoid exponential behaviour */
             ONEARG; 
	     if (!i_same(f1->a2.p, f2->a2.p))
	       return 0; 
	     f2->a2.p = f1->a2.p;
	     break;
920
921
  case P('S','W'): ONEARG; if (!same_tree(f1->a2.p, f2->a2.p)) return 0; break;
  case P('i','M'): TWOARGS; break;
922
  case P('A','p'): TWOARGS; break;
923
  case P('C','a'): TWOARGS; break;
924
925
926
927
928
929
  default:
    bug( "Unknown instruction %d in same (%c)", f1->code, f1->code & 0xff);
  }
  return i_same(f1->next, f2->next);
}

930
931
932
/**
 * f_run - external entry point to filters
 * @filter: pointer to filter to run
933
 * @tmp_attrs: where to store newly generated temporary attributes
Martin Mareš's avatar
Martin Mareš committed
934
 * @rte: pointer to pointer to &rte being filtered. When route is modified, this is changed with rte_cow().
935
 * @tmp_pool: all filter allocations go from this pool
936
 * @flags: flags
937
 */
938
int
939
f_run(struct filter *filter, struct rte **rte, struct ea_list **tmp_attrs, struct linpool *tmp_pool, int flags)
940
941
942
{
  struct f_inst *inst;
  struct f_val res;
943
  DBG( "Running filter `%s'...", filter->name );
944

945
  f_flags = flags;
Pavel Machek's avatar
Pavel Machek committed
946
  f_tmp_attrs = tmp_attrs;
947
  f_rte = rte;
948
  f_rte_old = *rte;
949
  f_rta_copy = NULL;
950
  f_pool = tmp_pool;
951
952
  inst = filter->root;
  res = interpret(inst);
953
954
  if (res.type != T_RETURN) {
    log( L_ERR "Filter %s did not return accept nor reject. Make up your mind", filter->name); 
955
    return F_ERROR;
956
  }
957
  DBG( "done (%d)\n", res.val.i );
958
959
960
  return res.val.i;
}

961
962
int
f_eval_int(struct f_inst *expr)
963
964
965
{
  struct f_val res;

966
967
968
969
970
971
972
973
974
975
976
  f_flags = 0;
  f_tmp_attrs = NULL;
  f_rte = NULL;
  f_rte_old = NULL;
  f_rta_copy = NULL;
  f_pool = cfg_mem;
  res = interpret(expr);
  if (res.type != T_INT)
    cf_error("Integer expression expected");
  return res.val.i;
}
977

978
979
980
981
982
983
984
985
986
987
u32
f_eval_asn(struct f_inst *expr)
{
  struct f_val res = interpret(expr);
  if (res.type != T_INT)
    cf_error("Can't operate with value of non-integer type in AS path mask constructor");
 
  return res.val.i;
}

988
989
990
991
992
993
994
995
996
997
/**
 * filter_same - compare two filters
 * @new: first filter to be compared
 * @old: second filter to be compared, notice that this filter is
 * damaged while comparing.
 *
 * Returns 1 in case filters are same, otherwise 0. If there are
 * underlying bugs, it will rather say 0 on same filters than say
 * 1 on different.
 */
998
999
1000
int
filter_same(struct filter *new, struct filter *old)
{
1001
1002
1003
1004
1005
  if (old == new)	/* Handle FILTER_ACCEPT and FILTER_REJECT */
    return 1;
  if (old == FILTER_ACCEPT || old == FILTER_REJECT ||
      new == FILTER_ACCEPT || new == FILTER_REJECT)
    return 0;
1006
  return i_same(new->root, old->root);
1007
}