Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / filter / filter.c @ 6b3f1a54

History | View | Annotate | Download (46.4 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 "lib/net.h"
43
#include "lib/ip.h"
44
#include "nest/route.h"
45
#include "nest/protocol.h"
46
#include "nest/iface.h"
47
#include "nest/attrs.h"
48
#include "conf/conf.h"
49
#include "filter/filter.h"
50

    
51
#define P(a,b) ((a<<8) | b)
52

    
53
#define CMP_ERROR 999
54

    
55
void (*bt_assert_hook)(int result, struct f_inst *assert);
56

    
57
static struct adata undef_adata;        /* adata of length 0 used for undefined */
58

    
59
/* Special undef value for paths and clists */
60
static inline int
61
undef_value(struct f_val v)
62
{
63
  return ((v.type == T_PATH) || (v.type == T_CLIST) ||
64
          (v.type == T_ECLIST) || (v.type == T_LCLIST)) &&
65
    (v.val.ad == &undef_adata);
66
}
67

    
68
static struct adata *
69
adata_empty(struct linpool *pool, int l)
70
{
71
  struct adata *res = lp_alloc(pool, sizeof(struct adata) + l);
72
  res->length = l;
73
  return res;
74
}
75

    
76
static void
77
pm_format(struct f_path_mask *p, buffer *buf)
78
{
79
  buffer_puts(buf, "[= ");
80

    
81
  while (p)
82
  {
83
    switch(p->kind)
84
    {
85
    case PM_ASN:
86
      buffer_print(buf, "%u ", p->val);
87
      break;
88

    
89
    case PM_QUESTION:
90
      buffer_puts(buf, "? ");
91
      break;
92

    
93
    case PM_ASTERISK:
94
      buffer_puts(buf, "* ");
95
      break;
96

    
97
    case PM_ASN_RANGE:
98
      buffer_print(buf, "%u..%u ", p->val, p->val2);
99
      break;
100

    
101
    case PM_ASN_EXPR:
102
      buffer_print(buf, "%u ", f_eval_asn((struct f_inst *) p->val));
103
      break;
104
    }
105

    
106
    p = p->next;
107
  }
108

    
109
  buffer_puts(buf, "=]");
110
}
111

    
112
static inline int val_is_ip4(const struct f_val v)
113
{ return (v.type == T_IP) && ipa_is_ip4(v.val.ip); }
114

    
115
static inline int
116
lcomm_cmp(lcomm v1, lcomm v2)
117
{
118
  if (v1.asn != v2.asn)
119
    return (v1.asn > v2.asn) ? 1 : -1;
120
  if (v1.ldp1 != v2.ldp1)
121
    return (v1.ldp1 > v2.ldp1) ? 1 : -1;
122
  if (v1.ldp2 != v2.ldp2)
123
    return (v1.ldp2 > v2.ldp2) ? 1 : -1;
124
  return 0;
125
}
126

    
127
/**
128
 * val_compare - compare two values
129
 * @v1: first value
130
 * @v2: second value
131
 *
132
 * Compares two values and returns -1, 0, 1 on <, =, > or CMP_ERROR on
133
 * error. Tree module relies on this giving consistent results so
134
 * that it can be used for building balanced trees.
135
 */
136
int
137
val_compare(struct f_val v1, struct f_val v2)
138
{
139
  if (v1.type != v2.type) {
140
    if (v1.type == T_VOID)        /* Hack for else */
141
      return -1;
142
    if (v2.type == T_VOID)
143
      return 1;
144

    
145
    /* IP->Quad implicit conversion */
146
    if ((v1.type == T_QUAD) && val_is_ip4(v2))
147
      return uint_cmp(v1.val.i, ipa_to_u32(v2.val.ip));
148
    if (val_is_ip4(v1) && (v2.type == T_QUAD))
149
      return uint_cmp(ipa_to_u32(v1.val.ip), v2.val.i);
150

    
151
    debug( "Types do not match in val_compare\n" );
152
    return CMP_ERROR;
153
  }
154

    
155
  switch (v1.type) {
156
  case T_VOID:
157
    return 0;
158
  case T_ENUM:
159
  case T_INT:
160
  case T_BOOL:
161
  case T_PAIR:
162
  case T_QUAD:
163
    return uint_cmp(v1.val.i, v2.val.i);
164
  case T_EC:
165
  case T_RD:
166
    return u64_cmp(v1.val.ec, v2.val.ec);
167
  case T_LC:
168
    return lcomm_cmp(v1.val.lc, v2.val.lc);
169
  case T_IP:
170
    return ipa_compare(v1.val.ip, v2.val.ip);
171
  case T_NET:
172
    return net_compare(v1.val.net, v2.val.net);
173
  case T_STRING:
174
    return strcmp(v1.val.s, v2.val.s);
175
  default:
176
    return CMP_ERROR;
177
  }
178
}
179

    
180
static int
181
pm_same(struct f_path_mask *m1, struct f_path_mask *m2)
182
{
183
  while (m1 && m2)
184
  {
185
    if (m1->kind != m2->kind)
186
      return 0;
187

    
188
    if (m1->kind == PM_ASN_EXPR)
189
    {
190
      if (!i_same((struct f_inst *) m1->val, (struct f_inst *) m2->val))
191
        return 0;
192
    }
193
    else
194
    {
195
      if ((m1->val != m2->val) || (m1->val2 != m2->val2))
196
        return 0;
197
    }
198

    
199
    m1 = m1->next;
200
    m2 = m2->next;
201
  }
202

    
203
  return !m1 && !m2;
204
}
205

    
206
/**
207
 * val_same - compare two values
208
 * @v1: first value
209
 * @v2: second value
210
 *
211
 * Compares two values and returns 1 if they are same and 0 if not.
212
 * Comparison of values of different types is valid and returns 0.
213
 */
214
int
215
val_same(struct f_val v1, struct f_val v2)
216
{
217
  int rc;
218

    
219
  rc = val_compare(v1, v2);
220
  if (rc != CMP_ERROR)
221
    return !rc;
222

    
223
  if (v1.type != v2.type)
224
    return 0;
225

    
226
  switch (v1.type) {
227
  case T_PATH_MASK:
228
    return pm_same(v1.val.path_mask, v2.val.path_mask);
229
  case T_PATH:
230
  case T_CLIST:
231
  case T_ECLIST:
232
  case T_LCLIST:
233
    return adata_same(v1.val.ad, v2.val.ad);
234
  case T_SET:
235
    return same_tree(v1.val.t, v2.val.t);
236
  case T_PREFIX_SET:
237
    return trie_same(v1.val.ti, v2.val.ti);
238
  default:
239
    bug("Invalid type in val_same(): %x", v1.type);
240
  }
241
}
242

    
243
static int
244
clist_set_type(struct f_tree *set, struct f_val *v)
245
{
246
  switch (set->from.type)
247
  {
248
  case T_PAIR:
249
    v->type = T_PAIR;
250
    return 1;
251

    
252
  case T_QUAD:
253
    v->type = T_QUAD;
254
    return 1;
255

    
256
  case T_IP:
257
    if (val_is_ip4(set->from) && val_is_ip4(set->to))
258
    {
259
      v->type = T_QUAD;
260
      return 1;
261
    }
262
    /* Fall through */
263
  default:
264
    v->type = T_VOID;
265
    return 0;
266
  }
267
}
268

    
269
static inline int
270
eclist_set_type(struct f_tree *set)
271
{ return set->from.type == T_EC; }
272

    
273
static inline int
274
lclist_set_type(struct f_tree *set)
275
{ return set->from.type == T_LC; }
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 int
323
lclist_match_set(struct adata *list, struct f_tree *set)
324
{
325
  if (!list)
326
    return 0;
327

    
328
  if (!lclist_set_type(set))
329
    return CMP_ERROR;
330

    
331
  struct f_val v;
332
  u32 *l = int_set_get_data(list);
333
  int len = int_set_get_size(list);
334
  int i;
335

    
336
  v.type = T_LC;
337
  for (i = 0; i < len; i += 3) {
338
    v.val.lc = lc_get(l, i);
339
    if (find_tree(set, v))
340
      return 1;
341
  }
342

    
343
  return 0;
344
}
345

    
346
static struct adata *
347
clist_filter(struct linpool *pool, struct adata *list, struct f_val set, int pos)
348
{
349
  if (!list)
350
    return NULL;
351

    
352
  int tree = (set.type == T_SET);        /* 1 -> set is T_SET, 0 -> set is T_CLIST */
353
  struct f_val v;
354
  if (tree)
355
    clist_set_type(set.val.t, &v);
356
  else
357
    v.type = T_PAIR;
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
  u32 *end = l + len;
364

    
365
  while (l < end) {
366
    v.val.i = *l++;
367
    /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
368
    if ((tree ? !!find_tree(set.val.t, v) : int_set_contains(set.val.ad, v.val.i)) == pos)
369
      *k++ = v.val.i;
370
  }
371

    
372
  uint nl = (k - tmp) * sizeof(u32);
373
  if (nl == list->length)
374
    return list;
375

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

    
381
static struct adata *
382
eclist_filter(struct linpool *pool, struct adata *list, struct f_val set, int pos)
383
{
384
  if (!list)
385
    return NULL;
386

    
387
  int tree = (set.type == T_SET);        /* 1 -> set is T_SET, 0 -> set is T_CLIST */
388
  struct f_val v;
389

    
390
  int len = int_set_get_size(list);
391
  u32 *l = int_set_get_data(list);
392
  u32 tmp[len];
393
  u32 *k = tmp;
394
  int i;
395

    
396
  v.type = T_EC;
397
  for (i = 0; i < len; i += 2) {
398
    v.val.ec = ec_get(l, i);
399
    /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
400
    if ((tree ? !!find_tree(set.val.t, v) : ec_set_contains(set.val.ad, v.val.ec)) == pos) {
401
      *k++ = l[i];
402
      *k++ = l[i+1];
403
    }
404
  }
405

    
406
  uint nl = (k - tmp) * sizeof(u32);
407
  if (nl == list->length)
408
    return list;
409

    
410
  struct adata *res = adata_empty(pool, nl);
411
  memcpy(res->data, tmp, nl);
412
  return res;
413
}
414

    
415
static struct adata *
416
lclist_filter(struct linpool *pool, struct adata *list, struct f_val set, int pos)
417
{
418
  if (!list)
419
    return NULL;
420

    
421
  int tree = (set.type == T_SET);        /* 1 -> set is T_SET, 0 -> set is T_CLIST */
422
  struct f_val v;
423

    
424
  int len = int_set_get_size(list);
425
  u32 *l = int_set_get_data(list);
426
  u32 tmp[len];
427
  u32 *k = tmp;
428
  int i;
429

    
430
  v.type = T_LC;
431
  for (i = 0; i < len; i += 3) {
432
    v.val.lc = lc_get(l, i);
433
    /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
434
    if ((tree ? !!find_tree(set.val.t, v) : lc_set_contains(set.val.ad, v.val.lc)) == pos)
435
      k = lc_copy(k, l+i);
436
  }
437

    
438
  uint nl = (k - tmp) * sizeof(u32);
439
  if (nl == list->length)
440
    return list;
441

    
442
  struct adata *res = adata_empty(pool, nl);
443
  memcpy(res->data, tmp, nl);
444
  return res;
445
}
446

    
447
/**
448
 * val_in_range - implement |~| operator
449
 * @v1: element
450
 * @v2: set
451
 *
452
 * Checks if @v1 is element (|~| operator) of @v2.
453
 */
454
static int
455
val_in_range(struct f_val v1, struct f_val v2)
456
{
457
  if ((v1.type == T_PATH) && (v2.type == T_PATH_MASK))
458
    return as_path_match(v1.val.ad, v2.val.path_mask);
459

    
460
  if ((v1.type == T_INT) && (v2.type == T_PATH))
461
    return as_path_contains(v2.val.ad, v1.val.i, 1);
462

    
463
  if (((v1.type == T_PAIR) || (v1.type == T_QUAD)) && (v2.type == T_CLIST))
464
    return int_set_contains(v2.val.ad, v1.val.i);
465

    
466
  /* IP->Quad implicit conversion */
467
  if (val_is_ip4(v1) && (v2.type == T_CLIST))
468
    return int_set_contains(v2.val.ad, ipa_to_u32(v1.val.ip));
469

    
470
  if ((v1.type == T_EC) && (v2.type == T_ECLIST))
471
    return ec_set_contains(v2.val.ad, v1.val.ec);
472

    
473
  if ((v1.type == T_LC) && (v2.type == T_LCLIST))
474
    return lc_set_contains(v2.val.ad, v1.val.lc);
475

    
476
  if ((v1.type == T_STRING) && (v2.type == T_STRING))
477
    return patmatch(v2.val.s, v1.val.s);
478

    
479
  if ((v1.type == T_IP) && (v2.type == T_NET))
480
    return ipa_in_netX(v1.val.ip, v2.val.net);
481

    
482
  if ((v1.type == T_NET) && (v2.type == T_NET))
483
    return net_in_netX(v1.val.net, v2.val.net);
484

    
485
  if ((v1.type == T_NET) && (v2.type == T_PREFIX_SET))
486
    return trie_match_net(v2.val.ti, v1.val.net);
487

    
488
  if (v2.type != T_SET)
489
    return CMP_ERROR;
490

    
491
  /* With integrated Quad<->IP implicit conversion */
492
  if ((v1.type == v2.val.t->from.type) ||
493
      ((v1.type == T_QUAD) && val_is_ip4(v2.val.t->from) && val_is_ip4(v2.val.t->to)))
494
    return !!find_tree(v2.val.t, v1);
495

    
496
  if (v1.type == T_CLIST)
497
    return clist_match_set(v1.val.ad, v2.val.t);
498

    
499
  if (v1.type == T_ECLIST)
500
    return eclist_match_set(v1.val.ad, v2.val.t);
501

    
502
  if (v1.type == T_LCLIST)
503
    return lclist_match_set(v1.val.ad, v2.val.t);
504

    
505
  if (v1.type == T_PATH)
506
    return as_path_match_set(v1.val.ad, v2.val.t);
507

    
508
  return CMP_ERROR;
509
}
510

    
511
/*
512
 * val_format - format filter value
513
 */
514
void
515
val_format(struct f_val v, buffer *buf)
516
{
517
  char buf2[1024];
518
  switch (v.type)
519
  {
520
  case T_VOID:        buffer_puts(buf, "(void)"); return;
521
  case T_BOOL:        buffer_puts(buf, v.val.i ? "TRUE" : "FALSE"); return;
522
  case T_INT:        buffer_print(buf, "%u", v.val.i); return;
523
  case T_STRING: buffer_print(buf, "%s", v.val.s); return;
524
  case T_IP:        buffer_print(buf, "%I", v.val.ip); return;
525
  case T_NET:   buffer_print(buf, "%N", v.val.net); return;
526
  case T_PAIR:        buffer_print(buf, "(%u,%u)", v.val.i >> 16, v.val.i & 0xffff); return;
527
  case T_QUAD:        buffer_print(buf, "%R", v.val.i); return;
528
  case T_EC:        ec_format(buf2, v.val.ec); buffer_print(buf, "%s", buf2); return;
529
  case T_LC:        lc_format(buf2, v.val.lc); buffer_print(buf, "%s", buf2); return;
530
  case T_RD:        rd_format(v.val.ec, buf2, 1024); buffer_print(buf, "%s", buf2); return;
531
  case T_PREFIX_SET: trie_format(v.val.ti, buf); return;
532
  case T_SET:        tree_format(v.val.t, buf); return;
533
  case T_ENUM:        buffer_print(buf, "(enum %x)%u", v.type, v.val.i); return;
534
  case T_PATH:        as_path_format(v.val.ad, buf2, 1000); buffer_print(buf, "(path %s)", buf2); return;
535
  case T_CLIST:        int_set_format(v.val.ad, 1, -1, buf2, 1000); buffer_print(buf, "(clist %s)", buf2); return;
536
  case T_ECLIST: ec_set_format(v.val.ad, -1, buf2, 1000); buffer_print(buf, "(eclist %s)", buf2); return;
537
  case T_LCLIST: lc_set_format(v.val.ad, -1, buf2, 1000); buffer_print(buf, "(lclist %s)", buf2); return;
538
  case T_PATH_MASK: pm_format(v.val.path_mask, buf); return;
539
  default:        buffer_print(buf, "[unknown type %x]", v.type); return;
540
  }
541
}
542

    
543
static struct rte **f_rte;
544
static struct rta *f_old_rta;
545
static struct ea_list **f_tmp_attrs;
546
static struct linpool *f_pool;
547
static struct buffer f_buf;
548
static int f_flags;
549

    
550
static inline void f_rte_cow(void)
551
{
552
  *f_rte = rte_cow(*f_rte);
553
}
554

    
555
/*
556
 * rta_cow - prepare rta for modification by filter
557
 */
558
static void
559
f_rta_cow(void)
560
{
561
  if (!rta_is_cached((*f_rte)->attrs))
562
    return;
563

    
564
  /* Prepare to modify rte */
565
  f_rte_cow();
566

    
567
  /* Store old rta to free it later, it stores reference from rte_cow() */
568
  f_old_rta = (*f_rte)->attrs;
569

    
570
  /*
571
   * Get shallow copy of rta. Fields eattrs and nexthops of rta are shared
572
   * with f_old_rta (they will be copied when the cached rta will be obtained
573
   * at the end of f_run()), also the lock of hostentry is inherited (we
574
   * suppose hostentry is not changed by filters).
575
   */
576
  (*f_rte)->attrs = rta_do_cow((*f_rte)->attrs, f_pool);
577
}
578

    
579
static char *
580
val_format_str(struct f_val v) {
581
  buffer b;
582
  LOG_BUFFER_INIT(b);
583
  val_format(v, &b);
584
  return lp_strdup(f_pool, b.start);
585
}
586

    
587
static struct tbf rl_runtime_err = TBF_DEFAULT_LOG_LIMITS;
588

    
589
#define runtime(fmt, ...) do { \
590
    log_rl(&rl_runtime_err, L_ERR "filters, line %d: " fmt, what->lineno, ##__VA_ARGS__); \
591
    res.type = T_RETURN; \
592
    res.val.i = F_ERROR; \
593
    return res; \
594
  } while(0)
595

    
596
#define ARG(x,y) \
597
        x = interpret(what->y); \
598
        if (x.type & T_RETURN) \
599
                return x;
600

    
601
#define ONEARG ARG(v1, a1.p)
602
#define TWOARGS ARG(v1, a1.p) \
603
                ARG(v2, a2.p)
604
#define TWOARGS_C TWOARGS \
605
                  if (v1.type != v2.type) \
606
                    runtime( "Can't operate with values of incompatible types" );
607
#define ACCESS_RTE \
608
  do { if (!f_rte) runtime("No route to access"); } while (0)
609

    
610
#define BITFIELD_MASK(what) \
611
  (1u << (what->a2.i >> 24))
612

    
613
/**
614
 * interpret
615
 * @what: filter to interpret
616
 *
617
 * Interpret given tree of filter instructions. This is core function
618
 * of filter system and does all the hard work.
619
 *
620
 * Each instruction has 4 fields: code (which is instruction code),
621
 * aux (which is extension to instruction code, typically type),
622
 * arg1 and arg2 - arguments. Depending on instruction, arguments
623
 * are either integers, or pointers to instruction trees. Common
624
 * instructions like +, that have two expressions as arguments use
625
 * TWOARGS macro to get both of them evaluated.
626
 *
627
 * &f_val structures are copied around, so there are no problems with
628
 * memory managment.
629
 */
630
static struct f_val
631
interpret(struct f_inst *what)
632
{
633
  struct symbol *sym;
634
  struct f_val v1, v2, res, *vp;
635
  unsigned u1, u2;
636
  int i;
637
  u32 as;
638

    
639
  res.type = T_VOID;
640
  if (!what)
641
    return res;
642

    
643
  switch(what->code) {
644
  case ',':
645
    TWOARGS;
646
    break;
647

    
648
/* Binary operators */
649
  case '+':
650
    TWOARGS_C;
651
    switch (res.type = v1.type) {
652
    case T_VOID: runtime( "Can't operate with values of type void" );
653
    case T_INT: res.val.i = v1.val.i + v2.val.i; break;
654
    default: runtime( "Usage of unknown type" );
655
    }
656
    break;
657
  case '-':
658
    TWOARGS_C;
659
    switch (res.type = v1.type) {
660
    case T_VOID: runtime( "Can't operate with values of type void" );
661
    case T_INT: res.val.i = v1.val.i - v2.val.i; break;
662
    default: runtime( "Usage of unknown type" );
663
    }
664
    break;
665
  case '*':
666
    TWOARGS_C;
667
    switch (res.type = v1.type) {
668
    case T_VOID: runtime( "Can't operate with values of type void" );
669
    case T_INT: res.val.i = v1.val.i * v2.val.i; break;
670
    default: runtime( "Usage of unknown type" );
671
    }
672
    break;
673
  case '/':
674
    TWOARGS_C;
675
    switch (res.type = v1.type) {
676
    case T_VOID: runtime( "Can't operate with values of type void" );
677
    case T_INT: if (v2.val.i == 0) runtime( "Mother told me not to divide by 0" );
678
                      res.val.i = v1.val.i / v2.val.i; break;
679
    default: runtime( "Usage of unknown type" );
680
    }
681
    break;
682

    
683
  case '&':
684
  case '|':
685
    ARG(v1, a1.p);
686
    if (v1.type != T_BOOL)
687
      runtime( "Can't do boolean operation on non-booleans" );
688
    if (v1.val.i == (what->code == '|')) {
689
      res.type = T_BOOL;
690
      res.val.i = v1.val.i;
691
      break;
692
    }
693

    
694
    ARG(v2, a2.p);
695
    if (v2.type != T_BOOL)
696
      runtime( "Can't do boolean operation on non-booleans" );
697
    res.type = T_BOOL;
698
    res.val.i = v2.val.i;
699
    break;
700

    
701
  case P('m','p'):
702
    TWOARGS;
703
    if ((v1.type != T_INT) || (v2.type != T_INT))
704
      runtime( "Can't operate with value of non-integer type in pair constructor" );
705
    u1 = v1.val.i;
706
    u2 = v2.val.i;
707
    if ((u1 > 0xFFFF) || (u2 > 0xFFFF))
708
      runtime( "Can't operate with value out of bounds in pair constructor" );
709
    res.val.i = (u1 << 16) | u2;
710
    res.type = T_PAIR;
711
    break;
712

    
713
  case P('m','c'):
714
    {
715
      TWOARGS;
716

    
717
      int check, ipv4_used;
718
      u32 key, val;
719

    
720
      if (v1.type == T_INT) {
721
        ipv4_used = 0; key = v1.val.i;
722
      }
723
      else if (v1.type == T_QUAD) {
724
        ipv4_used = 1; key = v1.val.i;
725
      }
726
      /* IP->Quad implicit conversion */
727
      else if (val_is_ip4(v1)) {
728
        ipv4_used = 1; key = ipa_to_u32(v1.val.ip);
729
      }
730
      else
731
        runtime("Can't operate with key of non-integer/IPv4 type in EC constructor");
732

    
733
      if (v2.type != T_INT)
734
        runtime("Can't operate with value of non-integer type in EC constructor");
735
      val = v2.val.i;
736

    
737
      /* XXXX */
738
      res.type = T_EC;
739

    
740
      if (what->aux == EC_GENERIC) {
741
        check = 0; res.val.ec = ec_generic(key, val);
742
      }
743
      else if (ipv4_used) {
744
        check = 1; res.val.ec = ec_ip4(what->aux, key, val);
745
      }
746
      else if (key < 0x10000) {
747
        check = 0; res.val.ec = ec_as2(what->aux, key, val);
748
      }
749
      else {
750
        check = 1; res.val.ec = ec_as4(what->aux, key, val);
751
      }
752

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

    
756
      break;
757
    }
758

    
759
  case P('m','l'):
760
    {
761
      TWOARGS;
762

    
763
      /* Third argument hack */
764
      struct f_val v3 = interpret(INST3(what).p);
765
      if (v3.type & T_RETURN)
766
        return v3;
767

    
768
      if ((v1.type != T_INT) || (v2.type != T_INT) || (v3.type != T_INT))
769
        runtime( "Can't operate with value of non-integer type in LC constructor" );
770

    
771
      res.type = T_LC;
772
      res.val.lc = (lcomm) { v1.val.i, v2.val.i, v3.val.i };
773

    
774
      break;
775
    }
776

    
777
/* Relational operators */
778

    
779
#define COMPARE(x) \
780
    TWOARGS; \
781
    i = val_compare(v1, v2); \
782
    if (i==CMP_ERROR) \
783
      runtime( "Can't compare values of incompatible types" ); \
784
    res.type = T_BOOL; \
785
    res.val.i = (x); \
786
    break;
787

    
788
#define SAME(x) \
789
    TWOARGS; \
790
    i = val_same(v1, v2); \
791
    res.type = T_BOOL; \
792
    res.val.i = (x); \
793
    break;
794

    
795
  case P('!','='): SAME(!i);
796
  case P('=','='): SAME(i);
797
  case '<': COMPARE(i==-1);
798
  case P('<','='): COMPARE(i!=1);
799

    
800
  case '!':
801
    ONEARG;
802
    if (v1.type != T_BOOL)
803
      runtime( "Not applied to non-boolean" );
804
    res = v1;
805
    res.val.i = !res.val.i;
806
    break;
807

    
808
  case '~':
809
    TWOARGS;
810
    res.type = T_BOOL;
811
    res.val.i = val_in_range(v1, v2);
812
    if (res.val.i == CMP_ERROR)
813
      runtime( "~ applied on unknown type pair" );
814
    res.val.i = !!res.val.i;
815
    break;
816

    
817
  case P('!','~'):
818
    TWOARGS;
819
    res.type = T_BOOL;
820
    res.val.i = val_in_range(v1, v2);
821
    if (res.val.i == CMP_ERROR)
822
      runtime( "!~ applied on unknown type pair" );
823
    res.val.i = !res.val.i;
824
    break;
825

    
826
  case P('d','e'):
827
    ONEARG;
828
    res.type = T_BOOL;
829
    res.val.i = (v1.type != T_VOID) && !undef_value(v1);
830
    break;
831
  case 'T':
832
    ONEARG;
833
    switch (v1.type)
834
    {
835
      case T_NET:
836
        res.type = T_ENUM_NETTYPE;
837
        res.val.i = v1.val.net->type;
838
        break;
839
      default:
840
        runtime( "Can't determine type of this item" );
841
    }
842
    break;
843
  case P('I','i'):
844
    ONEARG;
845
    if (v1.type != T_IP)
846
      runtime( "IP version check needs an IP address" );
847
    res.type = T_BOOL;
848
    res.val.i = ipa_is_ip4(v1.val.ip);
849
    break;
850

    
851
  /* Set to indirect value, a1 = variable, a2 = value */
852
  case 's':
853
    ARG(v2, a2.p);
854
    sym = what->a1.p;
855
    vp = sym->def;
856
    if ((sym->class != (SYM_VARIABLE | v2.type)) && (v2.type != T_VOID))
857
    {
858
      /* IP->Quad implicit conversion */
859
      if ((sym->class == (SYM_VARIABLE | T_QUAD)) && val_is_ip4(v2))
860
      {
861
        vp->type = T_QUAD;
862
        vp->val.i = ipa_to_u32(v2.val.ip);
863
        break;
864
      }
865
      runtime( "Assigning to variable of incompatible type" );
866
    }
867
    *vp = v2;
868
    break;
869

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

    
874
    if (res.type == T_PREFIX_SET)
875
      res.val.ti = what->a2.p;
876
    else if (res.type == T_SET)
877
      res.val.t = what->a2.p;
878
    else if (res.type == T_STRING)
879
      res.val.s = what->a2.p;
880
    else
881
      res.val.i = what->a2.i;
882
    break;
883
  case 'V':
884
  case 'C':
885
    res = * ((struct f_val *) what->a1.p);
886
    break;
887
  case 'p':
888
    ONEARG;
889
    val_format(v1, &f_buf);
890
    break;
891
  case '?':        /* ? has really strange error value, so we can implement if ... else nicely :-) */
892
    ONEARG;
893
    if (v1.type != T_BOOL)
894
      runtime( "If requires boolean expression" );
895
    if (v1.val.i) {
896
      ARG(res,a2.p);
897
      res.val.i = 0;
898
    } else res.val.i = 1;
899
    res.type = T_BOOL;
900
    break;
901
  case '0':
902
    debug( "No operation\n" );
903
    break;
904
  case P('p',','):
905
    ONEARG;
906
    if (what->a2.i == F_NOP || (what->a2.i != F_NONL && what->a1.p))
907
      log_commit(*L_INFO, &f_buf);
908

    
909
    switch (what->a2.i) {
910
    case F_QUITBIRD:
911
      die( "Filter asked me to die" );
912
    case F_ACCEPT:
913
      /* Should take care about turning ACCEPT into MODIFY */
914
    case F_ERROR:
915
    case F_REJECT:        /* FIXME (noncritical) Should print complete route along with reason to reject route */
916
      res.type = T_RETURN;
917
      res.val.i = what->a2.i;
918
      return res;        /* We have to return now, no more processing. */
919
    case F_NONL:
920
    case F_NOP:
921
      break;
922
    default:
923
      bug( "unknown return type: Can't happen");
924
    }
925
    break;
926
  case 'a':        /* rta access */
927
    {
928
      ACCESS_RTE;
929
      struct rta *rta = (*f_rte)->attrs;
930
      res.type = what->aux;
931

    
932
      switch (what->a2.i)
933
      {
934
      case SA_FROM:        res.val.ip = rta->from; break;
935
      case SA_GW:        res.val.ip = rta->nh.gw; break;
936
      case SA_NET:        res.val.net = (*f_rte)->net->n.addr; break;
937
      case SA_PROTO:        res.val.s = rta->src->proto->name; break;
938
      case SA_SOURCE:        res.val.i = rta->source; break;
939
      case SA_SCOPE:        res.val.i = rta->scope; break;
940
      case SA_DEST:        res.val.i = rta->dest; break;
941
      case SA_IFNAME:        res.val.s = rta->nh.iface ? rta->nh.iface->name : ""; break;
942
      case SA_IFINDEX:        res.val.i = rta->nh.iface ? rta->nh.iface->index : 0; break;
943

    
944
      default:
945
        bug("Invalid static attribute access (%x)", res.type);
946
      }
947
    }
948
    break;
949
  case P('a','S'):
950
    ACCESS_RTE;
951
    ONEARG;
952
    if (what->aux != v1.type)
953
      runtime( "Attempt to set static attribute to incompatible type" );
954

    
955
    f_rta_cow();
956
    {
957
      struct rta *rta = (*f_rte)->attrs;
958

    
959
      switch (what->a2.i)
960
      {
961
      case SA_FROM:
962
        rta->from = v1.val.ip;
963
        break;
964

    
965
      case SA_GW:
966
        {
967
          ip_addr ip = v1.val.ip;
968
          neighbor *n = neigh_find(rta->src->proto, &ip, 0);
969
          if (!n || (n->scope == SCOPE_HOST))
970
            runtime( "Invalid gw address" );
971

    
972
          rta->dest = RTD_UNICAST;
973
          rta->nh.gw = ip;
974
          rta->nh.iface = n->iface;
975
          rta->nh.next = NULL;
976
          rta->hostentry = NULL;
977
        }
978
        break;
979

    
980
      case SA_SCOPE:
981
        rta->scope = v1.val.i;
982
        break;
983

    
984
      case SA_DEST:
985
        i = v1.val.i;
986
        if ((i != RTD_BLACKHOLE) && (i != RTD_UNREACHABLE) && (i != RTD_PROHIBIT))
987
          runtime( "Destination can be changed only to blackhole, unreachable or prohibit" );
988

    
989
        rta->dest = i;
990
        rta->nh.gw = IPA_NONE;
991
        rta->nh.iface = NULL;
992
        rta->nh.next = NULL;
993
        rta->hostentry = NULL;
994
        break;
995

    
996
      default:
997
        bug("Invalid static attribute access (%x)", res.type);
998
      }
999
    }
1000
    break;
1001
  case P('e','a'):        /* Access to extended attributes */
1002
    ACCESS_RTE;
1003
    {
1004
      eattr *e = NULL;
1005
      u16 code = what->a2.i;
1006

    
1007
      if (!(f_flags & FF_FORCE_TMPATTR))
1008
        e = ea_find((*f_rte)->attrs->eattrs, code);
1009
      if (!e)
1010
        e = ea_find((*f_tmp_attrs), code);
1011
      if ((!e) && (f_flags & FF_FORCE_TMPATTR))
1012
        e = ea_find((*f_rte)->attrs->eattrs, code);
1013

    
1014
      if (!e) {
1015
        /* A special case: undefined as_path looks like empty as_path */
1016
        if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_AS_PATH) {
1017
          res.type = T_PATH;
1018
          res.val.ad = &undef_adata;
1019
          break;
1020
        }
1021

    
1022
        /* The same special case for int_set */
1023
        if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_INT_SET) {
1024
          res.type = T_CLIST;
1025
          res.val.ad = &undef_adata;
1026
          break;
1027
        }
1028

    
1029
        /* The same special case for ec_set */
1030
        if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_EC_SET) {
1031
          res.type = T_ECLIST;
1032
          res.val.ad = &undef_adata;
1033
          break;
1034
        }
1035

    
1036
        /* The same special case for lc_set */
1037
        if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_LC_SET) {
1038
          res.type = T_LCLIST;
1039
          res.val.ad = &undef_adata;
1040
          break;
1041
        }
1042

    
1043
        /* Undefined value */
1044
        res.type = T_VOID;
1045
        break;
1046
      }
1047

    
1048
      switch (what->aux & EAF_TYPE_MASK) {
1049
      case EAF_TYPE_INT:
1050
        res.type = T_INT;
1051
        res.val.i = e->u.data;
1052
        break;
1053
      case EAF_TYPE_ROUTER_ID:
1054
        res.type = T_QUAD;
1055
        res.val.i = e->u.data;
1056
        break;
1057
      case EAF_TYPE_OPAQUE:
1058
        res.type = T_ENUM_EMPTY;
1059
        res.val.i = 0;
1060
        break;
1061
      case EAF_TYPE_IP_ADDRESS:
1062
        res.type = T_IP;
1063
        struct adata * ad = e->u.ptr;
1064
        res.val.ip = * (ip_addr *) ad->data;
1065
        break;
1066
      case EAF_TYPE_AS_PATH:
1067
        res.type = T_PATH;
1068
        res.val.ad = e->u.ptr;
1069
        break;
1070
      case EAF_TYPE_BITFIELD:
1071
        res.type = T_BOOL;
1072
        res.val.i = !!(e->u.data & BITFIELD_MASK(what));
1073
        break;
1074
      case EAF_TYPE_INT_SET:
1075
        res.type = T_CLIST;
1076
        res.val.ad = e->u.ptr;
1077
        break;
1078
      case EAF_TYPE_EC_SET:
1079
        res.type = T_ECLIST;
1080
        res.val.ad = e->u.ptr;
1081
        break;
1082
      case EAF_TYPE_LC_SET:
1083
        res.type = T_LCLIST;
1084
        res.val.ad = e->u.ptr;
1085
        break;
1086
      case EAF_TYPE_UNDEF:
1087
        res.type = T_VOID;
1088
        break;
1089
      default:
1090
        bug("Unknown type in e,a");
1091
      }
1092
    }
