Statistics
| Branch: | Revision:

iof-bird-daemon / filter / filter.c @ 42a0c054

History | View | Annotate | Download (33.2 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, int l)
55
{
56
  struct adata *res = lp_alloc(pool, sizeof(struct adata) + l);
57
  res->length = l;
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
    /* FIXME: buggy, should return -1, 0, 1; but it doesn't matter */
69
    if ((m1->kind != m2->kind) || (m1->val != m2->val)) return 1;
70
    m1 = m1->next;
71
    m2 = m2->next;
72
  }
73
}
74

    
75
u32 f_eval_asn(struct f_inst *expr);
76

    
77
static void
78
pm_format(struct f_path_mask *p, byte *buf, unsigned int size)
79
{
80
  byte *end = buf + size - 16;
81

    
82
  while (p)
83
    {
84
      if (buf > end)
85
        {
86
          strcpy(buf, " ...");
87
          return;
88
        }
89

    
90
      switch(p->kind)
91
        {
92
        case PM_ASN:
93
          buf += bsprintf(buf, " %u", p->val);
94
          break;
95

    
96
        case PM_QUESTION:
97
          buf += bsprintf(buf, " ?");
98
          break;
99

    
100
        case PM_ASTERISK:
101
          buf += bsprintf(buf, " *");
102
          break;
103

    
104
        case PM_ASN_EXPR:
105
          buf += bsprintf(buf, " %u", f_eval_asn((struct f_inst *) p->val));
106
          break;
107
        }
108

    
109
      p = p->next;
110
    }
111

    
112
  *buf = 0;
113
}
114

    
115
static inline int int_cmp(int i1, int i2)
116
{
117
  if (i1 == i2) return 0;
118
  if (i1 < i2) return -1;
119
  else return 1;
120
}
121

    
122
static inline int uint_cmp(unsigned int i1, unsigned int i2)
123
{
124
  if (i1 == i2) return 0;
125
  if (i1 < i2) return -1;
126
  else return 1;
127
}
128

    
129
static inline int u64_cmp(u64 i1, u64 i2)
130
{
131
  if (i1 == i2) return 0;
132
  if (i1 < i2) return -1;
133
  else return 1;
134
}
135

    
136
/**
137
 * val_compare - compare two values
138
 * @v1: first value
139
 * @v2: second value
140
 *
141
 * Compares two values and returns -1, 0, 1 on <, =, > or 999 on error.
142
 * Tree module relies on this giving consistent results so that it can
143
 * build balanced trees.
144
 */
145
int
146
val_compare(struct f_val v1, struct f_val v2)
147
{
148
  int rc;
149

    
150
  if ((v1.type == T_VOID) && (v2.type == T_VOID))
151
    return 0;
152
  if (v1.type == T_VOID)        /* Hack for else */
153
    return -1;
154
  if (v2.type == T_VOID)
155
    return 1;
156

    
157
  if (v1.type != v2.type) {
158
#ifndef IPV6
159
    /* IP->Quad implicit conversion */
160
    if ((v1.type == T_QUAD) && (v2.type == T_IP))
161
      return uint_cmp(v1.val.i, ipa_to_u32(v2.val.px.ip));
162
    if ((v1.type == T_IP) && (v2.type == T_QUAD))
163
      return uint_cmp(ipa_to_u32(v1.val.px.ip), v2.val.i);
164
#endif
165

    
166
    debug( "Types do not match in val_compare\n" );
167
    return CMP_ERROR;
168
  }
169
  switch (v1.type) {
170
  case T_ENUM:
171
  case T_INT:
172
  case T_BOOL:
173
    return int_cmp(v1.val.i, v2.val.i);
174
  case T_PAIR:
175
  case T_QUAD:
176
    return uint_cmp(v1.val.i, v2.val.i);
177
  case T_EC:
178
    return u64_cmp(v1.val.ec, v2.val.ec);
179
  case T_IP:
180
    return ipa_compare(v1.val.px.ip, v2.val.px.ip);
181
  case T_PREFIX:
182
    if (rc = ipa_compare(v1.val.px.ip, v2.val.px.ip))
183
      return rc;
184
    if (v1.val.px.len < v2.val.px.len)
185
      return -1;
186
    if (v1.val.px.len > v2.val.px.len)
187
      return 1;
188
    return 0;
189
  case T_PATH_MASK:
190
    return pm_path_compare(v1.val.path_mask, v2.val.path_mask);
191
  case T_STRING:
192
    return strcmp(v1.val.s, v2.val.s);
193
  default:
194
    debug( "Compare of unknown entities: %x\n", v1.type );
195
    return CMP_ERROR;
196
  }
197
}
198

    
199
int 
200
tree_compare(const void *p1, const void *p2)
201
{
202
  return val_compare((* (struct f_tree **) p1)->from, (* (struct f_tree **) p2)->from);
203
}
204

    
205
void
206
fprefix_get_bounds(struct f_prefix *px, int *l, int *h)
207
{
208
  *l = *h = px->len & LEN_MASK;
209

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

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

    
216
  else if (px->len & LEN_RANGE)
217
    {
218
      *l = 0xff & (px->len >> 16);
219
      *h = 0xff & (px->len >> 8);
220
    }
221
}
222

    
223
/*
224
 * val_simple_in_range - check if @v1 ~ @v2 for everything except sets
225
 */ 
226
static int
227
val_simple_in_range(struct f_val v1, struct f_val v2)
228
{
229
  if ((v1.type == T_PATH) && (v2.type == T_PATH_MASK))
230
    return as_path_match(v1.val.ad, v2.val.path_mask);
231
  if (((v1.type == T_PAIR) || (v1.type == T_QUAD)) && (v2.type == T_CLIST))
232
    return int_set_contains(v2.val.ad, v1.val.i);
233
#ifndef IPV6
234
  /* IP->Quad implicit conversion */
235
  if ((v1.type == T_IP) && (v2.type == T_CLIST))
236
    return int_set_contains(v2.val.ad, ipa_to_u32(v1.val.px.ip));
237
#endif
238
  if ((v1.type == T_EC) && (v2.type == T_ECLIST))
239
    return ec_set_contains(v2.val.ad, v1.val.ec);
240

    
241
  if ((v1.type == T_STRING) && (v2.type == T_STRING))
242
    return patmatch(v2.val.s, v1.val.s);
243

    
244
  if ((v1.type == T_IP) && (v2.type == T_PREFIX))
245
    return ipa_in_net(v1.val.px.ip, v2.val.px.ip, v2.val.px.len);
246

    
247
  if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX))
