GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/bgpd/rde_attr.c Lines: 0 727 0.0 %
Date: 2017-11-13 Branches: 0 520 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: rde_attr.c,v 1.100 2017/05/31 10:44:00 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/types.h>
22
#include <sys/queue.h>
23
24
#include <netinet/in.h>
25
26
#include <limits.h>
27
#include <stdlib.h>
28
#include <stdio.h>
29
#include <string.h>
30
#include <siphash.h>
31
32
#include "bgpd.h"
33
#include "rde.h"
34
#include "log.h"
35
36
int
37
attr_write(void *p, u_int16_t p_len, u_int8_t flags, u_int8_t type,
38
    void *data, u_int16_t data_len)
39
{
40
	u_char		*b = p;
41
	u_int16_t	 tmp, tot_len = 2; /* attribute header (without len) */
42
43
	flags &= ~ATTR_DEFMASK;
44
	if (data_len > 255) {
45
		tot_len += 2 + data_len;
46
		flags |= ATTR_EXTLEN;
47
	} else {
48
		tot_len += 1 + data_len;
49
	}
50
51
	if (tot_len > p_len)
52
		return (-1);
53
54
	*b++ = flags;
55
	*b++ = type;
56
	if (data_len > 255) {
57
		tmp = htons(data_len);
58
		memcpy(b, &tmp, sizeof(tmp));
59
		b += 2;
60
	} else
61
		*b++ = (u_char)data_len;
62
63
	if (data_len != 0)
64
		memcpy(b, data, data_len);
65
66
	return (tot_len);
67
}
68
69
int
70
attr_writebuf(struct ibuf *buf, u_int8_t flags, u_int8_t type, void *data,
71
    u_int16_t data_len)
72
{
73
	u_char	hdr[4];
74
75
	flags &= ~ATTR_DEFMASK;
76
	if (data_len > 255) {
77
		flags |= ATTR_EXTLEN;
78
		hdr[2] = (data_len >> 8) & 0xff;
79
		hdr[3] = data_len & 0xff;
80
	} else {
81
		hdr[2] = data_len & 0xff;
82
	}
83
84
	hdr[0] = flags;
85
	hdr[1] = type;
86
87
	if (ibuf_add(buf, hdr, flags & ATTR_EXTLEN ? 4 : 3) == -1)
88
		return (-1);
89
	if (ibuf_add(buf, data, data_len) == -1)
90
		return (-1);
91
	return (0);
92
}
93
94
/* optional attribute specific functions */
95
int		 attr_diff(struct attr *, struct attr *);
96
struct attr	*attr_alloc(u_int8_t, u_int8_t, const void *, u_int16_t);
97
struct attr	*attr_lookup(u_int8_t, u_int8_t, const void *, u_int16_t);
98
void		 attr_put(struct attr *);
99
100
struct attr_table {
101
	struct attr_list	*hashtbl;
102
	u_int32_t		 hashmask;
103
} attrtable;
104
105
SIPHASH_KEY attrtablekey;
106
107
#define ATTR_HASH(x)				\
108
	&attrtable.hashtbl[(x) & attrtable.hashmask]
109
110
void
111
attr_init(u_int32_t hashsize)
112
{
113
	u_int32_t	hs, i;
114
115
	arc4random_buf(&attrtablekey, sizeof(attrtablekey));
116
	for (hs = 1; hs < hashsize; hs <<= 1)
117
		;
118
	attrtable.hashtbl = calloc(hs, sizeof(struct attr_list));
119
	if (attrtable.hashtbl == NULL)
120
		fatal("attr_init");
121
122
	for (i = 0; i < hs; i++)
123
		LIST_INIT(&attrtable.hashtbl[i]);
124
125
	attrtable.hashmask = hs - 1;
126
}
127
128
void
129
attr_shutdown(void)
130
{
131
	u_int32_t	i;
132
133
	for (i = 0; i <= attrtable.hashmask; i++)
134
		if (!LIST_EMPTY(&attrtable.hashtbl[i]))
135
			log_warnx("attr_shutdown: free non-free table");
136
137
	free(attrtable.hashtbl);
138
}
139
140
int
141
attr_optadd(struct rde_aspath *asp, u_int8_t flags, u_int8_t type,
142
    void *data, u_int16_t len)