1093
    break;
1094
  case P('e','S'):
1095
    ACCESS_RTE;
1096
    ONEARG;
1097
    {
1098
      struct ea_list *l = lp_alloc(f_pool, sizeof(struct ea_list) + sizeof(eattr));
1099
      u16 code = what->a2.i;
1100

    
1101
      l->next = NULL;
1102
      l->flags = EALF_SORTED;
1103
      l->count = 1;
1104
      l->attrs[0].id = code;
1105
      l->attrs[0].flags = 0;
1106
      l->attrs[0].type = what->aux | EAF_ORIGINATED | EAF_FRESH;
1107

    
1108
      switch (what->aux & EAF_TYPE_MASK) {
1109
      case EAF_TYPE_INT:
1110
        // Enums are also ints, so allow them in.
1111
        if (v1.type != T_INT && (v1.type < T_ENUM_LO || v1.type > T_ENUM_HI))
1112
          runtime( "Setting int attribute to non-int value" );
1113
        l->attrs[0].u.data = v1.val.i;
1114
        break;
1115

    
1116
      case EAF_TYPE_ROUTER_ID:
1117
        /* IP->Quad implicit conversion */
1118
        if (val_is_ip4(v1)) {
1119
          l->attrs[0].u.data = ipa_to_u32(v1.val.ip);
1120
          break;
1121
        }
1122
        /* T_INT for backward compatibility */
1123
        if ((v1.type != T_QUAD) && (v1.type != T_INT))
1124
          runtime( "Setting quad attribute to non-quad value" );
1125
        l->attrs[0].u.data = v1.val.i;
1126
        break;
1127

    
1128
      case EAF_TYPE_OPAQUE:
1129
        runtime( "Setting opaque attribute is not allowed" );
1130
        break;
1131
      case EAF_TYPE_IP_ADDRESS:
1132
        if (v1.type != T_IP)
1133
          runtime( "Setting ip attribute to non-ip value" );
1134
        int len = sizeof(ip_addr);
1135
        struct adata *ad = lp_alloc(f_pool, sizeof(struct adata) + len);
1136
        ad->length = len;
1137
        (* (ip_addr *) ad->data) = v1.val.ip;
1138
        l->attrs[0].u.ptr = ad;
1139
        break;
1140
      case EAF_TYPE_AS_PATH:
1141
        if (v1.type != T_PATH)
1142
          runtime( "Setting path attribute to non-path value" );
1143
        l->attrs[0].u.ptr = v1.val.ad;
1144
        break;
1145
      case EAF_TYPE_BITFIELD:
1146
        if (v1.type != T_BOOL)
1147
          runtime( "Setting bit in bitfield attribute to non-bool value" );
1148
        {
1149
          /* First, we have to find the old value */
1150
          eattr *e = NULL;
1151
          if (!(f_flags & FF_FORCE_TMPATTR))
1152
            e = ea_find((*f_rte)->attrs->eattrs, code);
1153
          if (!e)
1154
            e = ea_find((*f_tmp_attrs), code);
1155
          if ((!e) && (f_flags & FF_FORCE_TMPATTR))
1156
            e = ea_find((*f_rte)->attrs->eattrs, code);
1157
          u32 data = e ? e->u.data : 0;
1158

    
1159
          if (v1.val.i)
1160
            l->attrs[0].u.data = data | BITFIELD_MASK(what);
1161
          else
1162
            l->attrs[0].u.data = data & ~BITFIELD_MASK(what);;
1163
        }
1164
        break;
1165
      case EAF_TYPE_INT_SET:
1166
        if (v1.type != T_CLIST)
1167
          runtime( "Setting clist attribute to non-clist value" );
1168
        l->attrs[0].u.ptr = v1.val.ad;
1169
        break;
1170
      case EAF_TYPE_EC_SET:
1171
        if (v1.type != T_ECLIST)
1172
          runtime( "Setting eclist attribute to non-eclist value" );
1173
        l->attrs[0].u.ptr = v1.val.ad;
1174
        break;
1175
      case EAF_TYPE_LC_SET:
1176
        if (v1.type != T_LCLIST)
1177
          runtime( "Setting lclist attribute to non-lclist value" );
1178
        l->attrs[0].u.ptr = v1.val.ad;
1179
        break;
1180
      case EAF_TYPE_UNDEF:
1181
        if (v1.type != T_VOID)
1182
          runtime( "Setting void attribute to non-void value" );
1183
        l->attrs[0].u.data = 0;
1184
        break;
1185
      default: bug("Unknown type in e,S");
1186
      }
1187

    
1188
      if (!(what->aux & EAF_TEMP) && (!(f_flags & FF_FORCE_TMPATTR))) {
1189
        f_rta_cow();
1190
        l->next = (*f_rte)->attrs->eattrs;
1191
        (*f_rte)->attrs->eattrs = l;
1192
      } else {
1193
        l->next = (*f_tmp_attrs);
1194
        (*f_tmp_attrs) = l;
1195
      }
1196
    }