248
    return ipa_in_net(v1.val.px.ip, v2.val.px.ip, v2.val.px.len) && (v1.val.px.len >= v2.val.px.len);
249

    
250
  return CMP_ERROR;
251
}
252

    
253
static int
254
clist_set_type(struct f_tree *set, struct f_val *v)
255
{
256
 switch (set->from.type) {
257
  case T_PAIR:
258
    v->type = T_PAIR;
259
    return 1;
260
  case T_QUAD:
261
#ifndef IPV6
262
  case T_IP:
263
#endif
264
    v->type = T_QUAD;
265
    return 1;
266
    break;
267
  default:
268
    v->type = T_VOID;
269
    return 0;
270
  }
271
}
272

    
273
static inline int
274
eclist_set_type(struct f_tree *set)
275
{ return set->from.type == T_EC; }
276

    
277
static int
278
clist_match_set(struct adata *clist, struct f_tree *set)
279
{
280
  if (!clist)
281
    return 0;
282

    
283
  struct f_val v;
284
  if (!clist_set_type(set, &v))
285
    return CMP_ERROR;
286

    
287
  u32 *l = (u32 *) clist->data;
288
  u32 *end = l + clist->length/4;
289

    
290
  while (l < end) {
291
    v.val.i = *l++;
292
    if (find_tree(set, v))
293
      return 1;
294
  }
295
  return 0;
296
}
297

    
298
static int
299
eclist_match_set(struct adata *list, struct f_tree *set)
300
{
301
  if (!list)
302
    return 0;
303

    
304
  if (!eclist_set_type(set))
305
    return CMP_ERROR;
306

    
307
  struct f_val v;
308
  u32 *l = int_set_get_data(list);
309
  int len = int_set_get_size(list);
310
  int i;
311

    
312
  v.type = T_EC;
313
  for (i = 0; i < len; i += 2) {
314
    v.val.ec = ec_get(l, i);
315
    if (find_tree(set, v))
316
      return 1;
317
  }
318

    
319
  return 0;
320
}
321

    
322
static struct adata *
323
clist_filter(struct linpool *pool, struct adata *clist, struct f_tree *set, int pos)
324
{
325
  if (!clist)
326
    return NULL;
327

    
328
  struct f_val v;
329
  clist_set_type(set, &v);
330

    
331
  u32 tmp[clist->length/4];
332
  u32 *l = (u32 *) clist->data;
333
  u32 *k = tmp;
334
  u32 *end = l + clist->length/4;
335

    
336
  while (l < end) {
337
    v.val.i = *l++;
338
    if (pos == !!find_tree(set, v))        /* pos && find_tree || !pos && !find_tree */
339
      *k++ = v.val.i;
340
  }
341

    
342
  int nl = (k - tmp) * 4;
343
  if (nl == clist->length)
344
    return clist;
345

    
346
  struct adata *res = adata_empty(pool, nl);
347
  memcpy(res->data, tmp, nl);
348
  return res;
349
}
350

    
351
static struct adata *
352
eclist_filter(struct linpool *pool, struct adata *list, struct f_tree *set, int pos)
353
{
354
  if (!list)
355
    return NULL;
356

    
357
  struct f_val v;
358

    
359
  int len = int_set_get_size(list);
360
  u32 *l = int_set_get_data(list);
361
  u32 tmp[len];
362
  u32 *k = tmp;
363
  int i;
364

    
365
  v.type = T_EC;
366
  for (i = 0; i < len; i += 2) {
367
    v.val.ec = ec_get(l, i);
368
    if (pos == !!find_tree(set, v)) {        /* pos && find_tree || !pos && !find_tree */
369
      *k++ = l[i];
370
      *k++ = l[i+1];
371
    }
372
  }
373

    
374
  int nl = (k - tmp) * 4;
375
  if (nl == list->length)
376
    return list;
377

    
378
  struct adata *res = adata_empty(pool, nl);
379
  memcpy(res->data, tmp, nl);
380
  return res;
381
}
382

    
383
/**
384
 * val_in_range - implement |~| operator
385
 * @v1: element
386
 * @v2: set
387
 *
388
 * Checks if @v1 is element (|~| operator) of @v2. Sets are internally represented as balanced trees, see
389
 * |tree.c| module (this is not limited to sets, but for non-set cases, val_simple_in_range() is called early).
390
 */
391
static int
392
val_in_range(struct f_val v1, struct f_val v2)
393
{
394
  int res;
395

    
396
  res = val_simple_in_range(v1, v2);
397

    
398
  if (res != CMP_ERROR)
399
    return res;
400
  
401
  if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX_SET))
402
    return trie_match_fprefix(v2.val.ti, &v1.val.px);
403

    
404
  if ((v1.type == T_CLIST) && (v2.type == T_SET))
405
    return clist_match_set(v1.val.ad, v2.val.t);
406

    
407
  if ((v1.type == T_ECLIST) && (v2.type == T_SET))
408
    return eclist_match_set(v1.val.ad, v2.val.t);
409

    
410
  if (v2.type == T_SET)
411
    switch (v1.type) {
412
    case T_ENUM:
413
    case T_INT:
414
    case T_PAIR:
415
    case T_QUAD:
416
    case T_IP:
417
    case T_EC:
418
      {
419
        struct f_tree *n;
420
        n = find_tree(v2.val.t, v1);
421
        if (!n)
422
          return 0;
423
        return !! (val_simple_in_range(v1, n->from));        /* We turn CMP_ERROR into compared ok, and that's fine */
424
      }
425
    }