143
{
144
	u_int8_t	 l;
145
	struct attr	*a, *t;
146
	void		*p;
147
148
	/* known optional attributes were validated previously */
149
	if ((a = attr_lookup(flags, type, data, len)) == NULL)
150
		a = attr_alloc(flags, type, data, len);
151
152
	/* attribute allowed only once */
153
	for (l = 0; l < asp->others_len; l++) {
154
		if (asp->others[l] == NULL)
155
			break;
156
		if (type == asp->others[l]->type) {
157
			if (a->refcnt == 0)
158
				attr_put(a);
159
			return (-1);
160
		}
161
	}
162
163
	/* add attribute to the table but first bump refcnt */
164
	a->refcnt++;
165
	rdemem.attr_refs++;
166
167
	for (l = 0; l < asp->others_len; l++) {
168
		if (asp->others[l] == NULL) {
169
			asp->others[l] = a;
170
			return (0);
171
		}
172
		/* list is sorted */
173
		if (a->type < asp->others[l]->type) {
174
			t = asp->others[l];
175
			asp->others[l] = a;
176
			a = t;
177
		}
178
	}
179
180
	/* no empty slot found, need to realloc */
181
	if (asp->others_len == UCHAR_MAX)
182
		fatalx("attr_optadd: others_len overflow");
183
184
	asp->others_len++;
185
	if ((p = reallocarray(asp->others,
186
	    asp->others_len, sizeof(struct attr *))) == NULL)
187
		fatal("attr_optadd");
188
	asp->others = p;
189
190
	/* l stores the size of others before resize */
191
	asp->others[l] = a;
192
	return (0);
193
}
194
195
struct attr *
196
attr_optget(const struct rde_aspath *asp, u_int8_t type)
197
{
198
	u_int8_t	 l;
199
200
	for (l = 0; l < asp->others_len; l++) {
201
		if (asp->others[l] == NULL)
202
			break;
203
		if (type == asp->others[l]->type)
204
			return (asp->others[l]);
205
		if (type < asp->others[l]->type)
206
			break;
207
	}
208
	return (NULL);
209
}
210
211
void
212
attr_copy(struct rde_aspath *t, struct rde_aspath *s)
213
{
214
	u_int8_t	l;
215
216
	if (t->others != NULL)
217
		attr_freeall(t);
218
219
	t->others_len = s->others_len;
220
	if (t->others_len == 0) {
221
		t->others = NULL;
222
		return;
223
	}
224
225
	if ((t->others = calloc(s->others_len, sizeof(struct attr *))) == 0)
226
		fatal("attr_copy");
227
228
	for (l = 0; l < t->others_len; l++) {
229
		if (s->others[l] == NULL)
230
			break;
231
		s->others[l]->refcnt++;
232
		rdemem.attr_refs++;
233
		t->others[l] = s->others[l];
234
	}
235
}
236
237
int
238
attr_diff(struct attr *oa, struct attr *ob)
239
{
240
	int	r;
241
242
	if (ob == NULL)
243
		return (1);
244
	if (oa == NULL)
245
		return (-1);
246
	if (oa->flags > ob->flags)
247
		return (1);
248
	if (oa->flags < ob->flags)
249
		return (-1);
250
	if (oa->type > ob->type)
251
		return (1);
252
	if (oa->type < ob->type)
253
		return (-1);
254
	if (oa->len > ob->len)
255
		return (1);
256
	if (oa->len < ob->len)
257
		return (-1);
258
	r = memcmp(oa->data, ob->data, oa->len);
259
	if (r > 0)
260
		return (1);
261
	if (r < 0)
262
		return (-1);
263
264
	fatalx("attr_diff: equal attributes encountered");
265
	return (0);
266
}
267
268
int
269
attr_compare(struct rde_aspath *a, struct rde_aspath *b)
270
{
271
	u_int8_t	l, min;
272
273
	min = a->others_len < b->others_len ? a->others_len : b->others_len;
274
	for (l = 0; l < min; l++)
275
		if (a->others[l] != b->others[l])
276
			return (attr_diff(a->others[l], b->others[l]));
277
278
	if (a->others_len < b->others_len) {
279
		for (; l < b->others_len; l++)
280
			if (b->others[l] != NULL)
281
				return (-1);
282
	} else if (a->others_len > b->others_len) {
283
		for (; l < a->others_len; l++)
284
			if (a->others[l] != NULL)
285
				return (1);
286
	}
287
288
	return (0);
289
}
290
291
void
292
attr_free(struct rde_aspath *asp, struct attr *attr)
293
{
294
	u_int8_t	l;
295
296
	for (l = 0; l < asp->others_len; l++)
297
		if (asp->others[l] == attr) {
298
			attr_put(asp->others[l]);
299
			for (++l; l < asp->others_len; l++)
300
				asp->others[l - 1] = asp->others[l];
301
			asp->others[asp->others_len - 1] = NULL;
302
			return;
303
		}
304
305
	/* no realloc() because the slot may be reused soon */
306
}
307
308
void
309
attr_freeall(struct rde_aspath *asp)
310
{
311
	u_int8_t	l;
312
313
	for (l = 0; l < asp->others_len; l++)
314
		attr_put(asp->others[l]);
315
316
	free(asp->others);
317
	asp->others = NULL;
318
	asp->others_len = 0;
319
}
320
321
struct attr *
322
attr_alloc(u_int8_t flags, u_int8_t type, const void *data, u_int16_t len)
323
{
324
	struct attr	*a;
325
	SIPHASH_CTX	ctx;
326
327
	a = calloc(1, sizeof(struct attr));
328
	if (a == NULL)
329
		fatal("attr_optadd");
330
	rdemem.attr_cnt++;
331
332
	flags &= ~ATTR_DEFMASK;	/* normalize mask */
333
	a->flags = flags;
334
	a->type = type;
335
	a->len = len;
336
	if (len != 0) {
337
		if ((a->data = malloc(len)) == NULL)
338
			fatal("attr_optadd");
339
340
		rdemem.attr_dcnt++;
341
		rdemem.attr_data += len;
342
		memcpy(a->data, data, len);
343
	} else
344
		a->data = NULL;
345
346
	SipHash24_Init(&ctx, &attrtablekey);
347
	SipHash24_Update(&ctx, &flags, sizeof(flags));
348
	SipHash24_Update(&ctx, &type, sizeof(type));
349
	SipHash24_Update(&ctx, &len, sizeof(len));
350
	SipHash24_Update(&ctx, a->data, a->len);
351
	a->hash = SipHash24_End(&ctx);
352
	LIST_INSERT_HEAD(ATTR_HASH(a->hash), a, entry);
353
354
	return (a);
355
}
356
357
struct attr *
358
attr_lookup(u_int8_t flags, u_int8_t type, const void *data, u_int16_t len)
359
{
360
	struct attr_list	*head;
361
	struct attr		*a;
362
	u_int32_t		 hash;
363
	SIPHASH_CTX		ctx;
364
365
	flags &= ~ATTR_DEFMASK;	/* normalize mask */
366
367
	SipHash24_Init(&ctx, &attrtablekey);
368
	SipHash24_Update(&ctx, &flags, sizeof(flags));
369
	SipHash24_Update(&ctx, &type, sizeof(type));
370
	SipHash24_Update(&ctx, &len, sizeof(len));
371
	SipHash24_Update(&ctx, data, len);
372
	hash = SipHash24_End(&ctx);
373
	head = ATTR_HASH(hash);
374
375
	LIST_FOREACH(a, head, entry) {
376
		if (hash == a->hash && type == a->type &&
377
		    flags == a->flags && len == a->len &&
378
		    memcmp(data, a->data, len) == 0)
379
			return (a);
380
	}
381
	return (NULL);
382
}
383
384
void
385
attr_put(struct attr *a)
386
{
387
	if (a == NULL)
388
		return;
389
390
	rdemem.attr_refs--;
391
	if (--a->refcnt > 0)
392
		/* somebody still holds a reference */
393
		return;
394
395
	/* unlink */
396
	LIST_REMOVE(a, entry);
397
398
	if (a->len != 0)
399
		rdemem.attr_dcnt--;
400
	rdemem.attr_data -= a->len;
401
	rdemem.attr_cnt--;
402
	free(a->data);
403
	free(a);
404
}
405
406
/* aspath specific functions */
407
408
u_int16_t	 aspath_countlength(struct aspath *, u_int16_t, int);
409
void		 aspath_countcopy(struct aspath *, u_int16_t, u_int8_t *,
410
		     u_int16_t, int);
411
struct aspath	*aspath_lookup(const void *, u_int16_t);
412
413
struct aspath_table {
414
	struct aspath_list	*hashtbl;
415
	u_int32_t		 hashmask;
416
} astable;
417
418
SIPHASH_KEY astablekey;
419
420
#define ASPATH_HASH(x)				\
421
	&astable.hashtbl[(x) & astable.hashmask]