1197
    break;
1198
  case 'P':
1199
    ACCESS_RTE;
1200
    res.type = T_INT;
1201
    res.val.i = (*f_rte)->pref;
1202
    break;
1203
  case P('P','S'):
1204
    ACCESS_RTE;
1205
    ONEARG;
1206
    if (v1.type != T_INT)
1207
      runtime( "Can't set preference to non-integer" );
1208
    if (v1.val.i > 0xFFFF)
1209
      runtime( "Setting preference value out of bounds" );
1210
    f_rte_cow();
1211
    (*f_rte)->pref = v1.val.i;
1212
    break;
1213
  case 'L':        /* Get length of */
1214
    ONEARG;
1215
    res.type = T_INT;
1216
    switch(v1.type) {
1217
    case T_NET:    res.val.i = net_pxlen(v1.val.net); break;
1218
    case T_PATH:   res.val.i = as_path_getlen(v1.val.ad); break;
1219
    case T_CLIST:  res.val.i = int_set_get_size(v1.val.ad); break;
1220
    case T_ECLIST: res.val.i = ec_set_get_size(v1.val.ad); break;
1221
    case T_LCLIST: res.val.i = lc_set_get_size(v1.val.ad); break;
1222
    default: runtime( "Prefix, path, clist or eclist expected" );
1223
    }