426
  return CMP_ERROR;
427
}
428

    
429
static void val_print(struct f_val v);
430

    
431
static void
432
tree_node_print(struct f_tree *t, char **sep)
433
{
434
  if (t == NULL)
435
    return;
436

    
437
  tree_node_print(t->left, sep);
438

    
439
  logn(*sep);
440
  val_print(t->from);
441
  if (val_compare(t->from, t->to) != 0)
442
    {
443
      logn( ".." );
444
      val_print(t->to);
445
    }
446
  *sep = ", ";
447

    
448
  tree_node_print(t->right, sep);
449
}
450

    
451
static void
452
tree_print(struct f_tree *t)
453
{
454
  char *sep = "";
455
  logn( "[" );
456
  tree_node_print(t, &sep);
457
  logn( "] " );
458
}
459

    
460
/*
461
 * val_print - format filter value
462
 */
463
static void
464
val_print(struct f_val v)
465
{
466
  char buf2[1024];
467
  switch (v.type) {
468
  case T_VOID: logn("(void)"); return;
469
  case T_BOOL: logn(v.val.i ? "TRUE" : "FALSE"); return;
470
  case T_INT: logn("%d", v.val.i); return;
471
  case T_STRING: logn("%s", v.val.s); return;
472
  case T_IP: logn("%I", v.val.px.ip); return;
473
  case T_PREFIX: logn("%I/%d", v.val.px.ip, v.val.px.len); return;
474
  case T_PAIR: logn("(%d,%d)", v.val.i >> 16, v.val.i & 0xffff); return;
475
  case T_QUAD: logn("%R", v.val.i); return;
476
  case T_EC: ec_format(buf2, v.val.ec); logn("%s", buf2); return;
477
  case T_PREFIX_SET: trie_print(v.val.ti); return;
478
  case T_SET: tree_print(v.val.t); return;
479
  case T_ENUM: logn("(enum %x)%d", v.type, v.val.i); return;
480
  case T_PATH: as_path_format(v.val.ad, buf2, 1000); logn("(path %s)", buf2); return;
481
  case T_CLIST: int_set_format(v.val.ad, 1, -1, buf2, 1000); logn("(clist %s)", buf2); return;
482
  case T_ECLIST: ec_set_format(v.val.ad, -1, buf2, 1000); logn("(eclist %s)", buf2); return;
483
  case T_PATH_MASK: pm_format(v.val.path_mask, buf2, 1000); logn("(pathmask%s)", buf2); return;
484
  default: logn( "[unknown type %x]", v.type ); return;
485
  }
486
}
487

    
488
static struct rte **f_rte, *f_rte_old;
489
static struct linpool *f_pool;
490
static struct ea_list **f_tmp_attrs;
491
static int f_flags;
492

    
493
/*
494
 * rta_cow - prepare rta for modification by filter
495
 */
496
static void
497
rta_cow(void)
498
{
499
  if ((*f_rte)->attrs->aflags & RTAF_CACHED) {
500
    rta *f_rta_copy = lp_alloc(f_pool, sizeof(rta));
501
    memcpy(f_rta_copy, (*f_rte)->attrs, sizeof(rta));
502
    f_rta_copy->aflags = 0;
503
    *f_rte = rte_cow(*f_rte);
504
    rta_free((*f_rte)->attrs);
505
    (*f_rte)->attrs = f_rta_copy;
506
  }
507
}
508

    
509
static struct rate_limit rl_runtime_err;
510

    
511
#define runtime(x) do { \
512
    log_rl(&rl_runtime_err, L_ERR "filters, line %d: %s", what->lineno, x); \
513
    res.type = T_RETURN; \
514
    res.val.i = F_ERROR; \
515
    return res; \
516
  } while(0)
517

    
518
#define ARG(x,y) \
519
        x = interpret(what->y); \
520
        if (x.type & T_RETURN) \
521
                return x;
522

    
523
#define ONEARG ARG(v1, a1.p)
524
#define TWOARGS ARG(v1, a1.p) \
525
                ARG(v2, a2.p)
526
#define TWOARGS_C TWOARGS \
527
                  if (v1.type != v2.type) \
528
                    runtime( "Can't operate with values of incompatible types" );
529

    
530
/**
531
 * interpret
532
 * @what: filter to interpret
533
 *
534
 * Interpret given tree of filter instructions. This is core function
535
 * of filter system and does all the hard work.
536
 *
537
 * Each instruction has 4 fields: code (which is instruction code),
538
 * aux (which is extension to instruction code, typically type),
539
 * arg1 and arg2 - arguments. Depending on instruction, arguments
540
 * are either integers, or pointers to instruction trees. Common 
541
 * instructions like +, that have two expressions as arguments use
542
 * TWOARGS macro to get both of them evaluated.
543
 *
544
 * &f_val structures are copied around, so there are no problems with
545
 * memory managment.
546
 */