422
423
int
424
aspath_verify(void *data, u_int16_t len, int as4byte)
425
{
426
	u_int8_t	*seg = data;
427
	u_int16_t	 seg_size, as_size = 2;
428
	u_int8_t	 seg_len, seg_type;
429
	int		 i, error = 0;
430
431
	if (len & 1)
432
		/* odd length aspath are invalid */
433
		return (AS_ERR_BAD);
434
435
	if (as4byte)
436
		as_size = 4;
437
438
	for (; len > 0; len -= seg_size, seg += seg_size) {
439
		if (len < 2)	/* header length check */
440
			return (AS_ERR_BAD);
441
		seg_type = seg[0];
442
		seg_len = seg[1];
443
444
		/*
445
		 * BGP confederations should not show up but consider them
446
		 * as a soft error which invalidates the path but keeps the
447
		 * bgp session running.
448
		 */
449
		if (seg_type == AS_CONFED_SEQUENCE || seg_type == AS_CONFED_SET)
450
			error = AS_ERR_SOFT;
451
		if (seg_type != AS_SET && seg_type != AS_SEQUENCE &&
452
		    seg_type != AS_CONFED_SEQUENCE && seg_type != AS_CONFED_SET)
453
			return (AS_ERR_TYPE);
454
455
		seg_size = 2 + as_size * seg_len;
456
457
		if (seg_size > len)
458
			return (AS_ERR_LEN);
459
460
		if (seg_size == 0)
461
			/* empty aspath segments are not allowed */
462
			return (AS_ERR_BAD);
463
464
		 /* RFC 7607 - AS 0 is considered malformed */
465
		for (i = 0; i < seg_len; i++) {
466
			if (aspath_extract(seg, i) == 0)
467
				return (AS_ERR_SOFT);
468
		}
469
	}
470
	return (error);	/* aspath is valid but probably not loop free */
471
}
472
473
void
474
aspath_init(u_int32_t hashsize)
475
{
476
	u_int32_t	hs, i;
477
478
	for (hs = 1; hs < hashsize; hs <<= 1)
479
		;
480
	astable.hashtbl = calloc(hs, sizeof(struct aspath_list));
481
	if (astable.hashtbl == NULL)
482
		fatal("aspath_init");
483
484
	for (i = 0; i < hs; i++)
485
		LIST_INIT(&astable.hashtbl[i]);
486
487
	astable.hashmask = hs - 1;
488
	arc4random_buf(&astablekey, sizeof(astablekey));
489
}
490
491
void
492
aspath_shutdown(void)
493
{
494
	u_int32_t	i;
495
496
	for (i = 0; i <= astable.hashmask; i++)
497
		if (!LIST_EMPTY(&astable.hashtbl[i]))
498
			log_warnx("aspath_shutdown: free non-free table");
499
500
	free(astable.hashtbl);
501
}
502
503
struct aspath *
504
aspath_get(void *data, u_int16_t len)
505
{
506
	struct aspath_list	*head;
507
	struct aspath		*aspath;
508
509
	/* The aspath must already have been checked for correctness. */
510
	aspath = aspath_lookup(data, len);
511
	if (aspath == NULL) {
512
		aspath = malloc(ASPATH_HEADER_SIZE + len);
513
		if (aspath == NULL)
514
			fatal("aspath_get");
515
516
		rdemem.aspath_cnt++;
517
		rdemem.aspath_size += ASPATH_HEADER_SIZE + len;
518
519
		aspath->refcnt = 0;
520
		aspath->len = len;
521
		aspath->ascnt = aspath_count(data, len);
522
		memcpy(aspath->data, data, len);
523
524
		/* link */
525
		head = ASPATH_HASH(SipHash24(&astablekey, aspath->data,
526
		    aspath->len));
527
		LIST_INSERT_HEAD(head, aspath, entry);
528
	}
529
	aspath->refcnt++;
530
	rdemem.aspath_refs++;
531
532
	return (aspath);
533
}
534
535
void
536
aspath_put(struct aspath *aspath)
537
{
538
	if (aspath == NULL)
539
		return;
540
541
	rdemem.aspath_refs--;
542
	if (--aspath->refcnt > 0) {
543
		/* somebody still holds a reference */
544
		return;
545
	}
546
547
	/* unlink */
548
	LIST_REMOVE(aspath, entry);
549
550
	rdemem.aspath_cnt--;
551
	rdemem.aspath_size -= ASPATH_HEADER_SIZE + aspath->len;
552
	free(aspath);
553
}
554
555
u_char *
556
aspath_inflate(void *data, u_int16_t len, u_int16_t *newlen)
557
{
558
	u_int8_t	*seg, *nseg, *ndata;
559
	u_int16_t	 seg_size, olen, nlen;
560
	u_int8_t	 seg_len;
561
562
	/* first calculate the length of the aspath */
563
	seg = data;
564
	nlen = 0;
565
	for (olen = len; olen > 0; olen -= seg_size, seg += seg_size) {
566
		seg_len = seg[1];
567
		seg_size = 2 + sizeof(u_int16_t) * seg_len;
568
		nlen += 2 + sizeof(u_int32_t) * seg_len;
569
570
		if (seg_size > olen)
571
			fatalx("aspath_inflate: would overflow");
572
	}
573
574
	*newlen = nlen;
575
	if ((ndata = malloc(nlen)) == NULL)
576
		fatal("aspath_inflate");
577
578
	/* then copy the aspath */
579
	seg = data;
580
	for (nseg = ndata; nseg < ndata + nlen; ) {
581
		*nseg++ = *seg++;
582
		*nseg++ = seg_len = *seg++;
583
		for (; seg_len > 0; seg_len--) {
584
			*nseg++ = 0;
585
			*nseg++ = 0;
586
			*nseg++ = *seg++;
587
			*nseg++ = *seg++;
588
		}
589
	}
590
591
	return (ndata);
592
}
593
594
/* convert a 4 byte aspath to a 2byte one. data is freed by aspath_deflate */
595
u_char *
596
aspath_deflate(u_char *data, u_int16_t *len, int *flagnew)
597
{
598
	u_int8_t	*seg, *nseg, *ndata;
599
	u_int32_t	 as;
600
	int		 i;
601
	u_int16_t	 seg_size, olen, nlen;
602
	u_int8_t	 seg_len;
603
604
	/* first calculate the length of the aspath */
605
	nlen = 0;
606
	seg = data;
607
	olen = *len;
608
	for (; olen > 0; olen -= seg_size, seg += seg_size) {
609
		seg_len = seg[1];
610
		seg_size = 2 + sizeof(u_int32_t) * seg_len;
611
		nlen += 2 + sizeof(u_int16_t) * seg_len;
612
613
		if (seg_size > olen)
614
			fatalx("aspath_deflate: would overflow");
615
	}
616
617
	if ((ndata = malloc(nlen)) == NULL)
618
		fatal("aspath_deflate");
619
620
	/* then copy the aspath */
621
	seg = data;
622
	olen = *len;
623
	for (nseg = ndata; seg < data + olen; seg += seg_size) {
624
		*nseg++ = seg[0];
625
		*nseg++ = seg_len = seg[1];
626
		seg_size = 2 + sizeof(u_int32_t) * seg_len;
627
628
		for (i = 0; i < seg_len; i++) {
629
			as = aspath_extract(seg, i);
630
			if (as > USHRT_MAX) {
631
				as = AS_TRANS;
632
				*flagnew = 1;
633
			}
634
			*nseg++ = (as >> 8) & 0xff;
635
			*nseg++ = as & 0xff;
636
		}
637
	}
638
639
	free(data);
640
	*len = nlen;
641
	return (ndata);
642
}
643
644
void
645
aspath_merge(struct rde_aspath *a, struct attr *attr)
646
{
647
	u_int8_t	*np;
648
	u_int16_t	 ascnt, diff, nlen, difflen;
649
	int		 hroom = 0;
650
651
	ascnt = aspath_count(attr->data, attr->len);
652
	if (ascnt > a->aspath->ascnt) {
653
		/* ASPATH is shorter then AS4_PATH no way to merge */
654
		attr_free(a, attr);
655
		return;
656
	}
657
658
	diff = a->aspath->ascnt - ascnt;
659
	if (diff && attr->len > 2 && attr->data[0] == AS_SEQUENCE)
660
		hroom = attr->data[1];
661
	difflen = aspath_countlength(a->aspath, diff, hroom);
662
	nlen = attr->len + difflen;
663
664
	if ((np = malloc(nlen)) == NULL)
665
		fatal("aspath_merge");
666
667
	/* copy head from old aspath */
668
	aspath_countcopy(a->aspath, diff, np, difflen, hroom);
669
670
	/* copy tail from new aspath */
671
	if (hroom > 0)
672
		memcpy(np + nlen - attr->len + 2, attr->data + 2,
673
		    attr->len - 2);
674
	else
675
		memcpy(np + nlen - attr->len, attr->data, attr->len);
676
677
	aspath_put(a->aspath);
678
	a->aspath = aspath_get(np, nlen);
679
	free(np);
680
	attr_free(a, attr);
681
}
682
683
u_char *
684
aspath_dump(struct aspath *aspath)
685
{
686
	return (aspath->data);
687
}
688
689
u_int16_t
690
aspath_length(struct aspath *aspath)
691
{
692
	return (aspath->len);
693
}
694
695
u_int16_t
696
aspath_count(const void *data, u_int16_t len)
697
{
698
	const u_int8_t	*seg;
699
	u_int16_t	 cnt, seg_size;
700
	u_int8_t	 seg_type, seg_len;
701
702
	cnt = 0;
703
	seg = data;
704
	for (; len > 0; len -= seg_size, seg += seg_size) {
705
		seg_type = seg[0];
706
		seg_len = seg[1];
707
		seg_size = 2 + sizeof(u_int32_t) * seg_len;
708
709
		if (seg_type == AS_SET)
710
			cnt += 1;
711
		else
712
			cnt += seg_len;
713
714
		if (seg_size > len)
715
			fatalx("aspath_count: would overflow");
716
	}
717
	return (cnt);
718
}
719
720
u_int16_t
721
aspath_countlength(struct aspath *aspath, u_int16_t cnt, int headcnt)
722
{
723
	const u_int8_t	*seg;
724
	u_int16_t	 seg_size, len, clen;
725
	u_int8_t	 seg_type = 0, seg_len = 0;
726
727
	seg = aspath->data;
728
	clen = 0;
729
	for (len = aspath->len; len > 0 && cnt > 0;
730
	    len -= seg_size, seg += seg_size) {
731
		seg_type = seg[0];
732
		seg_len = seg[1];
733
		seg_size = 2 + sizeof(u_int32_t) * seg_len;
734
735
		if (seg_type == AS_SET)
736
			cnt -= 1;
737
		else if (seg_len > cnt) {
738
			seg_len = cnt;
739
			clen += 2 + sizeof(u_int32_t) * cnt;
740
			break;
741
		} else
742
			cnt -= seg_len;
743
744
		clen += seg_size;
745
746
		if (seg_size > len)
747
			fatalx("aspath_countlength: would overflow");
748
	}
749
	if (headcnt > 0 && seg_type == AS_SEQUENCE && headcnt + seg_len < 256)
750
		/* no need for additional header from the new aspath. */
751
		clen -= 2;
752
753
	return (clen);
754
}
755
756
void
757
aspath_countcopy(struct aspath *aspath, u_int16_t cnt, u_int8_t *buf,
758
    u_int16_t size, int headcnt)