1224
    break;
1225
  case P('R','m'):         /* Get ROA max prefix length */
1226
    ONEARG;
1227
    if (v1.type != T_NET || !net_is_roa(v1.val.net))
1228
      runtime( "ROA expected" );
1229

    
1230
    res.type = T_INT;
1231
    res.val.i = (v1.val.net->type == NET_ROA4) ?
1232
      ((net_addr_roa4 *) v1.val.net)->max_pxlen :
1233
      ((net_addr_roa6 *) v1.val.net)->max_pxlen;
1234
    break;
1235
  case P('R','a'):         /* Get ROA ASN */
1236
    ONEARG;
1237
    if (v1.type != T_NET || !net_is_roa(v1.val.net))
1238
      runtime( "ROA expected" );
1239

    
1240
    res.type = T_INT;
1241
    res.val.i = (v1.val.net->type == NET_ROA4) ?
1242
      ((net_addr_roa4 *) v1.val.net)->asn :
1243
      ((net_addr_roa6 *) v1.val.net)->asn;
1244
    break;
1245
  case P('c','p'):        /* Convert prefix to ... */
1246
    ONEARG;
1247
    if (v1.type != T_NET)
1248
      runtime( "Prefix expected" );
1249
    res.type = T_IP;
1250
    res.val.ip = net_prefix(v1.val.net);