547
static struct f_val
548
interpret(struct f_inst *what)
549
{
550
  struct symbol *sym;
551
  struct f_val v1, v2, res, *vp;
552
  unsigned u1, u2;
553
  int i;
554
  u32 as;
555

    
556
  res.type = T_VOID;
557
  if (!what)
558
    return res;
559

    
560
  switch(what->code) {
561
  case ',':
562
    TWOARGS;
563
    break;
564

    
565
/* Binary operators */
566
  case '+':
567
    TWOARGS_C;
568
    switch (res.type = v1.type) {
569
    case T_VOID: runtime( "Can't operate with values of type void" );
570
    case T_INT: res.val.i = v1.val.i + v2.val.i; break;
571
    default: runtime( "Usage of unknown type" );
572
    }
573
    break;
574
  case '-':
575
    TWOARGS_C;
576
    switch (res.type = v1.type) {
577
    case T_VOID: runtime( "Can't operate with values of type void" );
578
    case T_INT: res.val.i = v1.val.i - v2.val.i; break;
579
    default: runtime( "Usage of unknown type" );
580
    }
581
    break;
582
  case '*':
583
    TWOARGS_C;
584
    switch (res.type = v1.type) {
585
    case T_VOID: runtime( "Can't operate with values of type void" );
586
    case T_INT: res.val.i = v1.val.i * v2.val.i; break;
587
    default: runtime( "Usage of unknown type" );
588
    }
589
    break;
590
  case '/':
591
    TWOARGS_C;
592
    switch (res.type = v1.type) {
593
    case T_VOID: runtime( "Can't operate with values of type void" );
594
    case T_INT: if (v2.val.i == 0) runtime( "Mother told me not to divide by 0" );
595
                      res.val.i = v1.val.i / v2.val.i; break;
596
    case T_IP: if (v2.type != T_INT)
597
                 runtime( "Incompatible types in / operator" );
598
               break;
599
    default: runtime( "Usage of unknown type" );
600
    }
601
    break;
602
    
603
  case '&':
604
  case '|':
605
    ARG(v1, a1.p);
606
    if (v1.type != T_BOOL)
607
      runtime( "Can't do boolean operation on non-booleans" );
608
    if (v1.val.i == (what->code == '|')) {
609
      res.type = T_BOOL;
610
      res.val.i = v1.val.i;
611
      break;
612
    }
613

    
614
    ARG(v2, a2.p);
615
    if (v2.type != T_BOOL)
616
      runtime( "Can't do boolean operation on non-booleans" );
617
    res.type = T_BOOL;
618
    res.val.i = v2.val.i;
619
    break;
620

    
621
  case P('m','p'):
622
    TWOARGS;
623
    if ((v1.type != T_INT) || (v2.type != T_INT))
624
      runtime( "Can't operate with value of non-integer type in pair constructor" );
625
    u1 = v1.val.i;
626
    u2 = v2.val.i;
627
    if ((u1 > 0xFFFF) || (u2 > 0xFFFF))
628
      runtime( "Can't operate with value out of bounds in pair constructor" );
629
    res.val.i = (u1 << 16) | u2;
630
    res.type = T_PAIR;
631
    break;
632

    
633
  case P('m','c'):
634
    {
635
      TWOARGS;
636

    
637
      int check, ipv4_used;
638
      u32 key, val;
639

    
640
      if (v1.type == T_INT) {
641
        ipv4_used = 0; key = v1.val.i;
642
      } 
643
      else if (v1.type == T_QUAD) {
644
        ipv4_used = 1; key = v1.val.i;
645
      }
646
#ifndef IPV6
647
      /* IP->Quad implicit conversion */
648
      else if (v1.type == T_IP) {
649
        ipv4_used = 1; key = ipa_to_u32(v1.val.px.ip);
650
      }
651
#endif
652
      else
653
        runtime("Can't operate with key of non-integer/IPv4 type in EC constructor");
654

    
655
      if (v2.type != T_INT)
656
        runtime("Can't operate with value of non-integer type in EC constructor");
657
      val = v2.val.i;
658

    
659
      res.type = T_EC;
660

    
661
      if (what->aux == EC_GENERIC) {
662
        check = 0; res.val.ec = ec_generic(key, val);
663
      }
664
      else if (ipv4_used) {
665
        check = 1; res.val.ec = ec_ip4(what->aux, key, val);
666
      }
667
      else if (key < 0x10000) {
668
        check = 0; res.val.ec = ec_as2(what->aux, key, val);
669
      }
670
      else {
671
        check = 1; res.val.ec = ec_as4(what->aux, key, val);
672
      }
673

    
674
      if (check && (val > 0xFFFF))
675
        runtime("Can't operate with value out of bounds in EC constructor");
676

    
677
      break;
678
    }
679

    
680
/* Relational operators */
681

    
682
#define COMPARE(x) \
683
    TWOARGS; \
684
    i = val_compare(v1, v2); \
685
    if (i==CMP_ERROR) \
686
      runtime( "Can't compare values of incompatible types" ); \
687
    res.type = T_BOOL; \
688
    res.val.i = (x); \
689
    break;
690

    
691
  case P('!','='): COMPARE(i!=0);
692
  case P('=','='): COMPARE(i==0);
693
  case '<': COMPARE(i==-1);
694
  case P('<','='): COMPARE(i!=1);
695

    
696
  case '!':
697
    ONEARG;
698
    if (v1.type != T_BOOL)
699
      runtime( "Not applied to non-boolean" );
700
    res = v1;
701
    res.val.i = !res.val.i;
702
    break;
703

    
704
  case '~':
705
    TWOARGS;
706
    res.type = T_BOOL;
707
    res.val.i = val_in_range(v1, v2);
708
    if (res.val.i == CMP_ERROR)
709
      runtime( "~ applied on unknown type pair" );
710
    res.val.i = !!res.val.i;
711
    break;
712
  case P('d','e'):
713
    ONEARG;
714
    res.type = T_BOOL;
715
    res.val.i = (v1.type != T_VOID);
716
    break;
717

    
718
  /* Set to indirect value, a1 = variable, a2 = value */
719
  case 's':
720
    ARG(v2, a2.p);
721
    sym = what->a1.p;
722
    vp = sym->def;
723
    if ((sym->class != (SYM_VARIABLE | v2.type)) && (v2.type != T_VOID)) {
724
#ifndef IPV6
725
      /* IP->Quad implicit conversion */
726
      if ((sym->class == (SYM_VARIABLE | T_QUAD)) && (v2.type == T_IP)) {
727
        vp->type = T_QUAD;
728
        vp->val.i = ipa_to_u32(v2.val.px.ip);
729
        break;
730
      }
731
#endif
732
      runtime( "Assigning to variable of incompatible type" );
733
    }
734
    *vp = v2; 
735
    break;
736

    
737
    /* some constants have value in a2, some in *a1.p, strange. */
738
  case 'c':        /* integer (or simple type) constant, string, set, or prefix_set */
739
    res.type = what->aux;
740

    
741
    if (res.type == T_PREFIX_SET)
742
      res.val.ti = what->a2.p;
743
    else if (res.type == T_SET)
744
      res.val.t = what->a2.p;
745
    else if (res.type == T_STRING)
746
      res.val.s = what->a2.p;
747
    else
748
      res.val.i = what->a2.i;
749
    break;
750
  case 'V':
751
  case 'C':
752
    res = * ((struct f_val *) what->a1.p);
753
    break;
754
  case 'p':
755
    ONEARG;
756
    val_print(v1);
757
    break;
758
  case '?':        /* ? has really strange error value, so we can implement if ... else nicely :-) */
759
    ONEARG;
760
    if (v1.type != T_BOOL)
761
      runtime( "If requires boolean expression" );
762
    if (v1.val.i) {
763
      ARG(res,a2.p);
764
      res.val.i = 0;
765
    } else res.val.i = 1;
766
    res.type = T_BOOL;
767
    break;
768
  case '0':
769
    debug( "No operation\n" );
770
    break;
771
  case P('p',','):
772
    ONEARG;
773
    if (what->a2.i == F_NOP || (what->a2.i != F_NONL && what->a1.p))
774
      log_commit(*L_INFO);
775

    
776
    switch (what->a2.i) {
777
    case F_QUITBIRD:
778
      die( "Filter asked me to die" );
779
    case F_ACCEPT:
780
      /* Should take care about turning ACCEPT into MODIFY */
781
    case F_ERROR:
782
    case F_REJECT:        /* FIXME (noncritical) Should print complete route along with reason to reject route */
783
      res.type = T_RETURN;
784
      res.val.i = what->a2.i;
785
      return res;        /* We have to return now, no more processing. */
786
    case F_NONL:
787
    case F_NOP:
788
      break;
789
    default:
790
      bug( "unknown return type: Can't happen");
791
    }
792
    break;
793
  case 'a':        /* rta access */
794
    {
795
      struct rta *rta = (*f_rte)->attrs;
796
      res.type = what->aux;
797
      switch(res.type) {
798
      case T_IP:
799
        res.val.px.ip = * (ip_addr *) ((char *) rta + what->a2.i);
800
        break;
801
      case T_ENUM:
802
        res.val.i = * ((char *) rta + what->a2.i);
803
        break;
804
      case T_STRING:        /* Warning: this is a special case for proto attribute */
805
        res.val.s = rta->proto->name;
806
        break;
807
      case T_PREFIX:        /* Warning: this works only for prefix of network */
808
        {
809
          res.val.px.ip = (*f_rte)->net->n.prefix;
810
          res.val.px.len = (*f_rte)->net->n.pxlen;
811
          break;
812
        }
813
      default:
814
        bug( "Invalid type for rta access (%x)", res.type );
815
      }
816
    }
817
    break;
818
  case P('a','S'):
819
    ONEARG;
820
    if (what->aux != v1.type)
821
      runtime( "Attempt to set static attribute to incompatible type" );
822
    rta_cow();
823
    {
824
      struct rta *rta = (*f_rte)->attrs;
825
      switch (what->aux) {
826
      case T_ENUM:
827
        * ((char *) rta + what->a2.i) = v1.val.i;
828
        break;
829
      case T_IP:
830
        * (ip_addr *) ((char *) rta + what->a2.i) = v1.val.px.ip;
831
        break;
832
      default:
833
        bug( "Unknown type in set of static attribute" );
834
      }
835
    }
836
    break;
837
  case P('e','a'):        /* Access to extended attributes */
838
    {
839
      eattr *e = NULL;
840
      if (!(f_flags & FF_FORCE_TMPATTR))
841
        e = ea_find( (*f_rte)->attrs->eattrs, what->a2.i );
842
      if (!e) 
843
        e = ea_find( (*f_tmp_attrs), what->a2.i );
844
      if ((!e) && (f_flags & FF_FORCE_TMPATTR))
845
        e = ea_find( (*f_rte)->attrs->eattrs, what->a2.i );
846

    
847
      if (!e) {
848
        /* A special case: undefined int_set looks like empty int_set */
849
        if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_INT_SET) {
850
          res.type = T_CLIST;
851
          res.val.ad = adata_empty(f_pool, 0);
852
          break;
853
        }
854
        /* The same special case for ec_set */
855
        else if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_EC_SET) {
856
          res.type = T_ECLIST;
857
          res.val.ad = adata_empty(f_pool, 0);
858
          break;
859
        }
860

    
861
        /* Undefined value */
862
        res.type = T_VOID;
863
        break;
864
      }
865

    
866
      switch (what->aux & EAF_TYPE_MASK) {
867
      case EAF_TYPE_INT:
868
        res.type = T_INT;
869
        res.val.i = e->u.data;
870
        break;
871
      case EAF_TYPE_ROUTER_ID:
872
        res.type = T_QUAD;
873
        res.val.i = e->u.data;
874
        break;
875
      case EAF_TYPE_OPAQUE:
876
        res.type = T_ENUM_EMPTY;
877
        res.val.i = 0;
878
        break;
879
      case EAF_TYPE_IP_ADDRESS:
880
        res.type = T_IP;
881
        struct adata * ad = e->u.ptr;
882
        res.val.px.ip = * (ip_addr *) ad->data;
883
        break;
884
      case EAF_TYPE_AS_PATH:
885
        res.type = T_PATH;
886
        res.val.ad = e->u.ptr;
887
        break;
888
      case EAF_TYPE_INT_SET:
889
        res.type = T_CLIST;
890
        res.val.ad = e->u.ptr;
891
        break;
892
      case EAF_TYPE_EC_SET:
893
        res.type = T_ECLIST;
894
        res.val.ad = e->u.ptr;
895
        break;
896
      case EAF_TYPE_UNDEF:
897
        res.type = T_VOID;
898
        break;
899
      default:
900
        bug("Unknown type in e,a");
901
      }
902
    }
