filter/filter.c

   1 /*
   2  *      Filters: utility functions
   3  *
   4  *      Copyright 1998 Pavel Machek <pavel@ucw.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  *
   8  */
   9
  10 /**
  11  * DOC: Filters
  12  *
  13  * You can find sources of the filter language in |filter/|
  14  * directory. File |filter/config.Y| contains filter grammar and basically translates
  15  * the source from user into a tree of &f_inst structures. These trees are
  16  * later interpreted using code in |filter/filter.c|.
  17  *
  18  * A filter is represented by a tree of &f_inst structures, later translated
  19  * into lists called &f_line. All the instructions are defined and documented
  20  * in |filter/f-inst.c| definition file.
  21  *
  22  * Filters use a &f_val structure for their data. Each &f_val
  23  * contains type and value (types are constants prefixed with %T_).
  24  * Look into |filter/data.h| for more information and appropriate calls.
  25  */
  26
  27 #undef LOCAL_DEBUG
  28
  29 #include "nest/bird.h"
  30 #include "lib/lists.h"
  31 #include "lib/resource.h"
  32 #include "lib/socket.h"
  33 #include "lib/string.h"
  34 #include "lib/unaligned.h"
  35 #include "lib/ip.h"
  36 #include "lib/net.h"
  37 #include "lib/flowspec.h"
  38 #include "nest/route.h"
  39 #include "nest/protocol.h"
  40 #include "nest/iface.h"
  41 #include "nest/attrs.h"
  42 #include "conf/conf.h"
  43 #include "filter/filter.h"
  44 #include "filter/f-inst.h"
  45 #include "filter/data.h"
  46
  47
  48 /* Exception bits */
  49 enum f_exception {
  50   FE_RETURN = 0x1,
  51 };
  52
  53
  54 struct filter_stack {
  55   /* Value stack for execution */
  56 #define F_VAL_STACK_MAX 4096
  57   uint vcnt;                            /* Current value stack size; 0 for empty */
  58   uint ecnt;                            /* Current execute stack size; 0 for empty */
  59
  60   struct f_val vstk[F_VAL_STACK_MAX];   /* The stack itself */
  61
  62   /* Instruction stack for execution */
  63 #define F_EXEC_STACK_MAX 4096
  64   struct {
  65     const struct f_line *line;          /* The line that is being executed */
  66     uint pos;                           /* Instruction index in the line */
  67     uint ventry;                        /* Value stack depth on entry */
  68     uint vbase;                         /* Where to index variable positions from */
  69     enum f_exception emask;             /* Exception mask */
  70   } estk[F_EXEC_STACK_MAX];
  71 };
  72
  73 /* Internal filter state, to be allocated on stack when executing filters */
  74 struct filter_state {
  75   /* Stacks needed for execution */
  76   struct filter_stack *stack;
  77
  78   /* The route we are processing. This may be NULL to indicate no route available. */
  79   struct rte **rte;
  80
  81   /* The old rta to be freed after filters are done. */
  82   struct rta *old_rta;
  83
  84   /* Cached pointer to ea_list */
  85   struct ea_list **eattrs;
  86
  87   /* Linpool for adata allocation */
  88   struct linpool *pool;
  89
  90   /* Buffer for log output */
  91   struct buffer buf;
  92
  93   /* Filter execution flags */
  94   int flags;
  95 };
  96
  97 _Thread_local static struct filter_state filter_state;
  98 _Thread_local static struct filter_stack filter_stack;
  99
 100 void (*bt_assert_hook)(int result, const struct f_line_item *assert);
 101
 102 static inline void f_cache_eattrs(struct filter_state *fs)
 103 {
 104   fs->eattrs = &((*fs->rte)->attrs->eattrs);
 105 }
 106
 107 static inline void f_rte_cow(struct filter_state *fs)
 108 {
 109   if (!((*fs->rte)->flags & REF_COW))
 110     return;
 111
 112   *fs->rte = rte_cow(*fs->rte);
 113 }
 114
 115 /*
 116  * rta_cow - prepare rta for modification by filter
 117  */
 118 static void
 119 f_rta_cow(struct filter_state *fs)
 120 {
 121   if (!rta_is_cached((*fs->rte)->attrs))
 122     return;
 123
 124   /* Prepare to modify rte */
 125   f_rte_cow(fs);
 126
 127   /* Store old rta to free it later, it stores reference from rte_cow() */
 128   fs->old_rta = (*fs->rte)->attrs;
 129
 130   /*
 131    * Get shallow copy of rta. Fields eattrs and nexthops of rta are shared
 132    * with fs->old_rta (they will be copied when the cached rta will be obtained
 133    * at the end of f_run()), also the lock of hostentry is inherited (we
 134    * suppose hostentry is not changed by filters).
 135    */
 136   (*fs->rte)->attrs = rta_do_cow((*fs->rte)->attrs, fs->pool);
 137
 138   /* Re-cache the ea_list */
 139   f_cache_eattrs(fs);
 140 }
 141
 142 static struct tbf rl_runtime_err = TBF_DEFAULT_LOG_LIMITS;
 143
 144 /**
 145  * interpret
 146  * @fs: filter state
 147  * @what: filter to interpret
 148  *
 149  * Interpret given tree of filter instructions. This is core function
 150  * of filter system and does all the hard work.
 151  *
 152  * Each instruction has 4 fields: code (which is instruction code),
 153  * aux (which is extension to instruction code, typically type),
 154  * arg1 and arg2 - arguments. Depending on instruction, arguments
 155  * are either integers, or pointers to instruction trees. Common
 156  * instructions like +, that have two expressions as arguments use
 157  * TWOARGS macro to get both of them evaluated.
 158  */
 159 static enum filter_return
 160 interpret(struct filter_state *fs, const struct f_line *line, struct f_val *val)
 161 {
 162   /* No arguments allowed */
 163   ASSERT(line->args == 0);
 164
 165   /* Initialize the filter stack */
 166   struct filter_stack *fstk = fs->stack;
 167
 168   fstk->vcnt = line->vars;
 169   memset(fstk->vstk, 0, sizeof(struct f_val) * line->vars);
 170
 171   /* The same as with the value stack. Not resetting the stack for performance reasons. */
 172   fstk->ecnt = 1;
 173   fstk->estk[0].line = line;
 174   fstk->estk[0].pos = 0;
 175
 176 #define curline fstk->estk[fstk->ecnt-1]
 177
 178 #ifdef LOCAL_DEBUG
 179   debug("Interpreting line.");
 180   f_dump_line(line, 1);
 181 #endif
 182
 183   while (fstk->ecnt > 0) {
 184     while (curline.pos < curline.line->len) {
 185       const struct f_line_item *what = &(curline.line->items[curline.pos++]);
 186
 187       switch (what->fi_code) {
 188 #define res fstk->vstk[fstk->vcnt]
 189 #define vv(i) fstk->vstk[fstk->vcnt + (i)]
 190 #define v1 vv(0)
 191 #define v2 vv(1)
 192 #define v3 vv(2)
 193
 194 #define runtime(fmt, ...) do { \
 195   if (!(fs->flags & FF_SILENT)) \
 196     log_rl(&rl_runtime_err, L_ERR "filters, line %d: " fmt, what->lineno, ##__VA_ARGS__); \
 197   return F_ERROR; \
 198 } while(0)
 199
 200 #define falloc(size)  lp_alloc(fs->pool, size)
 201 #define fpool fs->pool
 202
 203 #define ACCESS_EATTRS do { if (!fs->eattrs) f_cache_eattrs(fs); } while (0)
 204
 205 #include "filter/inst-interpret.c"
 206 #undef res
 207 #undef v1
 208 #undef v2
 209 #undef v3
 210 #undef runtime
 211 #undef falloc
 212 #undef fpool
 213 #undef ACCESS_EATTRS
 214       }
 215     }
 216
 217     /* End of current line. Drop local variables before exiting. */
 218     fstk->vcnt -= curline.line->vars;
 219     fstk->vcnt -= curline.line->args;
 220     fstk->ecnt--;
 221   }
 222
 223   if (fstk->vcnt == 0) {
 224     if (val) {
 225       log_rl(&rl_runtime_err, L_ERR "filters: No value left on stack");
 226       return F_ERROR;
 227     }
 228     return F_NOP;
 229   }
 230
 231   if (val && (fstk->vcnt == 1)) {
 232     *val = fstk->vstk[0];
 233     return F_NOP;
 234   }
 235
 236   log_rl(&rl_runtime_err, L_ERR "Too many items left on stack: %u", fstk->vcnt);
 237   return F_ERROR;
 238 }
 239
 240
 241 /**
 242  * f_run - run a filter for a route
 243  * @filter: filter to run
 244  * @rte: route being filtered, may be modified
 245  * @tmp_pool: all filter allocations go from this pool
 246  * @flags: flags
 247  *
 248  * If filter needs to modify the route, there are several
 249  * posibilities. @rte might be read-only (with REF_COW flag), in that
 250  * case rw copy is obtained by rte_cow() and @rte is replaced. If
 251  * @rte is originally rw, it may be directly modified (and it is never
 252  * copied).
 253  *
 254  * The returned rte may reuse the (possibly cached, cloned) rta, or
 255  * (if rta was modified) contains a modified uncached rta, which
 256  * uses parts allocated from @tmp_pool and parts shared from original
 257  * rta. There is one exception - if @rte is rw but contains a cached
 258  * rta and that is modified, rta in returned rte is also cached.
 259  *
 260  * Ownership of cached rtas is consistent with rte, i.e.
 261  * if a new rte is returned, it has its own clone of cached rta
 262  * (and cached rta of read-only source rte is intact), if rte is
 263  * modified in place, old cached rta is possibly freed.
 264  */
 265 enum filter_return
 266 f_run(const struct filter *filter, struct rte **rte, struct linpool *tmp_pool, int flags)
 267 {
 268   if (filter == FILTER_ACCEPT)
 269     return F_ACCEPT;
 270
 271   if (filter == FILTER_REJECT)
 272     return F_REJECT;
 273
 274   int rte_cow = ((*rte)->flags & REF_COW);
 275   DBG( "Running filter `%s'...", filter->name );
 276
 277   /* Initialize the filter state */
 278   filter_state = (struct filter_state) {
 279     .stack = &filter_stack,
 280     .rte = rte,
 281     .pool = tmp_pool,
 282     .flags = flags,
 283   };
 284
 285   LOG_BUFFER_INIT(filter_state.buf);
 286
 287   /* Run the interpreter itself */
 288   enum filter_return fret = interpret(&filter_state, filter->root, NULL);
 289
 290   if (filter_state.old_rta) {
 291     /*
 292      * Cached rta was modified and filter_state->rte contains now an uncached one,
 293      * sharing some part with the cached one. The cached rta should
 294      * be freed (if rte was originally COW, filter_state->old_rta is a clone
 295      * obtained during rte_cow()).
 296      *
 297      * This also implements the exception mentioned in f_run()
 298      * description. The reason for this is that rta reuses parts of
 299      * filter_state->old_rta, and these may be freed during rta_free(filter_state->old_rta).
 300      * This is not the problem if rte was COW, because original rte
 301      * also holds the same rta.
 302      */
 303     if (!rte_cow) {
 304       /* Cache the new attrs */
 305       (*filter_state.rte)->attrs = rta_lookup((*filter_state.rte)->attrs);
 306
 307       /* Drop cached ea_list pointer */
 308       filter_state.eattrs = NULL;
 309     }
 310
 311     /* Uncache the old attrs and drop the pointer as it is invalid now. */
 312     rta_free(filter_state.old_rta);
 313     filter_state.old_rta = NULL;
 314   }
 315
 316   /* Process the filter output, log it and return */
 317   if (fret < F_ACCEPT) {
 318     if (!(filter_state.flags & FF_SILENT))
 319       log_rl(&rl_runtime_err, L_ERR "Filter %s did not return accept nor reject. Make up your mind", filter_name(filter));
 320     return F_ERROR;
 321   }
 322   DBG( "done (%u)\n", res.val.i );
 323   return fret;
 324 }
 325
 326 /**
 327  * f_eval_rte - run a filter line for an uncached route
 328  * @expr: filter line to run
 329  * @rte: route being filtered, may be modified
 330  * @tmp_pool: all filter allocations go from this pool
 331  *
 332  * This specific filter entry point runs the given filter line
 333  * (which must not have any arguments) on the given route.
 334  *
 335  * The route MUST NOT have REF_COW set and its attributes MUST NOT
 336  * be cached by rta_lookup().
 337  */
 338
 339 enum filter_return
 340 f_eval_rte(const struct f_line *expr, struct rte **rte, struct linpool *tmp_pool)
 341 {
 342   filter_state = (struct filter_state) {
 343     .stack = &filter_stack,
 344     .rte = rte,
 345     .pool = tmp_pool,
 346   };
 347
 348   LOG_BUFFER_INIT(filter_state.buf);
 349
 350   ASSERT(!((*rte)->flags & REF_COW));
 351   ASSERT(!rta_is_cached((*rte)->attrs));
 352
 353   return interpret(&filter_state, expr, NULL);
 354 }
 355
 356 /*
 357  * f_eval - get a value of a term
 358  * @expr: filter line containing the term
 359  * @tmp_pool: long data may get allocated from this pool
 360  * @pres: here the output will be stored
 361  */
 362 enum filter_return
 363 f_eval(const struct f_line *expr, struct linpool *tmp_pool, struct f_val *pres)
 364 {
 365   filter_state = (struct filter_state) {
 366     .stack = &filter_stack,
 367     .pool = tmp_pool,
 368   };
 369
 370   LOG_BUFFER_INIT(filter_state.buf);
 371
 372   enum filter_return fret = interpret(&filter_state, expr, pres);
 373   return fret;
 374 }
 375
 376 /*
 377  * f_eval_int - get an integer value of a term
 378  * Called internally from the config parser, uses its internal memory pool
 379  * for allocations. Do not call in other cases.
 380  */
 381 uint
 382 f_eval_int(const struct f_line *expr)
 383 {
 384   /* Called independently in parse-time to eval expressions */
 385   filter_state = (struct filter_state) {
 386     .stack = &filter_stack,
 387     .pool = cfg_mem,
 388   };
 389
 390   struct f_val val;
 391
 392   LOG_BUFFER_INIT(filter_state.buf);
 393
 394   if (interpret(&filter_state, expr, &val) > F_RETURN)
 395     cf_error("Runtime error while evaluating expression; see log for details");
 396
 397   if (val.type != T_INT)
 398     cf_error("Integer expression expected");
 399
 400   return val.val.i;
 401 }
 402
 403 /*
 404  * f_eval_buf - get a value of a term and print it to the supplied buffer
 405  */
 406 enum filter_return
 407 f_eval_buf(const struct f_line *expr, struct linpool *tmp_pool, buffer *buf)
 408 {
 409   struct f_val val;
 410   enum filter_return fret = f_eval(expr, tmp_pool, &val);
 411   if (fret <= F_RETURN)
 412     val_format(&val, buf);
 413   return fret;
 414 }
 415
 416 /**
 417  * filter_same - compare two filters
 418  * @new: first filter to be compared
 419  * @old: second filter to be compared
 420  *
 421  * Returns 1 in case filters are same, otherwise 0. If there are
 422  * underlying bugs, it will rather say 0 on same filters than say
 423  * 1 on different.
 424  */
 425 int
 426 filter_same(const struct filter *new, const struct filter *old)
 427 {
 428   if (old == new)       /* Handle FILTER_ACCEPT and FILTER_REJECT */
 429     return 1;
 430   if (old == FILTER_ACCEPT || old == FILTER_REJECT ||
 431       new == FILTER_ACCEPT || new == FILTER_REJECT)
 432     return 0;
 433
 434   if ((!old->sym) && (!new->sym))
 435     return f_same(new->root, old->root);
 436
 437   if ((!old->sym) || (!new->sym))
 438     return 0;
 439
 440   if (strcmp(old->sym->name, new->sym->name))
 441     return 0;
 442
 443   return new->sym->flags & SYM_FLAG_SAME;
 444 }
 445
 446 /**
 447  * filter_commit - do filter comparisons on all the named functions and filters
 448  */
 449 void
 450 filter_commit(struct config *new, struct config *old)
 451 {
 452   if (!old)
 453     return;
 454
 455   struct symbol *sym, *osym;
 456   WALK_LIST(sym, new->symbols)
 457     switch (sym->class) {
 458       case SYM_FUNCTION:
 459         if ((osym = cf_find_symbol(old, sym->name)) &&
 460             (osym->class == SYM_FUNCTION) &&
 461             f_same(sym->function, osym->function))
 462           sym->flags |= SYM_FLAG_SAME;
 463         else
 464           sym->flags &= ~SYM_FLAG_SAME;
 465         break;
 466
 467       case SYM_FILTER:
 468         if ((osym = cf_find_symbol(old, sym->name)) &&
 469             (osym->class == SYM_FILTER) &&
 470             f_same(sym->filter->root, osym->filter->root))
 471           sym->flags |= SYM_FLAG_SAME;
 472         else
 473           sym->flags &= ~SYM_FLAG_SAME;
 474         break;
 475     }
 476 }
 477
 478 void filters_dump_all(void)
 479 {
 480   struct symbol *sym;
 481   WALK_LIST(sym, config->symbols) {
 482     switch (sym->class) {
 483       case SYM_FILTER:
 484         debug("Named filter %s:\n", sym->name);
 485         f_dump_line(sym->filter->root, 1);
 486         break;
 487       case SYM_FUNCTION:
 488         debug("Function %s:\n", sym->name);
 489         f_dump_line(sym->function, 1);
 490         break;
 491       case SYM_PROTO:
 492         {
 493           debug("Protocol %s:\n", sym->name);
 494           struct channel *c;
 495           WALK_LIST(c, sym->proto->proto->channels) {
 496             debug(" Channel %s (%s) IMPORT", c->name, net_label[c->net_type]);
 497             if (c->in_filter == FILTER_ACCEPT)
 498               debug(" ALL\n");
 499             else if (c->in_filter == FILTER_REJECT)
 500               debug(" NONE\n");
 501             else if (c->in_filter == FILTER_UNDEF)
 502               debug(" UNDEF\n");
 503             else if (c->in_filter->sym) {
 504               ASSERT(c->in_filter->sym->filter == c->in_filter);
 505               debug(" named filter %s\n", c->in_filter->sym->name);
 506             } else {
 507               debug("\n");
 508               f_dump_line(c->in_filter->root, 2);
 509             }
 510           }
 511         }
 512     }
 513   }
 514 }