1251
    break;
1252
  case P('R','D'):
1253
    ONEARG;
1254
    if (v1.type != T_NET)
1255
      runtime( "Prefix expected" );
1256
    if (!net_is_vpn(v1.val.net))
1257
      runtime( "VPN address expected" );
1258
    res.type = T_RD;
1259
    res.val.ec = net_rd(v1.val.net);
1260
    break;
1261
  case P('a','f'):        /* Get first ASN from AS PATH */
1262
    ONEARG;
1263
    if (v1.type != T_PATH)
1264
      runtime( "AS path expected" );
1265

    
1266
    as = 0;
1267
    as_path_get_first(v1.val.ad, &as);
1268
    res.type = T_INT;
1269
    res.val.i = as;
1270
    break;
1271
  case P('a','l'):        /* Get last ASN from AS PATH */
1272
    ONEARG;
1273
    if (v1.type != T_PATH)
1274
      runtime( "AS path expected" );
1275

    
1276
    as = 0;
1277
    as_path_get_last(v1.val.ad, &as);
1278
    res.type = T_INT;
1279
    res.val.i = as;
1280
    break;
1281
  case P('a','L'):        /* Get last ASN from non-aggregated part of AS PATH */
1282
    ONEARG;
1283
    if (v1.type != T_PATH)
