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