1: /*
2: * Filters: utility functions
3: *
4: * (c) 1998 Pavel Machek <pavel@ucw.cz>
5: * (c) 2019 Maria Matejka <mq@jmq.cz>
6: *
7: * Can be freely distributed and used under the terms of the GNU GPL.
8: *
9: */
10:
11: #include "nest/bird.h"
12: #include "lib/lists.h"
13: #include "lib/resource.h"
14: #include "lib/socket.h"
15: #include "lib/string.h"
16: #include "lib/unaligned.h"
17: #include "lib/net.h"
18: #include "lib/ip.h"
19: #include "nest/route.h"
20: #include "nest/protocol.h"
21: #include "nest/iface.h"
22: #include "nest/attrs.h"
23: #include "conf/conf.h"
24: #include "filter/filter.h"
25: #include "filter/f-inst.h"
26: #include "filter/data.h"
27:
28: const struct f_val f_const_empty_path = {
29: .type = T_PATH,
30: .val.ad = &null_adata,
31: }, f_const_empty_clist = {
32: .type = T_CLIST,
33: .val.ad = &null_adata,
34: }, f_const_empty_eclist = {
35: .type = T_ECLIST,
36: .val.ad = &null_adata,
37: }, f_const_empty_lclist = {
38: .type = T_LCLIST,
39: .val.ad = &null_adata,
40: };
41:
42: static struct adata *
43: adata_empty(struct linpool *pool, int l)
44: {
45: struct adata *res = lp_alloc(pool, sizeof(struct adata) + l);
46: res->length = l;
47: return res;
48: }
49:
50: static void
51: pm_format(const struct f_path_mask *p, buffer *buf)
52: {
53: buffer_puts(buf, "[= ");
54:
55: for (uint i=0; i<p->len; i++)
56: {
57: switch(p->item[i].kind)
58: {
59: case PM_ASN:
60: buffer_print(buf, "%u ", p->item[i].asn);
61: break;
62:
63: case PM_QUESTION:
64: buffer_puts(buf, "? ");
65: break;
66:
67: case PM_ASTERISK:
68: buffer_puts(buf, "* ");
69: break;
70:
71: case PM_ASN_RANGE:
72: buffer_print(buf, "%u..%u ", p->item[i].from, p->item[i].to);
73: break;
74:
75: case PM_ASN_EXPR:
76: ASSERT(0);
77: }
78:
79: }
80:
81: buffer_puts(buf, "=]");
82: }
83:
84: static inline int
85: lcomm_cmp(lcomm v1, lcomm v2)
86: {
87: if (v1.asn != v2.asn)
88: return (v1.asn > v2.asn) ? 1 : -1;
89: if (v1.ldp1 != v2.ldp1)
90: return (v1.ldp1 > v2.ldp1) ? 1 : -1;
91: if (v1.ldp2 != v2.ldp2)
92: return (v1.ldp2 > v2.ldp2) ? 1 : -1;
93: return 0;
94: }
95:
96: /**
97: * val_compare - compare two values
98: * @v1: first value
99: * @v2: second value
100: *
101: * Compares two values and returns -1, 0, 1 on <, =, > or F_CMP_ERROR on
102: * error. Tree module relies on this giving consistent results so
103: * that it can be used for building balanced trees.
104: */
105: int
106: val_compare(const struct f_val *v1, const struct f_val *v2)
107: {
108: if (v1->type != v2->type) {
109: if (v1->type == T_VOID) /* Hack for else */
110: return -1;
111: if (v2->type == T_VOID)
112: return 1;
113:
114: /* IP->Quad implicit conversion */
115: if ((v1->type == T_QUAD) && val_is_ip4(v2))
116: return uint_cmp(v1->val.i, ipa_to_u32(v2->val.ip));
117: if (val_is_ip4(v1) && (v2->type == T_QUAD))
118: return uint_cmp(ipa_to_u32(v1->val.ip), v2->val.i);
119:
120: debug( "Types do not match in val_compare\n" );
121: return F_CMP_ERROR;
122: }
123:
124: switch (v1->type) {
125: case T_VOID:
126: return 0;
127: case T_ENUM:
128: case T_INT:
129: case T_BOOL:
130: case T_PAIR:
131: case T_QUAD:
132: return uint_cmp(v1->val.i, v2->val.i);
133: case T_EC:
134: case T_RD:
135: return u64_cmp(v1->val.ec, v2->val.ec);
136: case T_LC:
137: return lcomm_cmp(v1->val.lc, v2->val.lc);
138: case T_IP:
139: return ipa_compare(v1->val.ip, v2->val.ip);
140: case T_NET:
141: return net_compare(v1->val.net, v2->val.net);
142: case T_STRING:
143: return strcmp(v1->val.s, v2->val.s);
144: default:
145: return F_CMP_ERROR;
146: }
147: }
148:
149: static inline int
150: pmi_same(const struct f_path_mask_item *mi1, const struct f_path_mask_item *mi2)
151: {
152: if (mi1->kind != mi2->kind)
153: return 0;
154:
155: switch (mi1->kind) {
156: case PM_ASN:
157: if (mi1->asn != mi2->asn)
158: return 0;
159: break;
160: case PM_ASN_EXPR:
161: if (!f_same(mi1->expr, mi2->expr))
162: return 0;
163: break;
164: case PM_ASN_RANGE:
165: if (mi1->from != mi2->from)
166: return 0;
167: if (mi1->to != mi2->to)
168: return 0;
169: break;
170: }
171:
172: return 1;
173: }
174:
175: static int
176: pm_same(const struct f_path_mask *m1, const struct f_path_mask *m2)
177: {
178: if (m1->len != m2->len)
179:
180: for (uint i=0; i<m1->len; i++)
181: if (!pmi_same(&(m1->item[i]), &(m2->item[i])))
182: return 0;
183:
184: return 1;
185: }
186:
187: /**
188: * val_same - compare two values
189: * @v1: first value
190: * @v2: second value
191: *
192: * Compares two values and returns 1 if they are same and 0 if not.
193: * Comparison of values of different types is valid and returns 0.
194: */
195: int
196: val_same(const struct f_val *v1, const struct f_val *v2)
197: {
198: int rc;
199:
200: rc = val_compare(v1, v2);
201: if (rc != F_CMP_ERROR)
202: return !rc;
203:
204: if (v1->type != v2->type)
205: return 0;
206:
207: switch (v1->type) {
208: case T_PATH_MASK:
209: return pm_same(v1->val.path_mask, v2->val.path_mask);
210: case T_PATH_MASK_ITEM:
211: return pmi_same(&(v1->val.pmi), &(v2->val.pmi));
212: case T_PATH:
213: case T_CLIST:
214: case T_ECLIST:
215: case T_LCLIST:
216: return adata_same(v1->val.ad, v2->val.ad);
217: case T_SET:
218: return same_tree(v1->val.t, v2->val.t);
219: case T_PREFIX_SET:
220: return trie_same(v1->val.ti, v2->val.ti);
221: default:
222: bug("Invalid type in val_same(): %x", v1->type);
223: }
224: }
225:
226: int
227: clist_set_type(const struct f_tree *set, struct f_val *v)
228: {
229: switch (set->from.type)
230: {
231: case T_PAIR:
232: v->type = T_PAIR;
233: return 1;
234:
235: case T_QUAD:
236: v->type = T_QUAD;
237: return 1;
238:
239: case T_IP:
240: if (val_is_ip4(&(set->from)) && val_is_ip4(&(set->to)))
241: {
242: v->type = T_QUAD;
243: return 1;
244: }
245: /* Fall through */
246: default:
247: v->type = T_VOID;
248: return 0;
249: }
250: }
251:
252: static int
253: clist_match_set(const struct adata *clist, const struct f_tree *set)
254: {
255: if (!clist)
256: return 0;
257:
258: struct f_val v;
259: if (!clist_set_type(set, &v))
260: return F_CMP_ERROR;
261:
262: u32 *l = (u32 *) clist->data;
263: u32 *end = l + clist->length/4;
264:
265: while (l < end) {
266: v.val.i = *l++;
267: if (find_tree(set, &v))
268: return 1;
269: }
270: return 0;
271: }
272:
273: static int
274: eclist_match_set(const struct adata *list, const struct f_tree *set)
275: {
276: if (!list)
277: return 0;
278:
279: if (!eclist_set_type(set))
280: return F_CMP_ERROR;
281:
282: struct f_val v;
283: u32 *l = int_set_get_data(list);
284: int len = int_set_get_size(list);
285: int i;
286:
287: v.type = T_EC;
288: for (i = 0; i < len; i += 2) {
289: v.val.ec = ec_get(l, i);
290: if (find_tree(set, &v))
291: return 1;
292: }
293:
294: return 0;
295: }
296:
297: static int
298: lclist_match_set(const struct adata *list, const struct f_tree *set)
299: {
300: if (!list)
301: return 0;
302:
303: if (!lclist_set_type(set))
304: return F_CMP_ERROR;
305:
306: struct f_val v;
307: u32 *l = int_set_get_data(list);
308: int len = int_set_get_size(list);
309: int i;
310:
311: v.type = T_LC;
312: for (i = 0; i < len; i += 3) {
313: v.val.lc = lc_get(l, i);
314: if (find_tree(set, &v))
315: return 1;
316: }
317:
318: return 0;
319: }
320:
321: const struct adata *
322: clist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos)
323: {
324: if (!list)
325: return NULL;
326:
327: int tree = (set->type == T_SET); /* 1 -> set is T_SET, 0 -> set is T_CLIST */
328: struct f_val v;
329: if (tree)
330: clist_set_type(set->val.t, &v);
331: else
332: v.type = T_PAIR;
333:
334: int len = int_set_get_size(list);
335: u32 *l = int_set_get_data(list);
336: u32 tmp[len];
337: u32 *k = tmp;
338: u32 *end = l + len;
339:
340: while (l < end) {
341: v.val.i = *l++;
342: /* pos && member(val, set) || !pos && !member(val, set), member() depends on tree */
343: if ((tree ? !!find_tree(set->val.t, &v) : int_set_contains(set->val.ad, v.val.i)) == pos)
344: *k++ = v.val.i;
345: }
346:
347: uint nl = (k - tmp) * sizeof(u32);
348: if (nl == list->length)
349: return list;
350:
351: struct adata *res = adata_empty(pool, nl);
352: memcpy(res->data, tmp, nl);
353: return res;
354: }
355:
356: const struct adata *
357: eclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos)
358: {
359: if (!list)
360: return NULL;
361:
362: int tree = (set->type == T_SET); /* 1 -> set is T_SET, 0 -> set is T_CLIST */
363: struct f_val v;
364:
365: int len = int_set_get_size(list);
366: u32 *l = int_set_get_data(list);
367: u32 tmp[len];
368: u32 *k = tmp;
369: int i;
370:
371: v.type = T_EC;
372: for (i = 0; i < len; i += 2) {
373: v.val.ec = ec_get(l, i);
374: /* pos && member(val, set) || !pos && !member(val, set), member() depends on tree */
375: if ((tree ? !!find_tree(set->val.t, &v) : ec_set_contains(set->val.ad, v.val.ec)) == pos) {
376: *k++ = l[i];
377: *k++ = l[i+1];
378: }
379: }
380:
381: uint nl = (k - tmp) * sizeof(u32);
382: if (nl == list->length)
383: return list;
384:
385: struct adata *res = adata_empty(pool, nl);
386: memcpy(res->data, tmp, nl);
387: return res;
388: }
389:
390: const struct adata *
391: lclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos)
392: {
393: if (!list)
394: return NULL;
395:
396: int tree = (set->type == T_SET); /* 1 -> set is T_SET, 0 -> set is T_CLIST */
397: struct f_val v;
398:
399: int len = int_set_get_size(list);
400: u32 *l = int_set_get_data(list);
401: u32 tmp[len];
402: u32 *k = tmp;
403: int i;
404:
405: v.type = T_LC;
406: for (i = 0; i < len; i += 3) {
407: v.val.lc = lc_get(l, i);
408: /* pos && member(val, set) || !pos && !member(val, set), member() depends on tree */
409: if ((tree ? !!find_tree(set->val.t, &v) : lc_set_contains(set->val.ad, v.val.lc)) == pos)
410: k = lc_copy(k, l+i);
411: }
412:
413: uint nl = (k - tmp) * sizeof(u32);
414: if (nl == list->length)
415: return list;
416:
417: struct adata *res = adata_empty(pool, nl);
418: memcpy(res->data, tmp, nl);
419: return res;
420: }
421:
422: /**
423: * val_in_range - implement |~| operator
424: * @v1: element
425: * @v2: set
426: *
427: * Checks if @v1 is element (|~| operator) of @v2.
428: */
429: int
430: val_in_range(const struct f_val *v1, const struct f_val *v2)
431: {
432: if ((v1->type == T_PATH) && (v2->type == T_PATH_MASK))
433: return as_path_match(v1->val.ad, v2->val.path_mask);
434:
435: if ((v1->type == T_INT) && (v2->type == T_PATH))
436: return as_path_contains(v2->val.ad, v1->val.i, 1);
437:
438: if (((v1->type == T_PAIR) || (v1->type == T_QUAD)) && (v2->type == T_CLIST))
439: return int_set_contains(v2->val.ad, v1->val.i);
440: /* IP->Quad implicit conversion */
441: if (val_is_ip4(v1) && (v2->type == T_CLIST))
442: return int_set_contains(v2->val.ad, ipa_to_u32(v1->val.ip));
443:
444: if ((v1->type == T_EC) && (v2->type == T_ECLIST))
445: return ec_set_contains(v2->val.ad, v1->val.ec);
446:
447: if ((v1->type == T_LC) && (v2->type == T_LCLIST))
448: return lc_set_contains(v2->val.ad, v1->val.lc);
449:
450: if ((v1->type == T_STRING) && (v2->type == T_STRING))
451: return patmatch(v2->val.s, v1->val.s);
452:
453: if ((v1->type == T_IP) && (v2->type == T_NET))
454: return ipa_in_netX(v1->val.ip, v2->val.net);
455:
456: if ((v1->type == T_NET) && (v2->type == T_NET))
457: return net_in_netX(v1->val.net, v2->val.net);
458:
459: if ((v1->type == T_NET) && (v2->type == T_PREFIX_SET))
460: return trie_match_net(v2->val.ti, v1->val.net);
461:
462: if (v2->type != T_SET)
463: return F_CMP_ERROR;
464:
465: /* With integrated Quad<->IP implicit conversion */
466: if ((v1->type == v2->val.t->from.type) ||
467: ((v1->type == T_QUAD) && val_is_ip4(&(v2->val.t->from)) && val_is_ip4(&(v2->val.t->to))))
468: return !!find_tree(v2->val.t, v1);
469:
470: if (v1->type == T_CLIST)
471: return clist_match_set(v1->val.ad, v2->val.t);
472:
473: if (v1->type == T_ECLIST)
474: return eclist_match_set(v1->val.ad, v2->val.t);
475:
476: if (v1->type == T_LCLIST)
477: return lclist_match_set(v1->val.ad, v2->val.t);
478:
479: if (v1->type == T_PATH)
480: return as_path_match_set(v1->val.ad, v2->val.t);
481:
482: return F_CMP_ERROR;
483: }
484:
485: /*
486: * val_format - format filter value
487: */
488: void
489: val_format(const struct f_val *v, buffer *buf)
490: {
491: char buf2[1024];
492: switch (v->type)
493: {
494: case T_VOID: buffer_puts(buf, "(void)"); return;
495: case T_BOOL: buffer_puts(buf, v->val.i ? "TRUE" : "FALSE"); return;
496: case T_INT: buffer_print(buf, "%u", v->val.i); return;
497: case T_STRING: buffer_print(buf, "%s", v->val.s); return;
498: case T_IP: buffer_print(buf, "%I", v->val.ip); return;
499: case T_NET: buffer_print(buf, "%N", v->val.net); return;
500: case T_PAIR: buffer_print(buf, "(%u,%u)", v->val.i >> 16, v->val.i & 0xffff); return;
501: case T_QUAD: buffer_print(buf, "%R", v->val.i); return;
502: case T_EC: ec_format(buf2, v->val.ec); buffer_print(buf, "%s", buf2); return;
503: case T_LC: lc_format(buf2, v->val.lc); buffer_print(buf, "%s", buf2); return;
504: case T_RD: rd_format(v->val.ec, buf2, 1024); buffer_print(buf, "%s", buf2); return;
505: case T_PREFIX_SET: trie_format(v->val.ti, buf); return;
506: case T_SET: tree_format(v->val.t, buf); return;
507: case T_ENUM: buffer_print(buf, "(enum %x)%u", v->type, v->val.i); return;
508: case T_PATH: as_path_format(v->val.ad, buf2, 1000); buffer_print(buf, "(path %s)", buf2); return;
509: case T_CLIST: int_set_format(v->val.ad, 1, -1, buf2, 1000); buffer_print(buf, "(clist %s)", buf2); return;
510: case T_ECLIST: ec_set_format(v->val.ad, -1, buf2, 1000); buffer_print(buf, "(eclist %s)", buf2); return;
511: case T_LCLIST: lc_set_format(v->val.ad, -1, buf2, 1000); buffer_print(buf, "(lclist %s)", buf2); return;
512: case T_PATH_MASK: pm_format(v->val.path_mask, buf); return;
513: default: buffer_print(buf, "[unknown type %x]", v->type); return;
514: }
515: }
516:
517: char *
518: val_format_str(struct linpool *lp, const struct f_val *v) {
519: buffer b;
520: LOG_BUFFER_INIT(b);
521: val_format(v, &b);
522: return lp_strdup(lp, b.start);
523: }
524:
525:
526: static char val_dump_buffer[1024];
527: const char *
528: val_dump(const struct f_val *v) {
529: static buffer b = {
530: .start = val_dump_buffer,
531: .end = val_dump_buffer + 1024,
532: };
533: b.pos = b.start;
534: val_format(v, &b);
535: return val_dump_buffer;
536: }
537:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to data.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / filter