1284
      runtime( "AS path expected" );
1285

    
1286
    res.type = T_INT;
1287
    res.val.i = as_path_get_last_nonaggregated(v1.val.ad);
1288
    break;
1289
  case 'r':
1290
    ONEARG;
1291
    res = v1;
1292
    res.type |= T_RETURN;
1293
    return res;
1294
  case P('c','a'): /* CALL: this is special: if T_RETURN and returning some value, mask it out  */
1295
    ONEARG;
1296
    res = interpret(what->a2.p);
1297
    if (res.type == T_RETURN)
1298
      return res;
1299
    res.type &= ~T_RETURN;
1300
    break;
1301
  case P('c','v'):        /* Clear local variables */
1302
    for (sym = what->a1.p; sym != NULL; sym = sym->aux2)
1303
      ((struct f_val *) sym->def)->type = T_VOID;
1304
    break;
1305
  case P('S','W'):
1306
    ONEARG;
1307
    {
1308
      struct f_tree *t = find_tree(what->a2.p, v1);
1309
      if (!t) {
1310
        v1.type = T_VOID;
1311
        t = find_tree(what->a2.p, v1);
1312
        if (!t) {
1313
          debug( "No else statement?\n");
1314
          break;
1315
        }
1316
      }
1317
      /* It is actually possible to have t->data NULL */
1318

    
1319
      res = interpret(t->data);
1320
      if (res.type & T_RETURN)
1321
        return res;
1322
    }
1323
    break;
1324
  case P('i','M'): /* IP.MASK(val) */
1325
    TWOARGS;
1326
    if (v2.type != T_INT)
1327
      runtime( "Integer expected");
1328
    if (v1.type != T_IP)
1329
      runtime( "You can mask only IP addresses" );
1330

    
1331
    res.type = T_IP;
1332
    res.val.ip = ipa_is_ip4(v1.val.ip) ?
1333
      ipa_from_ip4(ip4_and(ipa_to_ip4(v1.val.ip), ip4_mkmask(v2.val.i))) :
1334
      ipa_from_ip6(ip6_and(ipa_to_ip6(v1.val.ip), ip6_mkmask(v2.val.i)));
1335
    break;
1336

    
1337
  case 'E':        /* Create empty attribute */
1338
    res.type = what->aux;
1339
    res.val.ad = adata_empty(f_pool, 0);
1340
    break;
1341
  case P('A','p'):        /* Path prepend */
1342
    TWOARGS;
1343
    if (v1.type != T_PATH)
1344
      runtime("Can't prepend to non-path");
1345
    if (v2.type != T_INT)
1346
      runtime("Can't prepend non-integer");
1347

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

    
1352
  case P('C','a'):        /* (Extended) Community list add or delete */
1353
    TWOARGS;
1354
    if (v1.type == T_PATH)
1355
    {
1356
      struct f_tree *set = NULL;
1357
      u32 key = 0;
1358
      int pos;
1359

    
1360
      if (v2.type == T_INT)
1361
        key = v2.val.i;
1362
      else if ((v2.type == T_SET) && (v2.val.t->from.type == T_INT))
1363
        set = v2.val.t;
1364
      else
1365
        runtime("Can't delete non-integer (set)");
1366

    
1367
      switch (what->aux)
1368
      {
1369
      case 'a':        runtime("Can't add to path");
1370
      case 'd':        pos = 0; break;
1371
      case 'f':        pos = 1; break;
1372
      default:        bug("unknown Ca operation");
1373
      }
1374

    
1375
      if (pos && !set)
1376
        runtime("Can't filter integer");
1377

    
1378
      res.type = T_PATH;
1379
      res.val.ad = as_path_filter(f_pool, v1.val.ad, set, key, pos);
1380
    }
1381
    else if (v1.type == T_CLIST)
1382
    {
1383
      /* Community (or cluster) list */
1384
      struct f_val dummy;
1385
      int arg_set = 0;
1386
      uint n = 0;
1387

    
1388
      if ((v2.type == T_PAIR) || (v2.type == T_QUAD))
1389
        n = v2.val.i;
1390
      /* IP->Quad implicit conversion */
1391
      else if (val_is_ip4(v2))
1392
        n = ipa_to_u32(v2.val.ip);
1393
      else if ((v2.type == T_SET) && clist_set_type(v2.val.t, &dummy))
1394
        arg_set = 1;
1395
      else if (v2.type == T_CLIST)
1396
        arg_set = 2;
1397
      else
1398
        runtime("Can't add/delete non-pair");
1399

    
1400
      res.type = T_CLIST;
1401
      switch (what->aux)
1402
      {
1403
      case 'a':
1404
        if (arg_set == 1)
1405
          runtime("Can't add set");
1406
        else if (!arg_set)
1407
          res.val.ad = int_set_add(f_pool, v1.val.ad, n);
1408
        else
1409
          res.val.ad = int_set_union(f_pool, v1.val.ad, v2.val.ad);
1410
        break;
1411

    
1412
      case 'd':
1413
        if (!arg_set)
1414
          res.val.ad = int_set_del(f_pool, v1.val.ad, n);
1415
        else
1416
          res.val.ad = clist_filter(f_pool, v1.val.ad, v2, 0);
1417
        break;
1418

    
1419
      case 'f':
1420
        if (!arg_set)
1421
          runtime("Can't filter pair");
1422
        res.val.ad = clist_filter(f_pool, v1.val.ad, v2, 1);
1423
        break;
1424

    
1425
      default:
1426
        bug("unknown Ca operation");
1427
      }
1428
    }
1429
    else if (v1.type == T_ECLIST)