903
    break;
904
  case P('e','S'):
905
    ONEARG;
906
    {
907
      struct ea_list *l = lp_alloc(f_pool, sizeof(struct ea_list) + sizeof(eattr));
908

    
909
      l->next = NULL;
910
      l->flags = EALF_SORTED;
911
      l->count = 1;
912
      l->attrs[0].id = what->a2.i;
913
      l->attrs[0].flags = 0;
914
      l->attrs[0].type = what->aux | EAF_ORIGINATED;
915
      switch (what->aux & EAF_TYPE_MASK) {
916
      case EAF_TYPE_INT:
917
      case EAF_TYPE_ROUTER_ID:
918
        if (v1.type != T_INT)
919
          runtime( "Setting int attribute to non-int value" );
920
        l->attrs[0].u.data = v1.val.i;
921
        break;
922
      case EAF_TYPE_OPAQUE:
923
        runtime( "Setting opaque attribute is not allowed" );
924
        break;
925
      case EAF_TYPE_IP_ADDRESS:
926
        if (v1.type != T_IP)
927
          runtime( "Setting ip attribute to non-ip value" );
928
        int len = sizeof(ip_addr);
929
        struct adata *ad = lp_alloc(f_pool, sizeof(struct adata) + len);
930
        ad->length = len;
931
        (* (ip_addr *) ad->data) = v1.val.px.ip;
932
        l->attrs[0].u.ptr = ad;
933
        break;
934
      case EAF_TYPE_AS_PATH:
935
        if (v1.type != T_PATH)
936
          runtime( "Setting path attribute to non-path value" );
937
        l->attrs[0].u.ptr = v1.val.ad;
938
        break;
939
      case EAF_TYPE_INT_SET:
940
        if (v1.type != T_CLIST)
941
          runtime( "Setting clist attribute to non-clist value" );
942
        l->attrs[0].u.ptr = v1.val.ad;
943
        break;
944
      case EAF_TYPE_EC_SET:
945
        if (v1.type != T_ECLIST)
946
          runtime( "Setting eclist attribute to non-eclist value" );
947
        l->attrs[0].u.ptr = v1.val.ad;
948
        break;
949
      case EAF_TYPE_UNDEF:
950
        if (v1.type != T_VOID)
951
          runtime( "Setting void attribute to non-void value" );
952
        l->attrs[0].u.data = 0;
953
        break;
954
      default: bug("Unknown type in e,S");
955
      }
956

    
957
      if (!(what->aux & EAF_TEMP) && (!(f_flags & FF_FORCE_TMPATTR))) {
958
        rta_cow();
959
        l->next = (*f_rte)->attrs->eattrs;
960
        (*f_rte)->attrs->eattrs = l;
961
      } else {
962
        l->next = (*f_tmp_attrs);
963
        (*f_tmp_attrs) = l;
964
      }
965
    }