759
{
760
	const u_int8_t	*seg;
761
	u_int16_t	 seg_size, len;
762
	u_int8_t	 seg_type, seg_len;
763
764
	if (headcnt > 0)
765
		/*
766
		 * additional room because we steal the segment header
767
		 * from the other aspath
768
		 */
769
		size += 2;
770
	seg = aspath->data;
771
	for (len = aspath->len; len > 0 && cnt > 0;
772
	    len -= seg_size, seg += seg_size) {
773
		seg_type = seg[0];
774
		seg_len = seg[1];
775
		seg_size = 2 + sizeof(u_int32_t) * seg_len;
776
777
		if (seg_type == AS_SET)
778
			cnt -= 1;
779
		else if (seg_len > cnt) {
780
			seg_len = cnt + headcnt;
781
			seg_size = 2 + sizeof(u_int32_t) * cnt;
782
			cnt = 0;
783
		} else {
784
			cnt -= seg_len;
785
			if (cnt == 0)
786
				seg_len += headcnt;
787
		}
788
789
		memcpy(buf, seg, seg_size);
790
		buf[0] = seg_type;
791
		buf[1] = seg_len;
792
		buf += seg_size;
793
		if (size < seg_size)
794
			fatalx("aspath_countlength: would overflow");
795
		size -= seg_size;
796
	}
797
}
798
799
u_int32_t
800
aspath_neighbor(struct aspath *aspath)
801
{
802
	/* Empty aspath is OK -- internal AS route. */
803
	if (aspath->len == 0)
804
		return (rde_local_as());
805
	return (aspath_extract(aspath->data, 0));
806
}
807
808
int
809
aspath_loopfree(struct aspath *aspath, u_int32_t myAS)
810
{
811
	u_int8_t	*seg;
812
	u_int16_t	 len, seg_size;
813
	u_int8_t	 i, seg_len;
814
815
	seg = aspath->data;
816
	for (len = aspath->len; len > 0; len -= seg_size, seg += seg_size) {
817
		seg_len = seg[1];
818
		seg_size = 2 + sizeof(u_int32_t) * seg_len;
819
820
		for (i = 0; i < seg_len; i++) {
821
			if (myAS == aspath_extract(seg, i))
822
				return (0);
823
		}
824
825
		if (seg_size > len)
826
			fatalx("aspath_loopfree: would overflow");
827
	}
828
	return (1);
829
}
830
831
int
832
aspath_compare(struct aspath *a1, struct aspath *a2)
833
{
834
	int r;
835
836
	if (a1->len > a2->len)
837
		return (1);
838
	if (a1->len < a2->len)
839
		return (-1);
840
	r = memcmp(a1->data, a2->data, a1->len);
841
	if (r > 0)
842
		return (1);
843
	if (r < 0)
844
		return (-1);
845
	return (0);
846
}
847
848
struct aspath *
849
aspath_lookup(const void *data, u_int16_t len)
850
{
851
	struct aspath_list	*head;
852
	struct aspath		*aspath;
853
	u_int32_t		 hash;
854
855
	hash = SipHash24(&astablekey, data, len);
856
	head = ASPATH_HASH(hash);
857
858
	LIST_FOREACH(aspath, head, entry) {
859
		if (len == aspath->len && memcmp(data, aspath->data, len) == 0)
860
			return (aspath);
861
	}
862
	return (NULL);
863
}
864
865
866
/*
867
 * Returns a new prepended aspath. Old needs to be freed by caller.
868
 */