1430
    {
1431
      /* Extended community list */
1432
      int arg_set = 0;
1433

    
1434
      /* v2.val is either EC or EC-set */
1435
      if ((v2.type == T_SET) && eclist_set_type(v2.val.t))
1436
        arg_set = 1;
1437
      else if (v2.type == T_ECLIST)
1438
        arg_set = 2;
1439
      else if (v2.type != T_EC)
1440
        runtime("Can't add/delete non-ec");
1441

    
1442
      res.type = T_ECLIST;
1443
      switch (what->aux)
1444
      {
1445
      case 'a':
1446
        if (arg_set == 1)
1447
          runtime("Can't add set");
1448
        else if (!arg_set)
1449
          res.val.ad = ec_set_add(f_pool, v1.val.ad, v2.val.ec);
1450
        else
1451
          res.val.ad = ec_set_union(f_pool, v1.val.ad, v2.val.ad);
1452
        break;
1453

    
1454
      case 'd':
1455
        if (!arg_set)
1456
          res.val.ad = ec_set_del(f_pool, v1.val.ad, v2.val.ec);
1457
        else
1458
          res.val.ad = eclist_filter(f_pool, v1.val.ad, v2, 0);
1459
        break;
1460

    
1461
      case 'f':
1462
        if (!arg_set)
1463
          runtime("Can't filter ec");
1464
        res.val.ad = eclist_filter(f_pool, v1.val.ad, v2, 1);
1465
        break;
1466

    
1467
      default:
1468
        bug("unknown Ca operation");
1469
      }
1470
    }
1471
    else if (v1.type == T_LCLIST)
1472
    {
1473
      /* Large community list */
1474
      int arg_set = 0;
1475

    
1476
      /* v2.val is either LC or LC-set */
1477
      if ((v2.type == T_SET) && lclist_set_type(v2.val.t))
1478
        arg_set = 1;
1479
      else if (v2.type == T_LCLIST)
1480
        arg_set = 2;
1481
      else if (v2.type != T_LC)
1482
        runtime("Can't add/delete non-lc");
1483

    
1484
      res.type = T_LCLIST;
1485
      switch (what->aux)
1486
      {
1487
      case 'a':
1488
        if (arg_set == 1)
1489
          runtime("Can't add set");
1490
        else if (!arg_set)
1491
          res.val.ad = lc_set_add(f_pool, v1.val.ad, v2.val.lc);
1492
        else
1493
          res.val.ad = lc_set_union(f_pool, v1.val.ad, v2.val.ad);
1494
        break;
1495

    
1496
      case 'd':
1497
        if (!arg_set)
1498
          res.val.ad = lc_set_del(f_pool, v1.val.ad, v2.val.lc);
1499
        else
1500
          res.val.ad = lclist_filter(f_pool, v1.val.ad, v2, 0);
1501
        break;
1502

    
1503
      case 'f':
1504
        if (!arg_set)
1505
          runtime("Can't filter lc");
1506
        res.val.ad = lclist_filter(f_pool, v1.val.ad, v2, 1);
1507
        break;
1508

    
1509
      default:
1510
        bug("unknown Ca operation");
1511
      }
1512
    }
1513
    else
1514
      runtime("Can't add/delete to non-[e|l]clist");
1515

    
1516
    break;
1517

    
1518

    
1519
  case P('R','C'):        /* ROA Check */
1520
    if (what->arg1)
1521
    {
1522
      TWOARGS;
1523
      if ((v1.type != T_NET) || (v2.type != T_INT))
1524
        runtime("Invalid argument to roa_check()");
1525

    
1526
      as = v2.val.i;
1527
    }
1528
    else
1529
    {
1530
      ACCESS_RTE;
1531
      v1.val.net = (*f_rte)->net->n.addr;
1532

    
1533
      /* We ignore temporary attributes, probably not a problem here */
1534
      /* 0x02 is a value of BA_AS_PATH, we don't want to include BGP headers */
1535
      eattr *e = ea_find((*f_rte)->attrs->eattrs, EA_CODE(EAP_BGP, 0x02));
1536

    
1537
      if (!e || e->type != EAF_TYPE_AS_PATH)
1538
        runtime("Missing AS_PATH attribute");
1539

    
1540
      as_path_get_last(e->u.ptr, &as);
1541
    }
1542

    
1543
    struct rtable *table = ((struct f_inst_roa_check *) what)->rtc->table;
1544
    if (!table)
1545
      runtime("Missing ROA table");
1546

    
1547
    if (table->addr_type != NET_ROA4 && table->addr_type != NET_ROA6)
1548
      runtime("Table type must be either ROA4 or ROA6");
1549

    
1550
    res.type = T_ENUM_ROA;
1551

    
1552
    if (table->addr_type != (v1.val.net->type == NET_IP4 ? NET_ROA4 : NET_ROA6))
1553
      res.val.i = ROA_UNKNOWN; /* Prefix and table type mismatch */
1554
    else
1555
      res.val.i = net_roa_check(table, v1.val.net, as);
1556

    
1557
    break;
1558

    
1559
  case P('f','m'):        /* Format */
1560
    ONEARG;
1561

    
1562
    res.type = T_STRING;
1563
    res.val.s = val_format_str(v1);
1564
    break;
1565

    
1566
  case P('a','s'):        /* Birdtest Assert */
1567
    ONEARG;
1568

    
1569
    if (v1.type != T_BOOL)
1570
      runtime("Should be boolean value");
1571

    
1572
    res.type = v1.type;
1573
    res.val = v1.val;
1574

    
1575
    CALL(bt_assert_hook, res.val.i, what);
1576
    break;
1577

    
1578
  default:
1579
    bug( "Unknown instruction %d (%c)", what->code, what->code & 0xff);
1580
  }
1581
  if (what->next)
1582
    return interpret(what->next);
1583
  return res;
1584
}
1585

    
1586
#undef ARG
1587
#define ARG(x,y) \
1588
        if (!i_same(f1->y, f2->y)) \
1589
                return 0;
1590

    
1591
#define ONEARG ARG(v1, a1.p)
1592
#define TWOARGS ARG(v1, a1.p) \
1593
                ARG(v2, a2.p)
1594

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

    
1597
/*
1598
 * i_same - function that does real comparing of instruction trees, you should call filter_same from outside
1599
 */
