1 /* $OpenBSD: rde_attr.c,v 1.134 2023/07/12 14:45:43 claudio Exp $ */
2
3 /*
4 * Copyright (c) 2004 Claudio Jeker <claudio@openbsd.org>
5 * Copyright (c) 2016 Job Snijders <job@instituut.net>
6 * Copyright (c) 2016 Peter Hessler <phessler@openbsd.org>
7 *
8 * Permission to use, copy, modify, and distribute this software for any
9 * purpose with or without fee is hereby granted, provided that the above
10 * copyright notice and this permission notice appear in all copies.
11 *
12 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
13 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
14 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
15 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
16 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
17 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
18 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 */
20
21 #include <sys/queue.h>
22
23 #include <endian.h>
24 #include <limits.h>
25 #include <stdlib.h>
26 #include <string.h>
27
28 #include "bgpd.h"
29 #include "rde.h"
30 #include "log.h"
31
32 int
attr_writebuf(struct ibuf * buf,uint8_t flags,uint8_t type,void * data,uint16_t data_len)33 attr_writebuf(struct ibuf *buf, uint8_t flags, uint8_t type, void *data,
34 uint16_t data_len)
35 {
36 u_char hdr[4];
37
38 flags &= ~ATTR_DEFMASK;
39 if (data_len > 255) {
40 flags |= ATTR_EXTLEN;
41 hdr[2] = (data_len >> 8) & 0xff;
42 hdr[3] = data_len & 0xff;
43 } else {
44 hdr[2] = data_len & 0xff;
45 }
46
47 hdr[0] = flags;
48 hdr[1] = type;
49
50 if (ibuf_add(buf, hdr, flags & ATTR_EXTLEN ? 4 : 3) == -1)
51 return (-1);
52 if (data != NULL && ibuf_add(buf, data, data_len) == -1)
53 return (-1);
54 return (0);
55 }
56
57 /* optional attribute specific functions */
58 struct attr *attr_alloc(uint8_t, uint8_t, void *, uint16_t);
59 struct attr *attr_lookup(uint8_t, uint8_t, void *, uint16_t);
60 void attr_put(struct attr *);
61
62 static inline int attr_diff(struct attr *, struct attr *);
63
64 RB_HEAD(attr_tree, attr) attrtable = RB_INITIALIZER(&attr);
65 RB_GENERATE_STATIC(attr_tree, attr, entry, attr_diff);
66
67
68 void
attr_shutdown(void)69 attr_shutdown(void)
70 {
71 if (!RB_EMPTY(&attrtable))
72 log_warnx("%s: free non-free attr table", __func__);
73 }
74
75 int
attr_optadd(struct rde_aspath * asp,uint8_t flags,uint8_t type,void * data,uint16_t len)76 attr_optadd(struct rde_aspath *asp, uint8_t flags, uint8_t type,
77 void *data, uint16_t len)
78 {
79 uint8_t l;
80 struct attr *a, *t;
81 void *p;
82
83 /* known optional attributes were validated previously */
84 if ((a = attr_lookup(flags, type, data, len)) == NULL)
85 a = attr_alloc(flags, type, data, len);
86
87 /* attribute allowed only once */
88 for (l = 0; l < asp->others_len; l++) {
89 if (asp->others[l] == NULL)
90 break;
91 if (type == asp->others[l]->type) {
92 if (a->refcnt == 0)
93 attr_put(a);
94 return (-1);
95 }
96 }
97
98 /* add attribute to the table but first bump refcnt */
99 a->refcnt++;
100 rdemem.attr_refs++;
101
102 for (l = 0; l < asp->others_len; l++) {
103 if (asp->others[l] == NULL) {
104 asp->others[l] = a;
105 return (0);
106 }
107 /* list is sorted */
108 if (a->type < asp->others[l]->type) {
109 t = asp->others[l];
110 asp->others[l] = a;
111 a = t;
112 }
113 }
114
115 /* no empty slot found, need to realloc */
116 if (asp->others_len == UCHAR_MAX)
117 fatalx("attr_optadd: others_len overflow");
118
119 asp->others_len++;
120 if ((p = reallocarray(asp->others,
121 asp->others_len, sizeof(struct attr *))) == NULL)
122 fatal("%s", __func__);
123 asp->others = p;
124
125 /* l stores the size of others before resize */
126 asp->others[l] = a;
127 return (0);
128 }
129
130 struct attr *
attr_optget(const struct rde_aspath * asp,uint8_t type)131 attr_optget(const struct rde_aspath *asp, uint8_t type)
132 {
133 uint8_t l;
134
135 for (l = 0; l < asp->others_len; l++) {
136 if (asp->others[l] == NULL)
137 break;
138 if (type == asp->others[l]->type)
139 return (asp->others[l]);
140 if (type < asp->others[l]->type)
141 break;
142 }
143 return (NULL);
144 }
145
146 void
attr_copy(struct rde_aspath * t,const struct rde_aspath * s)147 attr_copy(struct rde_aspath *t, const struct rde_aspath *s)
148 {
149 uint8_t l;
150
151 if (t->others != NULL)
152 attr_freeall(t);
153
154 t->others_len = s->others_len;
155 if (t->others_len == 0) {
156 t->others = NULL;
157 return;
158 }
159
160 if ((t->others = calloc(s->others_len, sizeof(struct attr *))) == 0)
161 fatal("%s", __func__);
162
163 for (l = 0; l < t->others_len; l++) {
164 if (s->others[l] == NULL)
165 break;
166 s->others[l]->refcnt++;
167 rdemem.attr_refs++;
168 t->others[l] = s->others[l];
169 }
170 }
171
172 static inline int
attr_diff(struct attr * oa,struct attr * ob)173 attr_diff(struct attr *oa, struct attr *ob)
174 {
175 int r;
176
177 if (ob == NULL)
178 return (1);
179 if (oa == NULL)
180 return (-1);
181 if (oa->flags > ob->flags)
182 return (1);
183 if (oa->flags < ob->flags)
184 return (-1);
185 if (oa->type > ob->type)
186 return (1);
187 if (oa->type < ob->type)
188 return (-1);
189 if (oa->len > ob->len)
190 return (1);
191 if (oa->len < ob->len)
192 return (-1);
193 r = memcmp(oa->data, ob->data, oa->len);
194 if (r > 0)
195 return (1);
196 if (r < 0)
197 return (-1);
198 return (0);
199 }
200
201 int
attr_compare(struct rde_aspath * a,struct rde_aspath * b)202 attr_compare(struct rde_aspath *a, struct rde_aspath *b)
203 {
204 uint8_t l, min;
205
206 min = a->others_len < b->others_len ? a->others_len : b->others_len;
207 for (l = 0; l < min; l++)
208 if (a->others[l] != b->others[l])
209 return (attr_diff(a->others[l], b->others[l]));
210
211 if (a->others_len < b->others_len) {
212 for (; l < b->others_len; l++)
213 if (b->others[l] != NULL)
214 return (-1);
215 } else if (a->others_len > b->others_len) {
216 for (; l < a->others_len; l++)
217 if (a->others[l] != NULL)
218 return (1);
219 }
220
221 return (0);
222 }
223
224 void
attr_free(struct rde_aspath * asp,struct attr * attr)225 attr_free(struct rde_aspath *asp, struct attr *attr)
226 {
227 uint8_t l;
228
229 for (l = 0; l < asp->others_len; l++)
230 if (asp->others[l] == attr) {
231 attr_put(asp->others[l]);
232 for (++l; l < asp->others_len; l++)
233 asp->others[l - 1] = asp->others[l];
234 asp->others[asp->others_len - 1] = NULL;
235 return;
236 }
237
238 /* no realloc() because the slot may be reused soon */
239 }
240
241 void
attr_freeall(struct rde_aspath * asp)242 attr_freeall(struct rde_aspath *asp)
243 {
244 uint8_t l;
245
246 for (l = 0; l < asp->others_len; l++)
247 attr_put(asp->others[l]);
248
249 free(asp->others);
250 asp->others = NULL;
251 asp->others_len = 0;
252 }
253
254 struct attr *
attr_alloc(uint8_t flags,uint8_t type,void * data,uint16_t len)255 attr_alloc(uint8_t flags, uint8_t type, void *data, uint16_t len)
256 {
257 struct attr *a;
258
259 a = calloc(1, sizeof(struct attr));
260 if (a == NULL)
261 fatal("%s", __func__);
262 rdemem.attr_cnt++;
263
264 flags &= ~ATTR_DEFMASK; /* normalize mask */
265 a->flags = flags;
266 a->type = type;
267 a->len = len;
268 if (len != 0) {
269 if ((a->data = malloc(len)) == NULL)
270 fatal("%s", __func__);
271
272 rdemem.attr_dcnt++;
273 rdemem.attr_data += len;
274 memcpy(a->data, data, len);
275 } else
276 a->data = NULL;
277
278 if (RB_INSERT(attr_tree, &attrtable, a) != NULL)
279 fatalx("corrupted attr tree");
280
281 return (a);
282 }
283
284 struct attr *
attr_lookup(uint8_t flags,uint8_t type,void * data,uint16_t len)285 attr_lookup(uint8_t flags, uint8_t type, void *data, uint16_t len)
286 {
287 struct attr needle;
288
289 flags &= ~ATTR_DEFMASK; /* normalize mask */
290
291 needle.flags = flags;
292 needle.type = type;
293 needle.len = len;
294 needle.data = data;
295 return RB_FIND(attr_tree, &attrtable, &needle);
296 }
297
298 void
attr_put(struct attr * a)299 attr_put(struct attr *a)
300 {
301 if (a == NULL)
302 return;
303
304 rdemem.attr_refs--;
305 if (--a->refcnt > 0)
306 /* somebody still holds a reference */
307 return;
308
309 /* unlink */
310 RB_REMOVE(attr_tree, &attrtable, a);
311
312 if (a->len != 0)
313 rdemem.attr_dcnt--;
314 rdemem.attr_data -= a->len;
315 rdemem.attr_cnt--;
316 free(a->data);
317 free(a);
318 }
319
320 /* aspath specific functions */
321
322 static uint16_t aspath_count(const void *, uint16_t);
323 static uint32_t aspath_extract_origin(const void *, uint16_t);
324 static uint16_t aspath_countlength(struct aspath *, uint16_t, int);
325 static void aspath_countcopy(struct aspath *, uint16_t, uint8_t *,
326 uint16_t, int);
327
328 int
aspath_compare(struct aspath * a1,struct aspath * a2)329 aspath_compare(struct aspath *a1, struct aspath *a2)
330 {
331 int r;
332
333 if (a1->len > a2->len)
334 return (1);
335 if (a1->len < a2->len)
336 return (-1);
337 r = memcmp(a1->data, a2->data, a1->len);
338 if (r > 0)
339 return (1);
340 if (r < 0)
341 return (-1);
342 return (0);
343 }
344
345 struct aspath *
aspath_get(void * data,uint16_t len)346 aspath_get(void *data, uint16_t len)
347 {
348 struct aspath *aspath;
349
350 aspath = malloc(ASPATH_HEADER_SIZE + len);
351 if (aspath == NULL)
352 fatal("%s", __func__);
353
354 rdemem.aspath_cnt++;
355 rdemem.aspath_size += ASPATH_HEADER_SIZE + len;
356
357 aspath->len = len;
358 aspath->ascnt = aspath_count(data, len);
359 aspath->source_as = aspath_extract_origin(data, len);
360 memcpy(aspath->data, data, len);
361
362 return (aspath);
363 }
364
365 struct aspath *
aspath_copy(struct aspath * a)366 aspath_copy(struct aspath *a)
367 {
368 struct aspath *aspath;
369
370 aspath = malloc(ASPATH_HEADER_SIZE + a->len);
371 if (aspath == NULL)
372 fatal("%s", __func__);
373
374 rdemem.aspath_cnt++;
375 rdemem.aspath_size += ASPATH_HEADER_SIZE + a->len;
376
377 memcpy(aspath, a, ASPATH_HEADER_SIZE + a->len);
378
379 return (aspath);
380 }
381
382 void
aspath_put(struct aspath * aspath)383 aspath_put(struct aspath *aspath)
384 {
385 if (aspath == NULL)
386 return;
387
388 rdemem.aspath_cnt--;
389 rdemem.aspath_size -= ASPATH_HEADER_SIZE + aspath->len;
390 free(aspath);
391 }
392
393 /*
394 * convert a 4 byte aspath to a 2 byte one.
395 */
396 u_char *
aspath_deflate(u_char * data,uint16_t * len,int * flagnew)397 aspath_deflate(u_char *data, uint16_t *len, int *flagnew)
398 {
399 uint8_t *seg, *nseg, *ndata;
400 uint32_t as;
401 int i;
402 uint16_t seg_size, olen, nlen;
403 uint8_t seg_len;
404
405 /* first calculate the length of the aspath */
406 nlen = 0;
407 seg = data;
408 olen = *len;
409 for (; olen > 0; olen -= seg_size, seg += seg_size) {
410 seg_len = seg[1];
411 seg_size = 2 + sizeof(uint32_t) * seg_len;
412 nlen += 2 + sizeof(uint16_t) * seg_len;
413
414 if (seg_size > olen)
415 fatalx("%s: would overflow", __func__);
416 }
417
418 if ((ndata = malloc(nlen)) == NULL)
419 fatal("%s", __func__);
420
421 /* then copy the aspath */
422 seg = data;
423 olen = *len;
424 for (nseg = ndata; seg < data + olen; seg += seg_size) {
425 *nseg++ = seg[0];
426 *nseg++ = seg_len = seg[1];
427 seg_size = 2 + sizeof(uint32_t) * seg_len;
428
429 for (i = 0; i < seg_len; i++) {
430 as = aspath_extract(seg, i);
431 if (as > USHRT_MAX) {
432 as = AS_TRANS;
433 *flagnew = 1;
434 }
435 *nseg++ = (as >> 8) & 0xff;
436 *nseg++ = as & 0xff;
437 }
438 }
439
440 *len = nlen;
441 return (ndata);
442 }
443
444 void
aspath_merge(struct rde_aspath * a,struct attr * attr)445 aspath_merge(struct rde_aspath *a, struct attr *attr)
446 {
447 uint8_t *np;
448 uint16_t ascnt, diff, nlen, difflen;
449 int hroom = 0;
450
451 ascnt = aspath_count(attr->data, attr->len);
452 if (ascnt > a->aspath->ascnt) {
453 /* ASPATH is shorter then AS4_PATH no way to merge */
454 attr_free(a, attr);
455 return;
456 }
457
458 diff = a->aspath->ascnt - ascnt;
459 if (diff && attr->len > 2 && attr->data[0] == AS_SEQUENCE)
460 hroom = attr->data[1];
461 difflen = aspath_countlength(a->aspath, diff, hroom);
462 nlen = attr->len + difflen;
463
464 if ((np = malloc(nlen)) == NULL)
465 fatal("%s", __func__);
466
467 /* copy head from old aspath */
468 aspath_countcopy(a->aspath, diff, np, difflen, hroom);
469
470 /* copy tail from new aspath */
471 if (hroom > 0)
472 memcpy(np + nlen - attr->len + 2, attr->data + 2,
473 attr->len - 2);
474 else
475 memcpy(np + nlen - attr->len, attr->data, attr->len);
476
477 aspath_put(a->aspath);
478 a->aspath = aspath_get(np, nlen);
479 free(np);
480 attr_free(a, attr);
481 }
482
483 uint32_t
aspath_neighbor(struct aspath * aspath)484 aspath_neighbor(struct aspath *aspath)
485 {
486 /*
487 * Empty aspath is OK -- internal AS route.
488 * Additionally the RFC specifies that if the path starts with an
489 * AS_SET the neighbor AS is also the local AS.
490 */
491 if (aspath->len == 0 ||
492 aspath->data[0] != AS_SEQUENCE)
493 return (rde_local_as());
494 return (aspath_extract(aspath->data, 0));
495 }
496
497 static uint16_t
aspath_count(const void * data,uint16_t len)498 aspath_count(const void *data, uint16_t len)
499 {
500 const uint8_t *seg;
501 uint16_t cnt, seg_size;
502 uint8_t seg_type, seg_len;
503
504 cnt = 0;
505 seg = data;
506 for (; len > 0; len -= seg_size, seg += seg_size) {
507 seg_type = seg[0];
508 seg_len = seg[1];
509 seg_size = 2 + sizeof(uint32_t) * seg_len;
510
511 if (seg_type == AS_SET)
512 cnt += 1;
513 else
514 cnt += seg_len;
515
516 if (seg_size > len)
517 fatalx("%s: would overflow", __func__);
518 }
519 return (cnt);
520 }
521
522 /*
523 * The origin AS number derived from a Route as follows:
524 * o the rightmost AS in the final segment of the AS_PATH attribute
525 * in the Route if that segment is of type AS_SEQUENCE, or
526 * o the BGP speaker's own AS number if that segment is of type
527 * AS_CONFED_SEQUENCE or AS_CONFED_SET or if the AS_PATH is empty,
528 * o the distinguished value "NONE" if the final segment of the
529 * AS_PATH attribute is of any other type.
530 */
531 static uint32_t
aspath_extract_origin(const void * data,uint16_t len)532 aspath_extract_origin(const void *data, uint16_t len)
533 {
534 const uint8_t *seg;
535 uint32_t as = AS_NONE;
536 uint16_t seg_size;
537 uint8_t seg_len;
538
539 /* AS_PATH is empty */
540 if (len == 0)
541 return (rde_local_as());
542
543 seg = data;
544 for (; len > 0; len -= seg_size, seg += seg_size) {
545 seg_len = seg[1];
546 seg_size = 2 + sizeof(uint32_t) * seg_len;
547
548 if (len == seg_size && seg[0] == AS_SEQUENCE) {
549 as = aspath_extract(seg, seg_len - 1);
550 }
551 if (seg_size > len)
552 fatalx("%s: would overflow", __func__);
553 }
554 return (as);
555 }
556
557 static uint16_t
aspath_countlength(struct aspath * aspath,uint16_t cnt,int headcnt)558 aspath_countlength(struct aspath *aspath, uint16_t cnt, int headcnt)
559 {
560 const uint8_t *seg;
561 uint16_t seg_size, len, clen;
562 uint8_t seg_type = 0, seg_len = 0;
563
564 seg = aspath->data;
565 clen = 0;
566 for (len = aspath->len; len > 0 && cnt > 0;
567 len -= seg_size, seg += seg_size) {
568 seg_type = seg[0];
569 seg_len = seg[1];
570 seg_size = 2 + sizeof(uint32_t) * seg_len;
571
572 if (seg_type == AS_SET)
573 cnt -= 1;
574 else if (seg_len > cnt) {
575 seg_len = cnt;
576 clen += 2 + sizeof(uint32_t) * cnt;
577 break;
578 } else
579 cnt -= seg_len;
580
581 clen += seg_size;
582
583 if (seg_size > len)
584 fatalx("%s: would overflow", __func__);
585 }
586 if (headcnt > 0 && seg_type == AS_SEQUENCE && headcnt + seg_len < 256)
587 /* no need for additional header from the new aspath. */
588 clen -= 2;
589
590 return (clen);
591 }
592
593 static void
aspath_countcopy(struct aspath * aspath,uint16_t cnt,uint8_t * buf,uint16_t size,int headcnt)594 aspath_countcopy(struct aspath *aspath, uint16_t cnt, uint8_t *buf,
595 uint16_t size, int headcnt)
596 {
597 const uint8_t *seg;
598 uint16_t seg_size, len;
599 uint8_t seg_type, seg_len;
600
601 if (headcnt > 0)
602 /*
603 * additional room because we steal the segment header
604 * from the other aspath
605 */
606 size += 2;
607 seg = aspath->data;
608 for (len = aspath->len; len > 0 && cnt > 0;
609 len -= seg_size, seg += seg_size) {
610 seg_type = seg[0];
611 seg_len = seg[1];
612 seg_size = 2 + sizeof(uint32_t) * seg_len;
613
614 if (seg_type == AS_SET)
615 cnt -= 1;
616 else if (seg_len > cnt) {
617 seg_len = cnt + headcnt;
618 seg_size = 2 + sizeof(uint32_t) * cnt;
619 cnt = 0;
620 } else {
621 cnt -= seg_len;
622 if (cnt == 0)
623 seg_len += headcnt;
624 }
625
626 memcpy(buf, seg, seg_size);
627 buf[0] = seg_type;
628 buf[1] = seg_len;
629 buf += seg_size;
630 if (size < seg_size)
631 fatalx("%s: would overflow", __func__);
632 size -= seg_size;
633 }
634 }
635
636 int
aspath_loopfree(struct aspath * aspath,uint32_t myAS)637 aspath_loopfree(struct aspath *aspath, uint32_t myAS)
638 {
639 uint8_t *seg;
640 uint16_t len, seg_size;
641 uint8_t i, seg_len;
642
643 seg = aspath->data;
644 for (len = aspath->len; len > 0; len -= seg_size, seg += seg_size) {
645 seg_len = seg[1];
646 seg_size = 2 + sizeof(uint32_t) * seg_len;
647
648 for (i = 0; i < seg_len; i++) {
649 if (myAS == aspath_extract(seg, i))
650 return (0);
651 }
652
653 if (seg_size > len)
654 fatalx("%s: would overflow", __func__);
655 }
656 return (1);
657 }
658
659 static int
as_compare(struct filter_as * f,uint32_t as,uint32_t neighas)660 as_compare(struct filter_as *f, uint32_t as, uint32_t neighas)
661 {
662 uint32_t match;
663
664 if (f->flags & AS_FLAG_AS_SET_NAME) /* should not happen */
665 return (0);
666 if (f->flags & AS_FLAG_AS_SET)
667 return (as_set_match(f->aset, as));
668
669 if (f->flags & AS_FLAG_NEIGHBORAS)
670 match = neighas;
671 else
672 match = f->as_min;
673
674 switch (f->op) {
675 case OP_NONE:
676 case OP_EQ:
677 if (as == match)
678 return (1);
679 break;
680 case OP_NE:
681 if (as != match)
682 return (1);
683 break;
684 case OP_RANGE:
685 if (as >= f->as_min && as <= f->as_max)
686 return (1);
687 break;
688 case OP_XRANGE:
689 if (as < f->as_min || as > f->as_max)
690 return (1);
691 break;
692 }
693 return (0);
694 }
695
696 /* we need to be able to search more than one as */
697 int
aspath_match(struct aspath * aspath,struct filter_as * f,uint32_t neighas)698 aspath_match(struct aspath *aspath, struct filter_as *f, uint32_t neighas)
699 {
700 const uint8_t *seg;
701 int final;
702 uint16_t len, seg_size;
703 uint8_t i, seg_len;
704 uint32_t as = AS_NONE;
705
706 if (f->type == AS_EMPTY) {
707 if (aspath_length(aspath) == 0)
708 return (1);
709 else
710 return (0);
711 }
712
713 /* just check the leftmost AS */
714 if (f->type == AS_PEER) {
715 as = aspath_neighbor(aspath);
716 if (as_compare(f, as, neighas))
717 return (1);
718 else
719 return (0);
720 }
721
722 seg = aspath->data;
723 len = aspath->len;
724 for (; len >= 6; len -= seg_size, seg += seg_size) {
725 seg_len = seg[1];
726 seg_size = 2 + sizeof(uint32_t) * seg_len;
727
728 final = (len == seg_size);
729
730 if (f->type == AS_SOURCE) {
731 /*
732 * Just extract the rightmost AS
733 * but if that segment is an AS_SET then the rightmost
734 * AS of a previous AS_SEQUENCE segment should be used.
735 * Because of that just look at AS_SEQUENCE segments.
736 */
737 if (seg[0] == AS_SEQUENCE)
738 as = aspath_extract(seg, seg_len - 1);
739 /* not yet in the final segment */
740 if (!final)
741 continue;
742 if (as_compare(f, as, neighas))
743 return (1);
744 else
745 return (0);
746 }
747 /* AS_TRANSIT or AS_ALL */
748 for (i = 0; i < seg_len; i++) {
749 /*
750 * the source (rightmost) AS is excluded from
751 * AS_TRANSIT matches.
752 */
753 if (final && i == seg_len - 1 && f->type == AS_TRANSIT)
754 return (0);
755 as = aspath_extract(seg, i);
756 if (as_compare(f, as, neighas))
757 return (1);
758 }
759
760 if (seg_size > len)
761 fatalx("%s: would overflow", __func__);
762 }
763 return (0);
764 }
765
766 /*
767 * Returns a new prepended aspath. Old needs to be freed by caller.
768 */
769 u_char *
aspath_prepend(struct aspath * asp,uint32_t as,int quantum,uint16_t * len)770 aspath_prepend(struct aspath *asp, uint32_t as, int quantum, uint16_t *len)
771 {
772 u_char *p;
773 int l, overflow = 0, shift = 0, size, wpos = 0;
774 uint8_t type;
775
776 /* lunatic prepends are blocked in the parser and limited */
777
778 /* first calculate new size */
779 if (asp->len > 0) {
780 if (asp->len < 2)
781 fatalx("aspath_prepend: bad aspath length");
782 type = asp->data[0];
783 size = asp->data[1];
784 } else {
785 /* empty as path */
786 type = AS_SET;
787 size = 0;
788 }
789
790 if (quantum > 255)
791 fatalx("aspath_prepend: preposterous prepend");
792 if (quantum == 0) {
793 /* no change needed but return a copy */
794 p = malloc(asp->len);
795 if (p == NULL)
796 fatal("%s", __func__);
797 memcpy(p, asp->data, asp->len);
798 *len = asp->len;
799 return (p);
800 } else if (type == AS_SET || size + quantum > 255) {
801 /* need to attach a new AS_SEQUENCE */
802 l = 2 + quantum * sizeof(uint32_t) + asp->len;
803 if (type == AS_SET)
804 overflow = quantum;
805 else
806 overflow = size + quantum - 255;
807 } else
808 l = quantum * sizeof(uint32_t) + asp->len;
809
810 quantum -= overflow;
811
812 p = malloc(l);
813 if (p == NULL)
814 fatal("%s", __func__);
815
816 /* first prepends */
817 as = htonl(as);
818 if (overflow > 0) {
819 p[wpos++] = AS_SEQUENCE;
820 p[wpos++] = overflow;
821
822 for (; overflow > 0; overflow--) {
823 memcpy(p + wpos, &as, sizeof(uint32_t));
824 wpos += sizeof(uint32_t);
825 }
826 }
827 if (quantum > 0) {
828 shift = 2;
829 p[wpos++] = AS_SEQUENCE;
830 p[wpos++] = quantum + size;
831
832 for (; quantum > 0; quantum--) {
833 memcpy(p + wpos, &as, sizeof(uint32_t));
834 wpos += sizeof(uint32_t);
835 }
836 }
837 memcpy(p + wpos, asp->data + shift, asp->len - shift);
838
839 *len = l;
840 return (p);
841 }
842
843 /*
844 * Returns a new aspath where neighbor_as is replaced by local_as.
845 */
846 u_char *
aspath_override(struct aspath * asp,uint32_t neighbor_as,uint32_t local_as,uint16_t * len)847 aspath_override(struct aspath *asp, uint32_t neighbor_as, uint32_t local_as,
848 uint16_t *len)
849 {
850 u_char *p, *seg, *nseg;
851 uint32_t as;
852 uint16_t l, seg_size;
853 uint8_t i, seg_len, seg_type;
854
855 p = malloc(asp->len);
856 if (p == NULL)
857 fatal("%s", __func__);
858
859 seg = asp->data;
860 nseg = p;
861 for (l = asp->len; l > 0; l -= seg_size, seg += seg_size) {
862 *nseg++ = seg_type = seg[0];
863 *nseg++ = seg_len = seg[1];
864 seg_size = 2 + sizeof(uint32_t) * seg_len;
865
866 for (i = 0; i < seg_len; i++) {
867 as = aspath_extract(seg, i);
868 if (as == neighbor_as)
869 as = local_as;
870 as = htonl(as);
871 memcpy(nseg, &as, sizeof(as));
872 nseg += sizeof(as);
873 }
874
875 if (seg_size > l)
876 fatalx("%s: would overflow", __func__);
877 }
878
879 *len = asp->len;
880 return (p);
881 }
882
883 int
aspath_lenmatch(struct aspath * a,enum aslen_spec type,u_int aslen)884 aspath_lenmatch(struct aspath *a, enum aslen_spec type, u_int aslen)
885 {
886 uint8_t *seg;
887 uint32_t as, lastas = 0;
888 u_int count = 0;
889 uint16_t len, seg_size;
890 uint8_t i, seg_len, seg_type;
891
892 if (type == ASLEN_MAX) {
893 if (aslen < aspath_count(a->data, a->len))
894 return (1);
895 else
896 return (0);
897 }
898
899 /* type == ASLEN_SEQ */
900 seg = a->data;
901 for (len = a->len; len > 0; len -= seg_size, seg += seg_size) {
902 seg_type = seg[0];
903 seg_len = seg[1];
904 seg_size = 2 + sizeof(uint32_t) * seg_len;
905
906 for (i = 0; i < seg_len; i++) {
907 as = aspath_extract(seg, i);
908 if (as == lastas) {
909 if (aslen < ++count)
910 return (1);
911 } else if (seg_type == AS_SET) {
912 /* AS path 3 { 4 3 7 } 3 will have count = 3 */
913 continue;
914 } else
915 count = 1;
916 lastas = as;
917 }
918
919 if (seg_size > len)
920 fatalx("%s: would overflow", __func__);
921 }
922 return (0);
923 }
924