869
u_char *
870
aspath_prepend(struct aspath *asp, u_int32_t as, int quantum, u_int16_t *len)
871
{
872
	u_char		*p;
873
	int		 l, overflow = 0, shift = 0, size, wpos = 0;
874
	u_int8_t	 type;
875
876
	/* lunatic prepends are blocked in the parser and limited */
877
878
	/* first calculate new size */
879
	if (asp->len > 0) {
880
		if (asp->len < 2)
881
			fatalx("aspath_prepend: bad aspath length");
882
		type = asp->data[0];
883
		size = asp->data[1];
884
	} else {
885
		/* empty as path */
886
		type = AS_SET;
887
		size = 0;
888
	}
889
890
	if (quantum > 255)
891
		fatalx("aspath_prepend: preposterous prepend");
892
	if (quantum == 0) {
893
		/* no change needed but return a copy */
894
		p = malloc(asp->len);
895
		if (p == NULL)
896
			fatal("aspath_prepend");
897
		memcpy(p, asp->data, asp->len);
898
		*len = asp->len;
899
		return (p);
900
	} else if (type == AS_SET || size + quantum > 255) {
901
		/* need to attach a new AS_SEQUENCE */
902
		l = 2 + quantum * sizeof(u_int32_t) + asp->len;
903
		if (type == AS_SET)
904
			overflow = quantum;
905
		else
906
			overflow = size + quantum - 255;
907
	} else
908
		l = quantum * sizeof(u_int32_t) + asp->len;
909
910
	quantum -= overflow;
911
912
	p = malloc(l);
913
	if (p == NULL)
914
		fatal("aspath_prepend");
915
916
	/* first prepends */
917
	as = htonl(as);
918
	if (overflow > 0) {
919
		p[wpos++] = AS_SEQUENCE;
920
		p[wpos++] = overflow;
921
922
		for (; overflow > 0; overflow--) {
923
			memcpy(p + wpos, &as, sizeof(u_int32_t));
924
			wpos += sizeof(u_int32_t);
925
		}
926
	}
927
	if (quantum > 0) {
928
		shift = 2;
929
		p[wpos++] = AS_SEQUENCE;
930
		p[wpos++] = quantum + size;
931
932
		for (; quantum > 0; quantum--) {
933
			memcpy(p + wpos, &as, sizeof(u_int32_t));
934
			wpos += sizeof(u_int32_t);
935
		}
936
	}
937
	memcpy(p + wpos, asp->data + shift, asp->len - shift);
938
939
	*len = l;
940
	return (p);
941
}
942
943
int
944
aspath_lenmatch(struct aspath *a, enum aslen_spec type, u_int aslen)
945
{
946
	u_int8_t	*seg;
947
	u_int32_t	 as, lastas = 0;
948
	u_int		 count = 0;
949
	u_int16_t	 len, seg_size;
950
	u_int8_t	 i, seg_len;
951
952
	if (type == ASLEN_MAX) {
953
		if (aslen < aspath_count(a->data, a->len))
954
			return (1);
955
		else
956
			return (0);
957
	}
958
959
	/* type == ASLEN_SEQ */
960
	seg = a->data;
961
	for (len = a->len; len > 0; len -= seg_size, seg += seg_size) {
962
		seg_len = seg[1];
963
		seg_size = 2 + sizeof(u_int32_t) * seg_len;
964
965
		for (i = 0; i < seg_len; i++) {
966
			/* what should we do with AS_SET? */
967
			as = aspath_extract(seg, i);
968
			if (as == lastas) {
969
				if (aslen < ++count)
970
					return (1);
971
			} else
972
				count = 1;
973
			lastas = as;
974
		}
975
	}
976
	return (0);
977
}
978
979
/*
980
 * Functions handling communities and extended communities.
981
 */
