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