1600
int
1601
i_same(struct f_inst *f1, struct f_inst *f2)
1602
{
1603
  if ((!!f1) != (!!f2))
1604
    return 0;
1605
  if (!f1)
1606
    return 1;
1607
  if (f1->aux != f2->aux)
1608
    return 0;
1609
  if (f1->code != f2->code)
1610
    return 0;
1611
  if (f1 == f2)                /* It looks strange, but it is possible with call rewriting trickery */
1612
    return 1;
1613

    
1614
  switch(f1->code) {
1615
  case ',': /* fall through */
1616
  case '+':
1617
  case '-':
1618
  case '*':
1619
  case '/':
1620
  case '|':
1621
  case '&':
1622
  case P('m','p'):
1623
  case P('m','c'):
1624
  case P('!','='):
1625
  case P('=','='):
1626
  case '<':
1627
  case P('<','='): TWOARGS; break;
1628

    
1629
  case '!': ONEARG; break;
1630
  case P('!', '~'):
1631
  case '~': TWOARGS; break;
1632
  case P('d','e'): ONEARG; break;
1633
  case 'T': ONEARG; break;
1634
  case P('n','T'): break;
1635

    
1636
  case P('m','l'):
1637
    TWOARGS;
1638
    if (!i_same(INST3(f1).p, INST3(f2).p))
1639
      return 0;
1640
    break;
1641

    
1642
  case 's':
1643
    ARG(v2, a2.p);
1644
    {
1645
      struct symbol *s1, *s2;
1646
      s1 = f1->a1.p;
1647
      s2 = f2->a1.p;
1648
      if (strcmp(s1->name, s2->name))
1649
        return 0;
1650
      if (s1->class != s2->class)
1651
        return 0;
1652
    }
1653
    break;
1654

    
1655
  case 'c':
1656
    switch (f1->aux) {
1657

    
1658
    case T_PREFIX_SET:
1659
      if (!trie_same(f1->a2.p, f2->a2.p))
1660
        return 0;
1661
      break;
1662

    
1663
    case T_SET:
1664
      if (!same_tree(f1->a2.p, f2->a2.p))
1665
        return 0;
1666
      break;
1667

    
1668
    case T_STRING:
1669
      if (strcmp(f1->a2.p, f2->a2.p))
1670
        return 0;
1671
      break;
1672

    
1673
    default:
1674
      A2_SAME;
1675
    }
1676
    break;
1677

    
1678
  case 'C':
1679
    if (!val_same(* (struct f_val *) f1->a1.p, * (struct f_val *) f2->a1.p))
1680
      return 0;
1681
    break;
1682

    
1683
  case 'V':
1684
    if (strcmp((char *) f1->a2.p, (char *) f2->a2.p))
1685
      return 0;
1686
    break;
1687
  case 'p': case 'L': ONEARG; break;
1688
  case '?': TWOARGS; break;
1689
  case '0': case 'E': break;
1690
  case P('p',','): ONEARG; A2_SAME; break;
1691
  case 'P':
1692
  case 'a': A2_SAME; break;
1693
  case P('e','a'): A2_SAME; break;
1694
  case P('P','S'):
1695
  case P('a','S'):
1696
  case P('e','S'): ONEARG; A2_SAME; break;
1697

    
1698
  case 'r': ONEARG; break;
1699
  case P('c','p'): ONEARG; break;
1700
  case P('R','D'): ONEARG; break;
1701
  case P('c','a'): /* Call rewriting trickery to avoid exponential behaviour */
1702
             ONEARG;
1703
             if (!i_same(f1->a2.p, f2->a2.p))
1704
               return 0;
1705
             f2->a2.p = f1->a2.p;
1706
             break;
1707
  case P('c','v'): break; /* internal instruction */
1708
  case P('S','W'): ONEARG; if (!same_tree(f1->a2.p, f2->a2.p)) return 0; break;
1709
  case P('i','M'): TWOARGS; break;
1710
  case P('A','p'): TWOARGS; break;
1711
  case P('C','a'): TWOARGS; break;
1712
  case P('a','f'):
1713
  case P('a','l'):
1714
  case P('a','L'): ONEARG; break;
1715
  case P('R','C'):
1716
    TWOARGS;
1717
    /* Does not really make sense - ROA check results may change anyway */
1718
    if (strcmp(((struct f_inst_roa_check *) f1)->rtc->name,
1719
               ((struct f_inst_roa_check *) f2)->rtc->name))
1720
      return 0;
1721
    break;
1722
  default:
1723
    bug( "Unknown instruction %d in same (%c)", f1->code, f1->code & 0xff);
1724
  }
1725
  return i_same(f1->next, f2->next);
1726
}
1727

    
1728
/**
1729
 * f_run - run a filter for a route
1730
 * @filter: filter to run
1731
 * @rte: route being filtered, may be modified
1732
 * @tmp_attrs: temporary attributes, prepared by caller or generated by f_run()
1733
 * @tmp_pool: all filter allocations go from this pool
1734
 * @flags: flags
1735
 *
1736
 * If filter needs to modify the route, there are several
1737
 * posibilities. @rte might be read-only (with REF_COW flag), in that
1738
 * case rw copy is obtained by rte_cow() and @rte is replaced. If
1739
 * @rte is originally rw, it may be directly modified (and it is never
1740
 * copied).
1741
 *
1742
 * The returned rte may reuse the (possibly cached, cloned) rta, or
1743
 * (if rta was modificied) contains a modified uncached rta, which
1744
 * uses parts allocated from @tmp_pool and parts shared from original
1745
 * rta. There is one exception - if @rte is rw but contains a cached
1746
 * rta and that is modified, rta in returned rte is also cached.
1747
 *
1748
 * Ownership of cached rtas is consistent with rte, i.e.
1749
 * if a new rte is returned, it has its own clone of cached rta
1750
 * (and cached rta of read-only source rte is intact), if rte is
1751
 * modified in place, old cached rta is possibly freed.
1752
 */
1753
int
1754
f_run(struct filter *filter, struct rte **rte, struct ea_list **tmp_attrs, struct linpool *tmp_pool, int flags)
1755
{
1756
  if (filter == FILTER_ACCEPT)
1757
    return F_ACCEPT;
1758

    
1759
  if (filter == FILTER_REJECT)
1760
    return F_REJECT;
1761

    
1762
  int rte_cow = ((*rte)->flags & REF_COW);
1763
  DBG( "Running filter `%s'...", filter->name );
1764

    
1765
  f_rte = rte;
1766
  f_old_rta = NULL;
1767
  f_tmp_attrs = tmp_attrs;
1768
  f_pool = tmp_pool;
1769
  f_flags = flags;
1770

    
1771
  LOG_BUFFER_INIT(f_buf);
1772

    
1773
  struct f_val res = interpret(filter->root);
1774

    
1775
  if (f_old_rta) {
1776
    /*
1777
     * Cached rta was modified and f_rte contains now an uncached one,
1778
     * sharing some part with the cached one. The cached rta should
1779
     * be freed (if rte was originally COW, f_old_rta is a clone
1780
     * obtained during rte_cow()).
1781
     *
1782
     * This also implements the exception mentioned in f_run()
1783
     * description. The reason for this is that rta reuses parts of
1784
     * f_old_rta, and these may be freed during rta_free(f_old_rta).
1785
     * This is not the problem if rte was COW, because original rte
1786
     * also holds the same rta.
1787
     */
1788
    if (!rte_cow)
1789
      (*f_rte)->attrs = rta_lookup((*f_rte)->attrs);
1790

    
1791
    rta_free(f_old_rta);
1792
  }
1793

    
1794

    
1795
  if (res.type != T_RETURN) {
1796
    log_rl(&rl_runtime_err, L_ERR "Filter %s did not return accept nor reject. Make up your mind", filter->name);
1797
    return F_ERROR;
1798
  }
1799
  DBG( "done (%u)\n", res.val.i );
1800
  return res.val.i;
1801
}
1802

    
1803
/* TODO: perhaps we could integrate f_eval(), f_eval_rte() and f_run() */
1804

    
1805
struct f_val
1806
f_eval_rte(struct f_inst *expr, struct rte **rte, struct linpool *tmp_pool)
1807
{
1808
  struct ea_list *tmp_attrs = NULL;
1809

    
1810
  f_rte = rte;
1811
  f_old_rta = NULL;
1812
  f_tmp_attrs = &tmp_attrs;
1813
  f_pool = tmp_pool;
1814
  f_flags = 0;
1815

    
1816
  LOG_BUFFER_INIT(f_buf);
1817

    
1818
  /* Note that in this function we assume that rte->attrs is private / uncached */
1819
  struct f_val res = interpret(expr);
1820

    
1821
  /* Hack to include EAF_TEMP attributes to the main list */
1822
  (*rte)->attrs->eattrs = ea_append(tmp_attrs, (*rte)->attrs->eattrs);
1823

    
1824
  return res;
1825
}
1826

    
1827
struct f_val
1828
f_eval(struct f_inst *expr, struct linpool *tmp_pool)
1829
{
1830
  f_flags = 0;
1831
  f_tmp_attrs = NULL;
1832
  f_rte = NULL;
1833
  f_pool = tmp_pool;
1834

    
1835
  LOG_BUFFER_INIT(f_buf);
1836

    
1837
  return interpret(expr);
1838
}
1839

    
1840
uint
1841
f_eval_int(struct f_inst *expr)
1842
{
1843
  /* Called independently in parse-time to eval expressions */
1844
  struct f_val res = f_eval(expr, cfg_mem);
1845

    
1846
  if (res.type != T_INT)
1847
    cf_error("Integer expression expected");
1848

    
1849
  return res.val.i;
1850
}
1851

    
1852
u32
1853
f_eval_asn(struct f_inst *expr)
1854
{
1855
  /* Called as a part of another interpret call, therefore no log_reset() */
1856
  struct f_val res = interpret(expr);
1857
  return (res.type == T_INT) ? res.val.i : 0;
1858
}
1859

    
1860
/**
1861
 * filter_same - compare two filters
1862
 * @new: first filter to be compared
1863
 * @old: second filter to be compared, notice that this filter is
1864
 * damaged while comparing.
1865
 *
1866
 * Returns 1 in case filters are same, otherwise 0. If there are
1867
 * underlying bugs, it will rather say 0 on same filters than say
1868
 * 1 on different.
1869
 */
1870
int
1871
filter_same(struct filter *new, struct filter *old)
1872
{
1873
  if (old == new)        /* Handle FILTER_ACCEPT and FILTER_REJECT */
1874
    return 1;
1875
  if (old == FILTER_ACCEPT || old == FILTER_REJECT ||
1876
      new == FILTER_ACCEPT || new == FILTER_REJECT)
1877
    return 0;
1878
  return i_same(new->root, old->root);
1879
}