982
983
int community_ext_matchone(struct filter_extcommunity *, u_int16_t, u_int64_t);
984
985
int
986
community_match(struct rde_aspath *asp, int as, int type)
987
{
988
	struct attr	*a;
989
	u_int8_t	*p;
990
	u_int16_t	 eas, etype, len;
991
992
	a = attr_optget(asp, ATTR_COMMUNITIES);
993
	if (a == NULL)
994
		/* no communities, no match */
995
		return (0);
996
997
	p = a->data;
998
	for (len = a->len / 4; len > 0; len--) {
999
		eas = *p++;
1000
		eas <<= 8;
1001
		eas |= *p++;
1002
		etype = *p++;
1003
		etype <<= 8;
1004
		etype |= *p++;
1005
		if ((as == COMMUNITY_ANY || (u_int16_t)as == eas) &&
1006
		    (type == COMMUNITY_ANY || (u_int16_t)type == etype))
1007
			return (1);
1008
	}
1009
	return (0);
1010
}
1011
1012
int
1013
community_set(struct rde_aspath *asp, int as, int type)
1014
{
1015
	struct attr	*attr;
1016
	u_int8_t	*p = NULL;
1017
	unsigned int	 i, ncommunities = 0;
1018
	u_int8_t	 f = ATTR_OPTIONAL|ATTR_TRANSITIVE;
1019
1020
	attr = attr_optget(asp, ATTR_COMMUNITIES);
1021
	if (attr != NULL) {
1022
		p = attr->data;
1023
		ncommunities = attr->len / 4;
1024
	}
1025
1026
	/* first check if the community is not already set */
1027
	for (i = 0; i < ncommunities; i++) {
1028
		if (as >> 8 == p[0] && (as & 0xff) == p[1] &&
1029
		    type >> 8 == p[2] && (type & 0xff) == p[3])
1030
			/* already present, nothing todo */
1031
			return (1);
1032
		p += 4;
1033
	}
1034
1035
	if (ncommunities++ >= USHRT_MAX / 4)
1036
		/* overflow */
1037
		return (0);
1038
1039
	if ((p = reallocarray(NULL, ncommunities, 4)) == NULL)
1040
		fatal("community_set");
1041
1042
	p[0] = as >> 8;
1043
	p[1] = as & 0xff;
1044
	p[2] = type >> 8;
1045
	p[3] = type & 0xff;
1046
1047
	if (attr != NULL) {
1048
		memcpy(p + 4, attr->data, attr->len);
1049
		f = attr->flags;
1050
		attr_free(asp, attr);
1051
	}
1052
1053
	attr_optadd(asp, f, ATTR_COMMUNITIES, p, ncommunities * 4);
1054
1055
	free(p);
1056
	return (1);
1057
}
1058
1059
void
1060
community_delete(struct rde_aspath *asp, int as, int type)
1061
{
1062
	struct attr	*attr;
1063
	u_int8_t	*p, *n;
1064
	u_int16_t	 l, len = 0;
1065
	u_int16_t	 eas, etype;
1066
	u_int8_t	 f;
1067
1068
	attr = attr_optget(asp, ATTR_COMMUNITIES);
1069
	if (attr == NULL)
1070
		/* no attr nothing to do */
1071
		return;
1072
1073
	p = attr->data;
1074
	for (l = 0; l < attr->len; l += 4) {
1075
		eas = *p++;
1076
		eas <<= 8;
1077
		eas |= *p++;
1078
		etype = *p++;
1079
		etype <<= 8;
1080
		etype |= *p++;
1081
1082
		if ((as == COMMUNITY_ANY || (u_int16_t)as == eas) &&
1083
		    (type == COMMUNITY_ANY || (u_int16_t)type == etype))
1084
			/* match */
1085
			continue;
1086
		len += 4;
1087
	}
1088
1089
	if (len == 0) {
1090
		attr_free(asp, attr);
1091
		return;
1092
	}
1093
1094
	if ((n = malloc(len)) == NULL)
1095
		fatal("community_delete");
1096
1097
	p = attr->data;
1098
	for (l = 0; l < len && p < attr->data + attr->len; ) {
1099
		eas = *p++;
1100
		eas <<= 8;
1101
		eas |= *p++;
1102
		etype = *p++;
1103
		etype <<= 8;
1104
		etype |= *p++;
1105
1106
		if ((as == COMMUNITY_ANY || (u_int16_t)as == eas) &&
1107
		    (type == COMMUNITY_ANY || (u_int16_t)type == etype))
1108
			/* match */
1109
			continue;
1110
		n[l++] = eas >> 8;
1111
		n[l++] = eas & 0xff;
1112
		n[l++] = etype >> 8;
1113
		n[l++] = etype & 0xff;
1114
	}
1115
1116
	f = attr->flags;
1117
1118
	attr_free(asp, attr);
1119
	attr_optadd(asp, f, ATTR_COMMUNITIES, n, len);
1120
	free(n);
1121
}
1122
1123
int
1124
community_ext_match(struct rde_aspath *asp, struct filter_extcommunity *c,
1125
    u_int16_t neighas)
1126
{
1127
	struct attr	*attr;
1128
	u_int8_t	*p;
1129
	u_int64_t	 ec;
1130
	u_int16_t	 len;
1131
1132
	attr = attr_optget(asp, ATTR_EXT_COMMUNITIES);
1133
	if (attr == NULL)
1134
		/* no communities, no match */
1135
		return (0);
1136
1137
	p = attr->data;
1138
	for (len = attr->len / sizeof(ec); len > 0; len--) {
1139
		memcpy(&ec, p, sizeof(ec));
1140
		if (community_ext_matchone(c, neighas, ec))
1141
			return (1);
1142
		p += sizeof(ec);
1143
	}
1144
1145
	return (0);
1146
}
1147
1148
int
1149
community_ext_set(struct rde_aspath *asp, struct filter_extcommunity *c,
1150
    u_int16_t neighas)
1151
{
1152
	struct attr	*attr;
1153
	u_int8_t	*p = NULL;
1154
	u_int64_t	 community;
1155
	unsigned int	 i, ncommunities = 0;
1156
	u_int8_t	 f = ATTR_OPTIONAL|ATTR_TRANSITIVE;
1157
1158
	if (community_ext_conv(c, neighas, &community))
1159
		return (0);
1160
1161
	attr = attr_optget(asp, ATTR_EXT_COMMUNITIES);
1162
	if (attr != NULL) {
1163
		p = attr->data;
1164
		ncommunities = attr->len / sizeof(community);
1165
	}
1166
1167
	/* first check if the community is not already set */
1168
	for (i = 0; i < ncommunities; i++) {
1169
		if (memcmp(&community, p, sizeof(community)) == 0)
1170
			/* already present, nothing todo */
1171
			return (1);
1172
		p += sizeof(community);
1173
	}
1174
1175
	if (ncommunities++ >= USHRT_MAX / sizeof(community))
1176
		/* overflow */
1177
		return (0);
1178
1179
	if ((p = reallocarray(NULL, ncommunities, sizeof(community))) == NULL)
1180
		fatal("community_ext_set");
1181
1182
	memcpy(p, &community, sizeof(community));
1183
	if (attr != NULL) {
1184
		memcpy(p + sizeof(community), attr->data, attr->len);
1185
		f = attr->flags;
1186
		attr_free(asp, attr);
1187
	}
1188
1189
	attr_optadd(asp, f, ATTR_EXT_COMMUNITIES, p,
1190
	    ncommunities * sizeof(community));
1191
1192
	free(p);
1193
	return (1);
1194
}
1195
1196
void
1197
community_ext_delete(struct rde_aspath *asp, struct filter_extcommunity *c,
1198
    u_int16_t neighas)