966
    break;
967
  case 'P':
968
    res.type = T_INT;
969
    res.val.i = (*f_rte)->pref;
970
    break;
971
  case P('P','S'):
972
    ONEARG;
973
    if (v1.type != T_INT)
974
      runtime( "Can't set preference to non-integer" );
975
    if ((v1.val.i < 0) || (v1.val.i > 0xFFFF))
976
      runtime( "Setting preference value out of bounds" );
977
    *f_rte = rte_cow(*f_rte);
978
    (*f_rte)->pref = v1.val.i;
979
    break;
980
  case 'L':        /* Get length of */
981
    ONEARG;
982
    res.type = T_INT;
983
    switch(v1.type) {
984
    case T_PREFIX: res.val.i = v1.val.px.len; break;
985
    case T_PATH:   res.val.i = as_path_getlen(v1.val.ad); break;
986
    default: runtime( "Prefix or path expected" );
987
    }
988
    break;
989
  case P('c','p'):        /* Convert prefix to ... */
990
    ONEARG;
991
    if (v1.type != T_PREFIX)
992
      runtime( "Prefix expected" );
993
    res.type = what->aux;
994
    switch(res.type) {
995
      /*    case T_INT:        res.val.i = v1.val.px.len; break; Not needed any more */
996
    case T_IP: res.val.px.ip = v1.val.px.ip; break;
997
    default: bug( "Unknown prefix to conversion" );
998
    }
999
    break;
1000
  case P('a','f'):        /* Get first ASN from AS PATH */
1001
    ONEARG;
1002
    if (v1.type != T_PATH)
1003
      runtime( "AS path expected" );
1004

    
1005
    as = 0;
1006
    as_path_get_first(v1.val.ad, &as);
1007
    res.type = T_INT;
1008
    res.val.i = as;
1009
    break;
1010
  case P('a','l'):        /* Get last ASN from AS PATH */
1011
    ONEARG;
1012
    if (v1.type != T_PATH)
1013
      runtime( "AS path expected" );
1014

    
1015
    as = 0;
1016
    as_path_get_last(v1.val.ad, &as);
1017
    res.type = T_INT;
1018
    res.val.i = as;
1019
    break;
1020
  case 'r':
1021
    ONEARG;
1022
    res = v1;
1023
    res.type |= T_RETURN;
1024
    return res;
1025
  case P('c','a'): /* CALL: this is special: if T_RETURN and returning some value, mask it out  */
1026
    ONEARG;
1027
    res = interpret(what->a2.p);
1028
    if (res.type == T_RETURN)
1029
      return res;
1030
    res.type &= ~T_RETURN;    
1031
    break;
1032
  case P('c','v'):        /* Clear local variables */
1033
    for (sym = what->a1.p; sym != NULL; sym = sym->aux2)
1034
      ((struct f_val *) sym->def)->type = T_VOID;
1035
    break;
1036
  case P('S','W'):
1037
    ONEARG;
1038
    {
1039
      struct f_tree *t = find_tree(what->a2.p, v1);
1040
      if (!t) {
1041
        v1.type = T_VOID;
1042
        t = find_tree(what->a2.p, v1);
1043
        if (!t) {
1044
          debug( "No else statement?\n");
1045
          break;
1046
        }
1047
      }        
1048
      /* It is actually possible to have t->data NULL */
1049

    
1050
      res = interpret(t->data);
1051
      if (res.type & T_RETURN)
1052
        return res;
1053
    }
