1: /*
2: * BIRD -- Path Operations
3: *
4: * (c) 2000 Martin Mares <mj@ucw.cz>
5: * (c) 2000 Pavel Machek <pavel@ucw.cz>
6: *
7: * Can be freely distributed and used under the terms of the GNU GPL.
8: */
9:
10: #include "nest/bird.h"
11: #include "nest/route.h"
12: #include "nest/attrs.h"
13: #include "lib/resource.h"
14: #include "lib/unaligned.h"
15: #include "lib/string.h"
16: #include "filter/data.h"
17:
18: // static inline void put_as(byte *data, u32 as) { put_u32(data, as); }
19: // static inline u32 get_as(byte *data) { return get_u32(data); }
20:
21: #define put_as put_u32
22: #define get_as get_u32
23: #define BS 4 /* Default block size of ASN (autonomous system number) */
24:
25: #define BAD(DSC, VAL) ({ err_dsc = DSC; err_val = VAL; goto bad; })
26:
27: int
28: as_path_valid(byte *data, uint len, int bs, int confed, char *err, uint elen)
29: {
30: byte *pos = data;
31: char *err_dsc = NULL;
32: uint err_val = 0;
33:
34: while (len)
35: {
36: if (len < 2)
37: BAD("segment framing error", 0);
38:
39: /* Process one AS path segment */
40: uint type = pos[0];
41: uint slen = 2 + bs * pos[1];
42:
43: if (len < slen)
44: BAD("segment framing error", len);
45:
46: switch (type)
47: {
48: case AS_PATH_SET:
49: case AS_PATH_SEQUENCE:
50: break;
51:
52: case AS_PATH_CONFED_SEQUENCE:
53: case AS_PATH_CONFED_SET:
54: if (!confed)
55: BAD("AS_CONFED* segment", type);
56: break;
57:
58: default:
59: BAD("unknown segment", type);
60: }
61:
62: if (pos[1] == 0)
63: BAD("zero-length segment", type);
64:
65: pos += slen;
66: len -= slen;
67: }
68:
69: return 1;
70:
71: bad:
72: if (err)
73: if (bsnprintf(err, elen, "%s (%u) at %d", err_dsc, err_val, (int) (pos - data)) < 0)
74: err[0] = 0;
75:
76: return 0;
77: }
78:
79: int
80: as_path_16to32(byte *dst, const byte *src, uint len)
81: {
82: byte *dst0 = dst;
83: const byte *end = src + len;
84: uint i, n;
85:
86: while (src < end)
87: {
88: n = src[1];
89: *dst++ = *src++;
90: *dst++ = *src++;
91:
92: for (i = 0; i < n; i++)
93: {
94: put_u32(dst, get_u16(src));
95: src += 2;
96: dst += 4;
97: }
98: }
99:
100: return dst - dst0;
101: }
102:
103: int
104: as_path_32to16(byte *dst, const byte *src, uint len)
105: {
106: byte *dst0 = dst;
107: const byte *end = src + len;
108: uint i, n;
109:
110: while (src < end)
111: {
112: n = src[1];
113: *dst++ = *src++;
114: *dst++ = *src++;
115:
116: for (i = 0; i < n; i++)
117: {
118: put_u16(dst, get_u32(src));
119: src += 4;
120: dst += 2;
121: }
122: }
123:
124: return dst - dst0;
125: }
126:
127: int
128: as_path_contains_as4(const struct adata *path)
129: {
130: const byte *pos = path->data;
131: const byte *end = pos + path->length;
132: uint i, n;
133:
134: while (pos < end)
135: {
136: n = pos[1];
137: pos += 2;
138:
139: for (i = 0; i < n; i++)
140: {
141: if (get_as(pos) > 0xFFFF)
142: return 1;
143:
144: pos += BS;
145: }
146: }
147:
148: return 0;
149: }
150:
151: int
152: as_path_contains_confed(const struct adata *path)
153: {
154: const byte *pos = path->data;
155: const byte *end = pos + path->length;
156:
157: while (pos < end)
158: {
159: uint type = pos[0];
160: uint slen = 2 + BS * pos[1];
161:
162: if ((type == AS_PATH_CONFED_SEQUENCE) ||
163: (type == AS_PATH_CONFED_SET))
164: return 1;
165:
166: pos += slen;
167: }
168:
169: return 0;
170: }
171:
172: struct adata *
173: as_path_strip_confed(struct linpool *pool, const struct adata *path)
174: {
175: struct adata *res = lp_alloc_adata(pool, path->length);
176: const byte *src = path->data;
177: const byte *end = src + path->length;
178: byte *dst = res->data;
179:
180: while (src < end)
181: {
182: uint type = src[0];
183: uint slen = 2 + BS * src[1];
184:
185: /* Copy regular segments */
186: if ((type == AS_PATH_SET) || (type == AS_PATH_SEQUENCE))
187: {
188: memcpy(dst, src, slen);
189: dst += slen;
190: }
191:
192: src += slen;
193: }
194:
195: /* Fix the result length */
196: res->length = dst - res->data;
197:
198: return res;
199: }
200:
201: struct adata *
202: as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as)
203: {
204: struct adata *np;
205: const byte *pos = op->data;
206: uint len = op->length;
207:
208: if (len && (pos[0] == seq) && (pos[1] < 255))
209: {
210: /* Starting with matching segment => just prepend the AS number */
211: np = lp_alloc_adata(pool, len + BS);
212: np->data[0] = seq;
213: np->data[1] = pos[1] + 1;
214: put_as(np->data + 2, as);
215:
216: uint dlen = BS * pos[1];
217: memcpy(np->data + 2 + BS, pos + 2, dlen);
218: ADVANCE(pos, len, 2 + dlen);
219: }
220: else
221: {
222: /* Create a new path segment */
223: np = lp_alloc_adata(pool, len + 2 + BS);
224: np->data[0] = seq;
225: np->data[1] = 1;
226: put_as(np->data + 2, as);
227: }
228:
229: if (len)
230: {
231: byte *dst = np->data + 2 + BS * np->data[1];
232:
233: memcpy(dst, pos, len);
234: }
235:
236: return np;
237: }
238:
239:
240: struct adata *
241: as_path_to_old(struct linpool *pool, const struct adata *path)
242: {
243: struct adata *res = lp_alloc_adata(pool, path->length);
244: byte *pos = res->data;
245: byte *end = pos + res->length;
246: uint i, n;
247: u32 as;
248:
249: /* Copy the whole path */
250: memcpy(res->data, path->data, path->length);
251:
252: /* Replace 32-bit AS numbers with AS_TRANS */
253: while (pos < end)
254: {
255: n = pos[1];
256: pos += 2;
257:
258: for (i = 0; i < n; i++)
259: {
260: as = get_as(pos);
261: if (as > 0xFFFF)
262: put_as(pos, AS_TRANS);
263:
264: pos += BS;
265: }
266: }
267:
268: return res;
269: }
270:
271: /*
272: * Cut the path to the length @num, measured to the usual path metric. Note that
273: * AS_CONFED_* segments have zero length and must be added if they are on edge.
274: */
275: struct adata *
276: as_path_cut(struct linpool *pool, const struct adata *path, uint num)
277: {
278: const byte *pos = path->data;
279: const byte *end = pos + path->length;
280:
281: while (pos < end)
282: {
283: uint t = pos[0];
284: uint l = pos[1];
285: uint n = 0;
286:
287: switch (t)
288: {
289: case AS_PATH_SET: n = 1; break;
290: case AS_PATH_SEQUENCE: n = l; break;
291: case AS_PATH_CONFED_SEQUENCE: n = 0; break;
292: case AS_PATH_CONFED_SET: n = 0; break;
293: default: bug("as_path_cut: Invalid path segment");
294: }
295:
296: /* Cannot add whole segment, so try partial one and finish */
297: if (num < n)
298: {
299: const byte *nend = pos;
300: if (num)
301: nend += 2 + BS * num;
302:
303: struct adata *res = lp_alloc_adata(pool, path->length);
304: res->length = nend - (const byte *) path->data;
305: memcpy(res->data, path->data, res->length);
306:
307: if (num)
308: {
309: byte *dpos = ((byte *) res->data) + (pos - (const byte *) path->data);
310: dpos[1] = num;
311: }
312:
313: return res;
314: }
315:
316: num -= n;
317: pos += 2 + BS * l;
318: }
319:
320: struct adata *res = lp_alloc_adata(pool, path->length);
321: res->length = path->length;
322: memcpy(res->data, path->data, res->length);
323: return res;
324: }
325:
326: /*
327: * Merge (concatenate) paths @p1 and @p2 and return the result.
328: * In contrast to other as_path_* functions, @p1 and @p2 may be reused.
329: */
330: const struct adata *
331: as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2)
332: {
333: if (p1->length == 0)
334: return p2;
335:
336: if (p2->length == 0)
337: return p1;
338:
339: struct adata *res = lp_alloc_adata(pool, p1->length + p2->length);
340: memcpy(res->data, p1->data, p1->length);
341: memcpy(res->data + p1->length, p2->data, p2->length);
342:
343: return res;
344: }
345:
346: void
347: as_path_format(const struct adata *path, byte *bb, uint size)
348: {
349: buffer buf = { .start = bb, .pos = bb, .end = bb + size }, *b = &buf;
350: const byte *pos = path->data;
351: const byte *end = pos + path->length;
352: const char *ops, *cls;
353:
354: b->pos[0] = 0;
355:
356: while (pos < end)
357: {
358: uint type = pos[0];
359: uint len = pos[1];
360: pos += 2;
361:
362: switch (type)
363: {
364: case AS_PATH_SET: ops = "{"; cls = "}"; break;
365: case AS_PATH_SEQUENCE: ops = NULL; cls = NULL; break;
366: case AS_PATH_CONFED_SEQUENCE: ops = "("; cls = ")"; break;
367: case AS_PATH_CONFED_SET: ops = "({"; cls = "})"; break;
368: default: bug("Invalid path segment");
369: }
370:
371: if (ops)
372: buffer_puts(b, ops);
373:
374: while (len--)
375: {
376: buffer_print(b, len ? "%u " : "%u", get_as(pos));
377: pos += BS;
378: }
379:
380: if (cls)
381: buffer_puts(b, cls);
382:
383: if (pos < end)
384: buffer_puts(b, " ");
385: }
386:
387: /* Handle overflow */
388: if (b->pos == b->end)
389: strcpy(b->end - 12, "...");
390: }
391:
392: int
393: as_path_getlen(const struct adata *path)
394: {
395: const byte *pos = path->data;
396: const byte *end = pos + path->length;
397: uint res = 0;
398:
399: while (pos < end)
400: {
401: uint t = pos[0];
402: uint l = pos[1];
403: uint n = 0;
404:
405: switch (t)
406: {
407: case AS_PATH_SET: n = 1; break;
408: case AS_PATH_SEQUENCE: n = l; break;
409: case AS_PATH_CONFED_SEQUENCE: n = 0; break;
410: case AS_PATH_CONFED_SET: n = 0; break;
411: default: bug("as_path_getlen: Invalid path segment");
412: }
413:
414: res += n;
415: pos += 2 + BS * l;
416: }
417:
418: return res;
419: }
420:
421: int
422: as_path_get_last(const struct adata *path, u32 *orig_as)
423: {
424: const byte *pos = path->data;
425: const byte *end = pos + path->length;
426: int found = 0;
427: u32 val = 0;
428:
429: while (pos < end)
430: {
431: uint type = pos[0];
432: uint len = pos[1];
433: pos += 2;
434:
435: if (!len)
436: continue;
437:
438: switch (type)
439: {
440: case AS_PATH_SET:
441: case AS_PATH_CONFED_SET:
442: found = 0;
443: break;
444:
445: case AS_PATH_SEQUENCE:
446: case AS_PATH_CONFED_SEQUENCE:
447: val = get_as(pos + BS * (len - 1));
448: found = 1;
449: break;
450:
451: default:
452: bug("Invalid path segment");
453: }
454:
455: pos += BS * len;
456: }
457:
458: if (found)
459: *orig_as = val;
460: return found;
461: }
462:
463: u32
464: as_path_get_last_nonaggregated(const struct adata *path)
465: {
466: const byte *pos = path->data;
467: const byte *end = pos + path->length;
468: u32 val = 0;
469:
470: while (pos < end)
471: {
472: uint type = pos[0];
473: uint len = pos[1];
474: pos += 2;
475:
476: if (!len)
477: continue;
478:
479: switch (type)
480: {
481: case AS_PATH_SET:
482: case AS_PATH_CONFED_SET:
483: return val;
484:
485: case AS_PATH_SEQUENCE:
486: case AS_PATH_CONFED_SEQUENCE:
487: val = get_as(pos + BS * (len - 1));
488: break;
489:
490: default:
491: bug("Invalid path segment");
492: }
493:
494: pos += BS * len;
495: }
496:
497: return val;
498: }
499:
500: int
501: as_path_get_first(const struct adata *path, u32 *last_as)
502: {
503: const u8 *p = path->data;
504:
505: if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0))
506: return 0;
507:
508: *last_as = get_as(p+2);
509: return 1;
510: }
511:
512: int
513: as_path_get_first_regular(const struct adata *path, u32 *last_as)
514: {
515: const byte *pos = path->data;
516: const byte *end = pos + path->length;
517:
518: while (pos < end)
519: {
520: uint type = pos[0];
521: uint len = pos[1];
522: pos += 2;
523:
524: switch (type)
525: {
526: case AS_PATH_SET:
527: return 0;
528:
529: case AS_PATH_SEQUENCE:
530: if (len == 0)
531: return 0;
532:
533: *last_as = get_as(pos);
534: return 1;
535:
536: case AS_PATH_CONFED_SEQUENCE:
537: case AS_PATH_CONFED_SET:
538: break;
539:
540: default:
541: bug("Invalid path segment");
542: }
543:
544: pos += BS * len;
545: }
546:
547: return 0;
548: }
549:
550: int
551: as_path_contains(const struct adata *path, u32 as, int min)
552: {
553: const u8 *p = path->data;
554: const u8 *q = p+path->length;
555: int num = 0;
556: int i, n;
557:
558: while (p<q)
559: {
560: n = p[1];
561: p += 2;
562: for(i=0; i<n; i++)
563: {
564: if (get_as(p) == as)
565: if (++num == min)
566: return 1;
567: p += BS;
568: }
569: }
570: return 0;
571: }
572:
573: int
574: as_path_match_set(const struct adata *path, const struct f_tree *set)
575: {
576: const u8 *p = path->data;
577: const u8 *q = p+path->length;
578: int i, n;
579:
580: while (p<q)
581: {
582: n = p[1];
583: p += 2;
584: for (i=0; i<n; i++)
585: {
586: struct f_val v = {T_INT, .val.i = get_as(p)};
587: if (find_tree(set, &v))
588: return 1;
589: p += BS;
590: }
591: }
592:
593: return 0;
594: }
595:
596: const struct adata *
597: as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos)
598: {
599: if (!path)
600: return NULL;
601:
602: int len = path->length;
603: const u8 *p = path->data;
604: const u8 *q = path->data + len;
605: u8 *d, *d2;
606: int i, bt, sn, dn;
607: u8 buf[len];
608:
609: d = buf;
610: while (p<q)
611: {
612: /* Read block header (type and length) */
613: bt = p[0];
614: sn = p[1];
615: dn = 0;
616: p += 2;
617: d2 = d + 2;
618:
619: for (i = 0; i < sn; i++)
620: {
621: u32 as = get_as(p);
622: int match;
623:
624: if (set)
625: {
626: struct f_val v = {T_INT, .val.i = as};
627: match = !!find_tree(set, &v);
628: }
629: else
630: match = (as == key);
631:
632: if (match == pos)
633: {
634: put_as(d2, as);
635: d2 += BS;
636: dn++;
637: }
638:
639: p += BS;
640: }
641:
642: if (dn > 0)
643: {
644: /* Nonempty block, set block header and advance */
645: d[0] = bt;
646: d[1] = dn;
647: d = d2;
648: }
649: }
650:
651: uint nl = d - buf;
652: if (nl == path->length)
653: return path;
654:
655: struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl);
656: res->length = nl;
657: memcpy(res->data, buf, nl);
658:
659: return res;
660: }
661:
662:
663: struct pm_pos
664: {
665: u8 set;
666: u8 mark;
667: union
668: {
669: const char *sp;
670: u32 asn;
671: } val;
672: };
673:
674: static int
675: parse_path(const struct adata *path, struct pm_pos *pp)
676: {
677: const byte *pos = path->data;
678: const byte *end = pos + path->length;
679: struct pm_pos *op = pp;
680: uint i;
681:
682: while (pos < end)
683: {
684: uint type = pos[0];
685: uint len = pos[1];
686: pos += 2;
687:
688: switch (type)
689: {
690: case AS_PATH_SET:
691: case AS_PATH_CONFED_SET:
692: pp->set = 1;
693: pp->mark = 0;
694: pp->val.sp = pos - 1;
695: pp++;
696:
697: pos += BS * len;
698: break;
699:
700: case AS_PATH_SEQUENCE:
701: case AS_PATH_CONFED_SEQUENCE:
702: for (i = 0; i < len; i++)
703: {
704: pp->set = 0;
705: pp->mark = 0;
706: pp->val.asn = get_as(pos);
707: pp++;
708:
709: pos += BS;
710: }
711: break;
712:
713: default:
714: bug("Invalid path segment");
715: }
716: }
717:
718: return pp - op;
719: }
720:
721: static int
722: pm_match(struct pm_pos *pos, u32 asn, u32 asn2)
723: {
724: u32 gas;
725: if (! pos->set)
726: return ((pos->val.asn >= asn) && (pos->val.asn <= asn2));
727:
728: const u8 *p = pos->val.sp;
729: int len = *p++;
730: int i;
731:
732: for (i = 0; i < len; i++)
733: {
734: gas = get_as(p + i * BS);
735:
736: if ((gas >= asn) && (gas <= asn2))
737: return 1;
738: }
739:
740: return 0;
741: }
742:
743: static int
744: pm_match_set(struct pm_pos *pos, const struct f_tree *set)
745: {
746: struct f_val asn = { .type = T_INT };
747:
748: if (! pos->set)
749: {
750: asn.val.i = pos->val.asn;
751: return !!find_tree(set, &asn);
752: }
753:
754: const u8 *p = pos->val.sp;
755: int len = *p++;
756: int i;
757:
758: for (i = 0; i < len; i++)
759: {
760: asn.val.i = get_as(p + i * BS);
761: if (find_tree(set, &asn))
762: return 1;
763: }
764:
765: return 0;
766: }
767:
768: static void
769: pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh)
770: {
771: int j;
772:
773: if (pos[i].set)
774: pos[i].mark = 1;
775:
776: for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++)
777: pos[j].mark = 1;
778: pos[j].mark = 1;
779:
780: /* We are going downwards, therefore every mark is
781: new low and just the first mark is new high */
782:
783: *nl = i + (pos[i].set ? 0 : 1);
784:
785: if (*nh < 0)
786: *nh = j;
787: }
788:
789: /* AS path matching is nontrivial. Because AS path can
790: * contain sets, it is not a plain wildcard matching. A set
791: * in an AS path is interpreted as it might represent any
792: * sequence of AS numbers from that set (possibly with
793: * repetitions). So it is also a kind of a pattern,
794: * more complicated than a path mask.
795: *
796: * The algorithm for AS path matching is a variant
797: * of nondeterministic finite state machine, where
798: * positions in AS path are states, and items in
799: * path mask are input for that finite state machine.
800: * During execution of the algorithm we maintain a set
801: * of marked states - a state is marked if it can be
802: * reached by any walk through NFSM with regard to
803: * currently processed part of input. When we process
804: * next part of mask, we advance each marked state.
805: * We start with marked first position, when we
806: * run out of marked positions, we reject. When
807: * we process the whole mask, we accept if final position
808: * (auxiliary position after last real position in AS path)
809: * is marked.
810: */
811: int
812: as_path_match(const struct adata *path, const struct f_path_mask *mask)
813: {
814: struct pm_pos pos[2048 + 1];
815: int plen = parse_path(path, pos);
816: int l, h, i, nh, nl;
817: u32 val = 0;
818: u32 val2 = 0;
819:
820: /* l and h are bound of interval of positions where
821: are marked states */
822:
823: pos[plen].set = 0;
824: pos[plen].mark = 0;
825:
826: l = h = 0;
827: pos[0].mark = 1;
828:
829: for (uint m=0; m < mask->len; m++)
830: {
831: /* We remove this mark to not step after pos[plen] */
832: pos[plen].mark = 0;
833:
834: switch (mask->item[m].kind)
835: {
836: case PM_ASTERISK:
837: for (i = l; i <= plen; i++)
838: pos[i].mark = 1;
839: h = plen;
840: break;
841:
842: case PM_ASN: /* Define single ASN as ASN..ASN - very narrow interval */
843: val2 = val = mask->item[m].asn;
844: goto step;
845: case PM_ASN_EXPR:
846: bug("Expressions should be evaluated on AS path mask construction.");
847: case PM_ASN_RANGE:
848: val = mask->item[m].from;
849: val2 = mask->item[m].to;
850: goto step;
851: case PM_QUESTION:
852: case PM_ASN_SET:
853: step:
854: nh = nl = -1;
855: for (i = h; i >= l; i--)
856: if (pos[i].mark)
857: {
858: pos[i].mark = 0;
859: if ((mask->item[m].kind == PM_QUESTION) ||
860: ((mask->item[m].kind != PM_ASN_SET) ?
861: pm_match(pos + i, val, val2) :
862: pm_match_set(pos + i, mask->item[m].set)))
863: pm_mark(pos, i, plen, &nl, &nh);
864: }
865:
866: if (nh < 0)
867: return 0;
868:
869: h = nh;
870: l = nl;
871: break;
872: }
873: }
874:
875: return pos[plen].mark;
876: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to a-path.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 / nest