1199
{
1200
	struct attr	*attr;
1201
	u_int8_t	*p, *n;
1202
	u_int64_t	 community;
1203
	u_int16_t	 l, len = 0;
1204
	u_int8_t	 f;
1205
1206
	if (community_ext_conv(c, neighas, &community))
1207
		return;
1208
1209
	attr = attr_optget(asp, ATTR_EXT_COMMUNITIES);
1210
	if (attr == NULL)
1211
		/* no attr nothing to do */
1212
		return;
1213
1214
	p = attr->data;
1215
	for (l = 0; l < attr->len; l += sizeof(community)) {
1216
		if (memcmp(&community, p + l, sizeof(community)) == 0)
1217
			/* match */
1218
			continue;
1219
		len += sizeof(community);
1220
	}
1221
1222
	if (len == 0) {
1223
		attr_free(asp, attr);
1224
		return;
1225
	}
1226
1227
	if ((n = malloc(len)) == NULL)
1228
		fatal("community_delete");
1229
1230
	p = attr->data;
1231
	for (l = 0; l < len && p < attr->data + attr->len;
1232
	    p += sizeof(community)) {
1233
		if (memcmp(&community, p, sizeof(community)) == 0)
1234
			/* match */
1235
			continue;
1236
		memcpy(n + l, p, sizeof(community));
1237
		l += sizeof(community);
1238
	}
1239
1240
	f = attr->flags;
1241
1242
	attr_free(asp, attr);
1243
	attr_optadd(asp, f, ATTR_EXT_COMMUNITIES, n, len);
1244
	free(n);
1245
}
1246
1247
int
1248
community_ext_conv(struct filter_extcommunity *c, u_int16_t neighas,
1249
    u_int64_t *community)
1250
{
1251
	u_int64_t	com;
1252
	u_int32_t	ip;
1253
1254
	com = (u_int64_t)c->type << 56;
1255
	switch (c->type & EXT_COMMUNITY_VALUE) {
1256
	case EXT_COMMUNITY_TRANS_TWO_AS:
1257
		com |= (u_int64_t)c->subtype << 48;
1258
		com |= (u_int64_t)c->data.ext_as.as << 32;
1259
		com |= c->data.ext_as.val;
1260
		break;
1261
	case EXT_COMMUNITY_TRANS_IPV4:
1262
		com |= (u_int64_t)c->subtype << 48;
1263
		ip = ntohl(c->data.ext_ip.addr.s_addr);
1264
		com |= (u_int64_t)ip << 16;
1265
		com |= c->data.ext_ip.val;
1266
		break;
1267
	case EXT_COMMUNITY_TRANS_FOUR_AS:
1268
		com |= (u_int64_t)c->subtype << 48;
1269
		com |= (u_int64_t)c->data.ext_as4.as4 << 16;
1270
		com |= c->data.ext_as4.val;
1271
		break;
1272
	case EXT_COMMUNITY_TRANS_OPAQUE:
1273
		com |= (u_int64_t)c->subtype << 48;
1274
		com |= c->data.ext_opaq & EXT_COMMUNITY_OPAQUE_MAX;
1275
		break;
1276
	default:
1277
		com |= c->data.ext_opaq & 0xffffffffffffffULL;
1278
		break;
1279
	}
1280
1281
	*community = htobe64(com);
1282
1283
	return (0);
1284
}
1285
1286
int
1287
community_ext_matchone(struct filter_extcommunity *c, u_int16_t neighas,
1288
    u_int64_t community)
1289
{
1290
	u_int64_t	com, mask;
1291
	u_int32_t	ip;
1292
1293
	community = betoh64(community);
1294
1295
	com = (u_int64_t)c->type << 56;
1296
	mask = 0xffULL << 56;
1297
	if ((com & mask) != (community & mask))
1298
		return (0);
1299
1300
	switch (c->type & EXT_COMMUNITY_VALUE) {
1301
	case EXT_COMMUNITY_TRANS_TWO_AS:
1302
	case EXT_COMMUNITY_TRANS_IPV4:
1303
	case EXT_COMMUNITY_TRANS_FOUR_AS:
1304
	case EXT_COMMUNITY_TRANS_OPAQUE:
1305
		com = (u_int64_t)c->subtype << 48;
1306
		mask = 0xffULL << 48;
1307
		if ((com & mask) != (community & mask))
1308
			return (0);
1309
		break;
1310
	default:
1311
		com = c->data.ext_opaq & 0xffffffffffffffULL;
1312
		mask = 0xffffffffffffffULL;
1313
		if ((com & mask) == (community & mask))
1314
			return (1);
1315
		return (0);
1316
	}
1317
1318
1319
	switch (c->type & EXT_COMMUNITY_VALUE) {
1320
	case EXT_COMMUNITY_TRANS_TWO_AS:
1321
		com = (u_int64_t)c->data.ext_as.as << 32;
1322
		mask = 0xffffULL << 32;
1323
		if ((com & mask) != (community & mask))
1324
			return (0);
1325
1326
		com = c->data.ext_as.val;
1327
		mask = 0xffffffffULL;
1328
		if ((com & mask) == (community & mask))
1329
			return (1);
1330
		break;
1331
	case EXT_COMMUNITY_TRANS_IPV4:
1332
		ip = ntohl(c->data.ext_ip.addr.s_addr);
1333
		com = (u_int64_t)ip << 16;
1334
		mask = 0xffffffff0000ULL;
1335
		if ((com & mask) != (community & mask))
1336
			return (0);
1337
1338
		com = c->data.ext_ip.val;
1339
		mask = 0xffff;
1340
		if ((com & mask) == (community & mask))
1341
			return (1);
1342
		break;
1343
	case EXT_COMMUNITY_TRANS_FOUR_AS:
1344
		com = (u_int64_t)c->data.ext_as4.as4 << 16;
1345
		mask = 0xffffffffULL << 16;
1346
		if ((com & mask) != (community & mask))
1347
			return (0);
1348
1349
		com = c->data.ext_as4.val;
1350
		mask = 0xffff;
1351
		if ((com & mask) == (community & mask))
1352
			return (1);
1353
		break;
1354
	case EXT_COMMUNITY_TRANS_OPAQUE:
1355
		com = c->data.ext_opaq & EXT_COMMUNITY_OPAQUE_MAX;
1356
		mask = EXT_COMMUNITY_OPAQUE_MAX;
1357
		if ((com & mask) == (community & mask))
1358
			return (1);
1359
		break;
1360
	}
1361
1362
	return (0);
1363
}
1364
1365
int
1366
community_large_match(struct rde_aspath *asp, int64_t as, int64_t ld1,
1367
    int64_t ld2)
