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