1054
    break;
1055
  case P('i','M'): /* IP.MASK(val) */
1056
    TWOARGS;
1057
    if (v2.type != T_INT)
1058
      runtime( "Integer expected");
1059
    if (v1.type != T_IP)
1060
      runtime( "You can mask only IP addresses" );
1061
    {
1062
      ip_addr mask = ipa_mkmask(v2.val.i);
1063
      res.type = T_IP;
1064
      res.val.px.ip = ipa_and(mask, v1.val.px.ip);
1065
    }
1066
    break;
1067

    
1068
  case 'E':        /* Create empty attribute */
1069
    res.type = what->aux;
1070
    res.val.ad = adata_empty(f_pool, 0);
1071
    break;
1072
  case P('A','p'):        /* Path prepend */
1073
    TWOARGS;
1074
    if (v1.type != T_PATH)
1075
      runtime("Can't prepend to non-path");
1076
    if (v2.type != T_INT)
1077
      runtime("Can't prepend non-integer");
1078

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

    
1083
  case P('C','a'):        /* (Extended) Community list add or delete */
1084
    TWOARGS;
1085
    if (v1.type == T_CLIST)
1086
    {
1087
      /* Community (or cluster) list */
1088
      struct f_val dummy;
1089
      int arg_set = 0;
1090
      i = 0;
1091

    
1092
      if ((v2.type == T_PAIR) || (v2.type == T_QUAD))
1093
        i = v2.val.i;
1094
#ifndef IPV6
1095
      /* IP->Quad implicit conversion */
1096
      else if (v2.type == T_IP)
1097
        i = ipa_to_u32(v2.val.px.ip);
1098
#endif
1099
      else if ((v2.type == T_SET) && clist_set_type(v2.val.t, &dummy))
1100
        arg_set = 1;
1101
      else
1102
        runtime("Can't add/delete non-pair");
1103

    
1104
      res.type = T_CLIST;
1105
      switch (what->aux)
1106
      {
1107
      case 'a':
1108
        if (arg_set)
1109
          runtime("Can't add set");
1110
        res.val.ad = int_set_add(f_pool, v1.val.ad, i);
1111
        break;
1112
      
1113
      case 'd':
1114
        if (!arg_set)
1115
          res.val.ad = int_set_del(f_pool, v1.val.ad, i);
1116
        else
1117
          res.val.ad = clist_filter(f_pool, v1.val.ad, v2.val.t, 0);
1118
        break;
1119

    
1120
      case 'f':
1121
        if (!arg_set)
1122
          runtime("Can't filter pair");
1123
        res.val.ad = clist_filter(f_pool, v1.val.ad, v2.val.t, 1);
1124
        break;
1125

    
1126
      default:
1127
        bug("unknown Ca operation");
1128
      }
1129
    }
1130
    else if (v1.type == T_ECLIST)
1131
    {
1132
      /* Extended community list */
1133
      int arg_set = 0;
1134
      
1135
      /* v2.val is either EC or EC-set */
1136
      if ((v2.type == T_SET) && eclist_set_type(v2.val.t))
1137
        arg_set = 1;
1138
      else if (v2.type != T_EC)
1139
        runtime("Can't add/delete non-pair");
1140

    
1141
      res.type = T_ECLIST;
1142
      switch (what->aux)
1143
      {
1144
      case 'a':
1145
        if (arg_set)
1146
          runtime("Can't add set");
1147
        res.val.ad = ec_set_add(f_pool, v1.val.ad, v2.val.ec);
1148
        break;
1149
      
1150
      case 'd':
1151
        if (!arg_set)
1152
          res.val.ad = ec_set_del(f_pool, v1.val.ad, v2.val.ec);
1153
        else
1154
          res.val.ad = eclist_filter(f_pool, v1.val.ad, v2.val.t, 0);
1155
        break;
1156

    
1157
      case 'f':
1158
        if (!arg_set)
1159
          runtime("Can't filter ec");
1160
        res.val.ad = eclist_filter(f_pool, v1.val.ad, v2.val.t, 1);
1161
        break;
1162

    
1163
      default:
1164
        bug("unknown Ca operation");
1165
      }
1166
    }
1167
    else
1168
      runtime("Can't add/delete to non-(e)clist");
1169

    
1170
    break;
1171

    
1172
  default:
1173
    bug( "Unknown instruction %d (%c)", what->code, what->code & 0xff);
1174
  }
1175
  if (what->next)
1176
    return interpret(what->next);
1177
  return res;
1178
}
1179

    
1180
#undef ARG
1181
#define ARG(x,y) \
1182
        if (!i_same(f1->y, f2->y)) \
1183
                return 0;
1184

    
1185
#define ONEARG ARG(v1, a1.p)
1186
#define TWOARGS ARG(v1, a1.p) \
1187
                ARG(v2, a2.p)
1188

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

    
1191
/*
1192
 * i_same - function that does real comparing of instruction trees, you should call filter_same from outside
1193
 */