1368
{
1369
	struct wire_largecommunity	*bar;
1370
	struct attr	*a;
1371
	u_int8_t	*p;
1372
	u_int16_t	 len;
1373
	u_int32_t	 eas, eld1, eld2;
1374
1375
	a = attr_optget(asp, ATTR_LARGE_COMMUNITIES);
1376
	if (a == NULL)
1377
		/* no communities, no match */
1378
		return (0);
1379
1380
	p = a->data;
1381
	for (len = a->len / 12; len > 0; len--) {
1382
		bar = (struct wire_largecommunity *)p;
1383
		p += 12;
1384
		eas = betoh32(bar->as);
1385
		eld1 = betoh32(bar->ld1);
1386
		eld2 = betoh32(bar->ld2);
1387
1388
		if ((as == COMMUNITY_ANY || as == eas) &&
1389
		    (ld1 == COMMUNITY_ANY || ld1 == eld1) &&
1390
		    (ld2 == COMMUNITY_ANY || ld2 == eld2))
1391
			return (1);
1392
	}
1393
	return (0);
1394
}
1395
1396
int
1397
community_large_set(struct rde_aspath *asp, int64_t as, int64_t ld1,
1398
    int64_t ld2)
1399
{
1400
	struct wire_largecommunity	*bar;
1401
	struct attr	*attr;
1402
	u_int8_t	*p = NULL;
1403
	unsigned int	 i, ncommunities = 0;
1404
	u_int8_t	 f = ATTR_OPTIONAL|ATTR_TRANSITIVE;
1405
1406
	attr = attr_optget(asp, ATTR_LARGE_COMMUNITIES);
1407
	if (attr != NULL) {
1408
		p = attr->data;
1409
		ncommunities = attr->len / 12;
1410
	}
1411
1412
	/* first check if the community is not already set */
1413
	for (i = 0; i < ncommunities; i++) {
1414
		bar = (struct wire_largecommunity *)p;
1415
		if (bar->as == as && bar->ld1 == ld1 && bar->ld2 == ld2)
1416
			/* already present, nothing todo */
1417
			return (1);
1418
		p += 12;
1419
	}
1420
1421
	if (ncommunities++ >= USHRT_MAX / 12)
1422
		/* overflow */
1423
		return (0);
1424
1425
	if ((p = reallocarray(NULL, ncommunities, 12)) == NULL)
1426
		fatal("community_set");
1427
1428
	bar = (struct wire_largecommunity *)p;
1429
	bar->as = htobe32(as);
1430
	bar->ld1 = htobe32(ld1);
1431
	bar->ld2 = htobe32(ld2);
1432
1433
	if (attr != NULL) {
1434
		memcpy(p + 12, attr->data, attr->len);
1435
		f = attr->flags;
1436
		attr_free(asp, attr);
1437
	}
1438
1439
	attr_optadd(asp, f, ATTR_LARGE_COMMUNITIES, p, ncommunities * 12);
1440
1441
	free(p);
1442
	return (1);
1443
}
1444
1445
void
1446
community_large_delete(struct rde_aspath *asp, int64_t as, int64_t ld1,
1447
    int64_t ld2)
1448
{
1449
	struct wire_largecommunity	*bar;
1450
	struct attr	*attr;
1451
	u_int8_t	*p, *n;
1452
	u_int16_t	 l = 0, len = 0;
1453
	u_int32_t	 eas, eld1, eld2;
1454
	u_int8_t	 f;
1455
1456
	attr = attr_optget(asp, ATTR_LARGE_COMMUNITIES);
1457
	if (attr == NULL)
1458
		/* no attr nothing to do */
1459
		return;
1460
1461
	p = attr->data;
1462
	for (len = 0; l < attr->len; l += 12) {
1463
		bar = (struct wire_largecommunity *)p;
1464
		p += 12;
1465
		eas = betoh32(bar->as);
1466
		eld1 = betoh32(bar->ld1);
1467
		eld2 = betoh32(bar->ld2);
1468
1469
		if ((as == COMMUNITY_ANY || as == eas) &&
1470
		    (ld1 == COMMUNITY_ANY || ld1 == eld1) &&
1471
		    (ld2 == COMMUNITY_ANY || ld2 == eld2))
1472
			/* match */
1473
			continue;
1474
		len += 12;
1475
	}
1476
1477
	if (len == 0) {
1478
		attr_free(asp, attr);
1479
		return;
1480
	}
1481
1482
	if ((n = malloc(len)) == NULL)
1483
		fatal("community_delete");
1484
1485
	p = attr->data;
1486
	for (l = 0; l < len && p < attr->data + attr->len; ) {
1487
		bar = (struct wire_largecommunity *)p;
1488
		p += 12;
1489
		eas = betoh32(bar->as);
1490
		eld1 = betoh32(bar->ld1);
1491
		eld2 = betoh32(bar->ld2);
1492
1493
		if ((as == COMMUNITY_ANY || as == eas) &&
1494
		    (ld1 == COMMUNITY_ANY || ld1 == eld1) &&
1495
		    (ld2 == COMMUNITY_ANY || ld2 == eld2))
1496
			/* match */
1497
			continue;
1498
		memcpy(n + l, bar, sizeof(*bar));
1499
		l += 12;
1500
	}
1501
1502
	f = attr->flags;
1503
1504
	attr_free(asp, attr);
1505
	attr_optadd(asp, f, ATTR_LARGE_COMMUNITIES, n, len);
1506
	free(n);
1507
}
1508
1509
1510
u_char *
1511
community_ext_delete_non_trans(u_char *data, u_int16_t len, u_int16_t *newlen)
1512
{
1513
	u_int8_t	*ext = data, *newdata;
1514
	u_int16_t	l, nlen = 0;
1515
1516
	for (l = 0; l < len; l += sizeof(u_int64_t)) {
1517
		if (!(ext[l] & EXT_COMMUNITY_TRANSITIVE))
1518
			nlen += sizeof(u_int64_t);
1519
	}
1520
1521
	if (nlen == 0) {
1522
		*newlen = 0;
1523
		return NULL;
1524
	}
1525
1526
	newdata = malloc(nlen);
1527
	if (newdata == NULL)
1528
		fatal("%s", __func__);;
1529
1530
	for (l = 0, nlen = 0; l < len; l += sizeof(u_int64_t)) {
1531
		if (!(ext[l] & EXT_COMMUNITY_TRANSITIVE)) {
1532
			memcpy(newdata + nlen, ext + l, sizeof(u_int64_t));
1533
			nlen += sizeof(u_int64_t);
1534
		}
1535
	}
1536
1537
	*newlen = nlen;
1538
	return newdata;
1539
}