1194
int
1195
i_same(struct f_inst *f1, struct f_inst *f2)
1196
{
1197
  if ((!!f1) != (!!f2))
1198
    return 0;
1199
  if (!f1)
1200
    return 1;
1201
  if (f1->aux != f2->aux)
1202
    return 0;
1203
  if (f1->code != f2->code)
1204
    return 0;
1205
  if (f1 == f2)                /* It looks strange, but it is possible with call rewriting trickery */
1206
    return 1;
1207

    
1208
  switch(f1->code) {
1209
  case ',': /* fall through */
1210
  case '+':
1211
  case '-':
1212
  case '*':
1213
  case '/':
1214
  case '|':
1215
  case '&':
1216
  case P('m','p'):
1217
  case P('!','='):
1218
  case P('=','='):
1219
  case '<':
1220
  case P('<','='): TWOARGS; break;
1221

    
1222
  case '!': ONEARG; break;
1223
  case '~': TWOARGS; break;
1224
  case P('d','e'): ONEARG; break;
1225

    
1226
  case 's':
1227
    ARG(v2, a2.p);
1228
    {
1229
      struct symbol *s1, *s2;
1230
      s1 = f1->a1.p;
1231
      s2 = f2->a1.p;
1232
      if (strcmp(s1->name, s2->name))
1233
        return 0;
1234
      if (s1->class != s2->class)
1235
        return 0;
1236
    }
1237
    break;
1238

    
1239
  case 'c': 
1240
    switch (f1->aux) {
1241

    
1242
    case T_PREFIX_SET:
1243
      if (!trie_same(f1->a2.p, f2->a2.p))
1244
        return 0;
1245
      break;
1246

    
1247
    case T_SET:
1248
      if (!same_tree(f1->a2.p, f2->a2.p))
1249
        return 0;
1250
      break;
1251

    
1252
    case T_STRING:
1253
      if (strcmp(f1->a2.p, f2->a2.p))
1254
        return 0;
1255
      break;
1256

    
1257
    default:
1258
      A2_SAME;
1259
    }
1260
    break;
1261
  case 'C': 
1262
    if (val_compare(* (struct f_val *) f1->a1.p, * (struct f_val *) f2->a1.p))
1263
      return 0;
1264
    break;
1265
  case 'V': 
1266
    if (strcmp((char *) f1->a2.p, (char *) f2->a2.p))
1267
      return 0;
1268
    break;
1269
  case 'p': case 'L': ONEARG; break;
1270
  case '?': TWOARGS; break;
1271
  case '0': case 'E': break;
1272
  case P('p',','): ONEARG; A2_SAME; break;
1273
  case 'P':
1274
  case 'a': A2_SAME; break;
1275
  case P('e','a'): A2_SAME; break;
1276
  case P('P','S'):
1277
  case P('a','S'):
1278
  case P('e','S'): ONEARG; A2_SAME; break;
1279

    
1280
  case 'r': ONEARG; break;
1281
  case P('c','p'): ONEARG; break;
1282
  case P('c','a'): /* Call rewriting trickery to avoid exponential behaviour */
1283
             ONEARG; 
1284
             if (!i_same(f1->a2.p, f2->a2.p))
1285
               return 0; 
1286
             f2->a2.p = f1->a2.p;
1287
             break;
1288
  case P('c','v'): break; /* internal instruction */ 
1289
  case P('S','W'): ONEARG; if (!same_tree(f1->a2.p, f2->a2.p)) return 0; break;
1290
  case P('i','M'): TWOARGS; break;
1291
  case P('A','p'): TWOARGS; break;
1292
  case P('C','a'): TWOARGS; break;
1293
  case P('a','f'):
1294
  case P('a','l'): ONEARG; break;
1295
  default:
1296
    bug( "Unknown instruction %d in same (%c)", f1->code, f1->code & 0xff);
1297
  }
1298
  return i_same(f1->next, f2->next);
1299
}
1300

    
1301
/**
1302
 * f_run - external entry point to filters
1303
 * @filter: pointer to filter to run
1304
 * @tmp_attrs: where to store newly generated temporary attributes
1305
 * @rte: pointer to pointer to &rte being filtered. When route is modified, this is changed with rte_cow().
1306
 * @tmp_pool: all filter allocations go from this pool
1307
 * @flags: flags
1308
 */
1309
int
1310
f_run(struct filter *filter, struct rte **rte, struct ea_list **tmp_attrs, struct linpool *tmp_pool, int flags)
1311
{
1312
  struct f_inst *inst;
1313
  struct f_val res;
1314
  DBG( "Running filter `%s'...", filter->name );
1315

    
1316
  f_flags = flags;
1317
  f_tmp_attrs = tmp_attrs;
1318
  f_rte = rte;
1319
  f_rte_old = *rte;
1320
  f_pool = tmp_pool;
1321
  inst = filter->root;
1322

    
1323
  log_reset();
1324
  res = interpret(inst);
1325

    
1326
  if (res.type != T_RETURN) {
1327
    log( L_ERR "Filter %s did not return accept nor reject. Make up your mind", filter->name); 
1328
    return F_ERROR;
1329
  }
1330
  DBG( "done (%d)\n", res.val.i );
1331
  return res.val.i;
1332
}
1333

    
1334
int
1335
f_eval_int(struct f_inst *expr)
1336
{
1337
  /* Called independently in parse-time to eval expressions */
1338
  struct f_val res;
1339

    
1340
  f_flags = 0;
1341
  f_tmp_attrs = NULL;
1342
  f_rte = NULL;
1343
  f_rte_old = NULL;
1344
  f_pool = cfg_mem;
1345

    
1346
  log_reset();
1347
  res = interpret(expr);
1348

    
1349
  if (res.type != T_INT)
1350
    cf_error("Integer expression expected");
1351
  return res.val.i;
1352
}
1353

    
1354
u32
1355
f_eval_asn(struct f_inst *expr)
1356
{
1357
  /* Called as a part of another interpret call, therefore no log_reset() */
1358
  struct f_val res = interpret(expr);
1359
  return (res.type == T_INT) ? res.val.i : 0;
1360
}
1361

    
1362
/**
1363
 * filter_same - compare two filters
1364
 * @new: first filter to be compared
1365
 * @old: second filter to be compared, notice that this filter is
1366
 * damaged while comparing.
1367
 *
1368
 * Returns 1 in case filters are same, otherwise 0. If there are
1369
 * underlying bugs, it will rather say 0 on same filters than say
1370
 * 1 on different.
1371
 */
1372
int
1373
filter_same(struct filter *new, struct filter *old)
1374
{
1375
  if (old == new)        /* Handle FILTER_ACCEPT and FILTER_REJECT */
1376
    return 1;
1377
  if (old == FILTER_ACCEPT || old == FILTER_REJECT ||
1378
      new == FILTER_ACCEPT || new == FILTER_REJECT)
1379
    return 0;
1380
  return i_same(new->root, old->root);
1381
}