Line data Source code
1 : /* AS path management routines.
2 : * Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro
3 : * Copyright (C) 2005 Sun Microsystems, Inc.
4 : *
5 : * This file is part of GNU Zebra.
6 : *
7 : * GNU Zebra is free software; you can redistribute it and/or modify it
8 : * under the terms of the GNU General Public License as published by the
9 : * Free Software Foundation; either version 2, or (at your option) any
10 : * later version.
11 : *
12 : * GNU Zebra is distributed in the hope that it will be useful, but
13 : * WITHOUT ANY WARRANTY; without even the implied warranty of
14 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : * General Public License for more details.
16 : *
17 : * You should have received a copy of the GNU General Public License along
18 : * with this program; see the file COPYING; if not, write to the Free Software
19 : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 : */
21 :
22 : #include <zebra.h>
23 :
24 : #include "hash.h"
25 : #include "memory.h"
26 : #include "vector.h"
27 : #include "log.h"
28 : #include "stream.h"
29 : #include "command.h"
30 : #include "jhash.h"
31 : #include "queue.h"
32 : #include "filter.h"
33 :
34 : #include "bgpd/bgpd.h"
35 : #include "bgpd/bgp_aspath.h"
36 : #include "bgpd/bgp_debug.h"
37 : #include "bgpd/bgp_attr.h"
38 : #include "bgpd/bgp_errors.h"
39 :
40 : /* Attr. Flags and Attr. Type Code. */
41 : #define AS_HEADER_SIZE 2
42 :
43 : /* Now FOUR octets are used for AS value. */
44 : #define AS_VALUE_SIZE sizeof(as_t)
45 : /* This is the old one */
46 : #define AS16_VALUE_SIZE sizeof(as16_t)
47 :
48 : /* Maximum protocol segment length value */
49 : #define AS_SEGMENT_MAX 255
50 :
51 : /* The following length and size macros relate specifically to Quagga's
52 : * internal representation of AS-Segments, not per se to the on-wire
53 : * sizes and lengths. At present (200508) they sort of match, however
54 : * the ONLY functions which should now about the on-wire syntax are
55 : * aspath_put, assegment_put and assegment_parse.
56 : *
57 : * aspath_put returns bytes written, the only definitive record of
58 : * size of wire-format attribute..
59 : */
60 :
61 : /* Calculated size in bytes of ASN segment data to hold N ASN's */
62 : #define ASSEGMENT_DATA_SIZE(N, S) \
63 : ((N) * ((S) ? AS_VALUE_SIZE : AS16_VALUE_SIZE))
64 :
65 : /* Calculated size of segment struct to hold N ASN's */
66 : #define ASSEGMENT_SIZE(N,S) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N,S))
67 :
68 : /* AS segment octet length. */
69 : #define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S)
70 :
71 : /* AS_SEQUENCE segments can be packed together */
72 : /* Can the types of X and Y be considered for packing? */
73 : #define ASSEGMENT_TYPES_PACKABLE(X, Y) \
74 : (((X)->type == (Y)->type) && ((X)->type == AS_SEQUENCE))
75 : /* Types and length of X,Y suitable for packing? */
76 : #define ASSEGMENTS_PACKABLE(X, Y) \
77 : (ASSEGMENT_TYPES_PACKABLE((X), (Y)) \
78 : && (((X)->length + (Y)->length) <= AS_SEGMENT_MAX))
79 :
80 : /* As segment header - the on-wire representation
81 : * NOT the internal representation!
82 : */
83 : struct assegment_header {
84 : uint8_t type;
85 : uint8_t length;
86 : };
87 :
88 : /* Hash for aspath. This is the top level structure of AS path. */
89 : static struct hash *ashash;
90 :
91 : /* Stream for SNMP. See aspath_snmp_pathseg */
92 : static struct stream *snmp_stream;
93 :
94 : /* Callers are required to initialize the memory */
95 7 : static as_t *assegment_data_new(int num)
96 : {
97 7 : return (XMALLOC(MTYPE_AS_SEG_DATA, ASSEGMENT_DATA_SIZE(num, 1)));
98 : }
99 :
100 7 : static void assegment_data_free(as_t *asdata)
101 : {
102 14 : XFREE(MTYPE_AS_SEG_DATA, asdata);
103 : }
104 :
105 : const char *const aspath_segment_type_str[] = {
106 : "as-invalid", "as-set", "as-sequence", "as-confed-sequence",
107 : "as-confed-set"
108 : };
109 :
110 : /* Get a new segment. Note that 0 is an allowed length,
111 : * and will result in a segment with no allocated data segment.
112 : * the caller should immediately assign data to the segment, as the segment
113 : * otherwise is not generally valid
114 : */
115 6 : static struct assegment *assegment_new(uint8_t type, unsigned short length)
116 : {
117 6 : struct assegment *new;
118 :
119 6 : new = XCALLOC(MTYPE_AS_SEG, sizeof(struct assegment));
120 :
121 6 : if (length)
122 6 : new->as = assegment_data_new(length);
123 :
124 6 : new->length = length;
125 6 : new->type = type;
126 :
127 6 : return new;
128 : }
129 :
130 6 : static void assegment_free(struct assegment *seg)
131 : {
132 6 : if (!seg)
133 : return;
134 :
135 6 : assegment_data_free(seg->as);
136 6 : memset(seg, 0xfe, sizeof(struct assegment));
137 6 : XFREE(MTYPE_AS_SEG, seg);
138 :
139 6 : return;
140 : }
141 :
142 : /* free entire chain of segments */
143 3 : static void assegment_free_all(struct assegment *seg)
144 : {
145 3 : struct assegment *prev;
146 :
147 14 : while (seg) {
148 6 : prev = seg;
149 6 : seg = seg->next;
150 6 : assegment_free(prev);
151 : }
152 : }
153 :
154 : /* Duplicate just the given assegment and its data */
155 1 : static struct assegment *assegment_dup(struct assegment *seg)
156 : {
157 1 : struct assegment *new;
158 :
159 1 : new = assegment_new(seg->type, seg->length);
160 1 : memcpy(new->as, seg->as, ASSEGMENT_DATA_SIZE(new->length, 1));
161 :
162 1 : return new;
163 : }
164 :
165 : /* Duplicate entire chain of assegments, return the head */
166 1 : static struct assegment *assegment_dup_all(struct assegment *seg)
167 : {
168 1 : struct assegment *new = NULL;
169 1 : struct assegment *head = NULL;
170 :
171 2 : while (seg) {
172 1 : if (head) {
173 0 : new->next = assegment_dup(seg);
174 0 : new = new->next;
175 : } else
176 1 : head = new = assegment_dup(seg);
177 :
178 1 : seg = seg->next;
179 : }
180 1 : return head;
181 : }
182 :
183 : /* prepend the as number to given segment, given num of times */
184 1 : static struct assegment *assegment_prepend_asns(struct assegment *seg,
185 : as_t asnum, int num)
186 : {
187 1 : as_t *newas;
188 1 : int i;
189 :
190 1 : if (!num)
191 : return seg;
192 :
193 1 : if (num >= AS_SEGMENT_MAX)
194 : return seg; /* we don't do huge prepends */
195 :
196 1 : newas = assegment_data_new(seg->length + num);
197 1 : if (newas == NULL)
198 : return seg;
199 :
200 2 : for (i = 0; i < num; i++)
201 1 : newas[i] = asnum;
202 :
203 1 : memcpy(newas + num, seg->as, ASSEGMENT_DATA_SIZE(seg->length, 1));
204 1 : assegment_data_free(seg->as);
205 1 : seg->as = newas;
206 1 : seg->length += num;
207 :
208 1 : return seg;
209 : }
210 :
211 : /* append given array of as numbers to the segment */
212 0 : static struct assegment *assegment_append_asns(struct assegment *seg,
213 : as_t *asnos, int num)
214 : {
215 0 : as_t *newas;
216 :
217 0 : if (!seg)
218 : return seg;
219 :
220 0 : newas = XREALLOC(MTYPE_AS_SEG_DATA, seg->as,
221 : ASSEGMENT_DATA_SIZE(seg->length + num, 1));
222 :
223 0 : seg->as = newas;
224 0 : memcpy(seg->as + seg->length, asnos,
225 : ASSEGMENT_DATA_SIZE(num, 1));
226 0 : seg->length += num;
227 0 : return seg;
228 : }
229 :
230 0 : static int int_cmp(const void *p1, const void *p2)
231 : {
232 0 : const as_t *as1 = p1;
233 0 : const as_t *as2 = p2;
234 :
235 0 : return (*as1 == *as2) ? 0 : ((*as1 > *as2) ? 1 : -1);
236 : }
237 :
238 : /* normalise the segment.
239 : * In particular, merge runs of AS_SEQUENCEs into one segment
240 : * Internally, we do not care about the wire segment length limit, and
241 : * we want each distinct AS_PATHs to have the exact same internal
242 : * representation - eg, so that our hashing actually works..
243 : */
244 3 : static struct assegment *assegment_normalise(struct assegment *head)
245 : {
246 3 : struct assegment *seg = head, *pin;
247 3 : struct assegment *tmp;
248 :
249 3 : if (!head)
250 : return head;
251 :
252 6 : while (seg) {
253 3 : pin = seg;
254 :
255 : /* Sort values SET segments, for determinism in paths to aid
256 : * creation of hash values / path comparisons
257 : * and because it helps other lesser implementations ;)
258 : */
259 3 : if (seg->type == AS_SET || seg->type == AS_CONFED_SET) {
260 0 : int tail = 0;
261 0 : int i;
262 :
263 0 : qsort(seg->as, seg->length, sizeof(as_t), int_cmp);
264 :
265 : /* weed out dupes */
266 0 : for (i = 1; i < seg->length; i++) {
267 0 : if (seg->as[tail] == seg->as[i])
268 0 : continue;
269 :
270 0 : tail++;
271 0 : if (tail < i)
272 0 : seg->as[tail] = seg->as[i];
273 : }
274 : /* seg->length can be 0.. */
275 0 : if (seg->length)
276 0 : seg->length = tail + 1;
277 : }
278 :
279 : /* read ahead from the current, pinned segment while the
280 : * segments
281 : * are packable/mergeable. Append all following packable
282 : * segments
283 : * to the segment we have pinned and remove these appended
284 : * segments.
285 : */
286 3 : while (pin->next && ASSEGMENT_TYPES_PACKABLE(pin, pin->next)) {
287 0 : tmp = pin->next;
288 0 : seg = pin->next;
289 :
290 : /* append the next sequence to the pinned sequence */
291 0 : pin = assegment_append_asns(pin, seg->as, seg->length);
292 :
293 : /* bypass the next sequence */
294 0 : pin->next = seg->next;
295 :
296 : /* get rid of the now referenceless segment */
297 0 : assegment_free(tmp);
298 : }
299 :
300 : seg = pin->next;
301 : }
302 : return head;
303 : }
304 :
305 0 : static struct aspath *aspath_new(void)
306 : {
307 0 : return XCALLOC(MTYPE_AS_PATH, sizeof(struct aspath));
308 : }
309 :
310 : /* Free AS path structure. */
311 6 : void aspath_free(struct aspath *aspath)
312 : {
313 6 : if (!aspath)
314 : return;
315 6 : if (aspath->segments)
316 6 : assegment_free_all(aspath->segments);
317 6 : XFREE(MTYPE_AS_STR, aspath->str);
318 :
319 6 : if (aspath->json) {
320 0 : json_object_free(aspath->json);
321 0 : aspath->json = NULL;
322 : }
323 :
324 6 : XFREE(MTYPE_AS_PATH, aspath);
325 : }
326 :
327 : /* Unintern aspath from AS path bucket. */
328 23 : void aspath_unintern(struct aspath **aspath)
329 : {
330 23 : struct aspath *ret;
331 23 : struct aspath *asp;
332 :
333 23 : if (!*aspath)
334 : return;
335 :
336 19 : asp = *aspath;
337 :
338 19 : if (asp->refcnt)
339 19 : asp->refcnt--;
340 :
341 19 : if (asp->refcnt == 0) {
342 : /* This aspath must exist in aspath hash table. */
343 3 : ret = hash_release(ashash, asp);
344 3 : assert(ret != NULL);
345 3 : aspath_free(asp);
346 3 : *aspath = NULL;
347 : }
348 : }
349 :
350 : /* Return the start or end delimiters for a particular Segment type */
351 : #define AS_SEG_START 0
352 : #define AS_SEG_END 1
353 0 : static char aspath_delimiter_char(uint8_t type, uint8_t which)
354 : {
355 0 : int i;
356 0 : struct {
357 : int type;
358 : char start;
359 : char end;
360 0 : } aspath_delim_char[] = {{AS_SET, '{', '}'},
361 : {AS_CONFED_SET, '[', ']'},
362 : {AS_CONFED_SEQUENCE, '(', ')'},
363 : {0}};
364 :
365 0 : for (i = 0; aspath_delim_char[i].type != 0; i++) {
366 0 : if (aspath_delim_char[i].type == type) {
367 0 : if (which == AS_SEG_START)
368 0 : return aspath_delim_char[i].start;
369 0 : else if (which == AS_SEG_END)
370 0 : return aspath_delim_char[i].end;
371 : }
372 : }
373 : return ' ';
374 : }
375 :
376 : /* countup asns from this segment and index onward */
377 : static int assegment_count_asns(struct assegment *seg, int from)
378 : {
379 : int count = 0;
380 0 : while (seg) {
381 6 : if (!from)
382 6 : count += seg->length;
383 : else {
384 : count += (seg->length - from);
385 : from = 0;
386 : }
387 6 : seg = seg->next;
388 : }
389 6 : return count;
390 : }
391 :
392 0 : unsigned int aspath_count_confeds(struct aspath *aspath)
393 : {
394 0 : int count = 0;
395 0 : struct assegment *seg = aspath->segments;
396 :
397 0 : while (seg) {
398 0 : if (seg->type == AS_CONFED_SEQUENCE)
399 0 : count += seg->length;
400 0 : else if (seg->type == AS_CONFED_SET)
401 0 : count++;
402 :
403 0 : seg = seg->next;
404 : }
405 0 : return count;
406 : }
407 :
408 0 : unsigned int aspath_count_hops(const struct aspath *aspath)
409 : {
410 0 : int count = 0;
411 0 : struct assegment *seg = aspath->segments;
412 :
413 0 : while (seg) {
414 0 : if (seg->type == AS_SEQUENCE)
415 0 : count += seg->length;
416 0 : else if (seg->type == AS_SET)
417 0 : count++;
418 :
419 0 : seg = seg->next;
420 : }
421 0 : return count;
422 : }
423 :
424 : /* Check if aspath has AS_SET or AS_CONFED_SET */
425 0 : bool aspath_check_as_sets(struct aspath *aspath)
426 : {
427 0 : struct assegment *seg = aspath->segments;
428 :
429 0 : while (seg) {
430 0 : if (seg->type == AS_SET || seg->type == AS_CONFED_SET)
431 : return true;
432 0 : seg = seg->next;
433 : }
434 : return false;
435 : }
436 :
437 : /* Check if aspath has BGP_AS_ZERO */
438 7 : bool aspath_check_as_zero(struct aspath *aspath)
439 : {
440 7 : struct assegment *seg = aspath->segments;
441 7 : unsigned int i;
442 :
443 12 : while (seg) {
444 11 : for (i = 0; i < seg->length; i++)
445 6 : if (seg->as[i] == BGP_AS_ZERO)
446 : return true;
447 5 : seg = seg->next;
448 : }
449 :
450 : return false;
451 : }
452 :
453 : /* Estimate size aspath /might/ take if encoded into an
454 : * ASPATH attribute.
455 : *
456 : * This is a quick estimate, not definitive! aspath_put()
457 : * may return a different number!!
458 : */
459 0 : unsigned int aspath_size(struct aspath *aspath)
460 : {
461 0 : int size = 0;
462 0 : struct assegment *seg = aspath->segments;
463 :
464 0 : while (seg) {
465 0 : size += ASSEGMENT_SIZE(seg->length, 1);
466 0 : seg = seg->next;
467 : }
468 0 : return size;
469 : }
470 :
471 : /* Return highest public ASN in path */
472 0 : as_t aspath_highest(struct aspath *aspath)
473 : {
474 0 : struct assegment *seg = aspath->segments;
475 0 : as_t highest = 0;
476 0 : unsigned int i;
477 :
478 0 : while (seg) {
479 0 : for (i = 0; i < seg->length; i++)
480 0 : if (seg->as[i] > highest
481 0 : && !BGP_AS_IS_PRIVATE(seg->as[i]))
482 0 : highest = seg->as[i];
483 0 : seg = seg->next;
484 : }
485 0 : return highest;
486 : }
487 :
488 : /* Return the left-most ASN in path */
489 0 : as_t aspath_leftmost(struct aspath *aspath)
490 : {
491 0 : struct assegment *seg = aspath->segments;
492 0 : as_t leftmost = 0;
493 :
494 0 : if (seg && seg->length && seg->type == AS_SEQUENCE)
495 0 : leftmost = seg->as[0];
496 :
497 0 : return leftmost;
498 : }
499 :
500 : /* Return 1 if there are any 4-byte ASes in the path */
501 3 : bool aspath_has_as4(struct aspath *aspath)
502 : {
503 3 : struct assegment *seg = aspath->segments;
504 3 : unsigned int i;
505 :
506 6 : while (seg) {
507 7 : for (i = 0; i < seg->length; i++)
508 4 : if (seg->as[i] > BGP_AS_MAX)
509 : return true;
510 3 : seg = seg->next;
511 : }
512 : return false;
513 : }
514 :
515 : /* Convert aspath structure to string expression. */
516 9 : static void aspath_make_str_count(struct aspath *as, bool make_json)
517 : {
518 9 : struct assegment *seg;
519 9 : int str_size;
520 9 : int len = 0;
521 9 : char *str_buf;
522 9 : json_object *jaspath_segments = NULL;
523 9 : json_object *jseg = NULL;
524 9 : json_object *jseg_list = NULL;
525 :
526 9 : if (make_json) {
527 0 : as->json = json_object_new_object();
528 0 : jaspath_segments = json_object_new_array();
529 : }
530 :
531 : /* Empty aspath. */
532 9 : if (!as->segments) {
533 3 : if (make_json) {
534 0 : json_object_string_add(as->json, "string", "Local");
535 0 : json_object_object_add(as->json, "segments",
536 : jaspath_segments);
537 0 : json_object_int_add(as->json, "length", 0);
538 : }
539 3 : as->str = XMALLOC(MTYPE_AS_STR, 1);
540 3 : as->str[0] = '\0';
541 3 : as->str_len = 0;
542 3 : return;
543 : }
544 :
545 12 : seg = as->segments;
546 :
547 : /* ASN takes 5 to 10 chars plus separator, see below.
548 : * If there is one differing segment type, we need an additional
549 : * 2 chars for segment delimiters, and the final '\0'.
550 : * Hopefully this is large enough to avoid hitting the realloc
551 : * code below for most common sequences.
552 : *
553 : * This was changed to 10 after the well-known BGP assertion, which
554 : * had hit some parts of the Internet in May of 2009.
555 : */
556 : #define ASN_STR_LEN (10 + 1)
557 6 : str_size = MAX(assegment_count_asns(seg, 0) * ASN_STR_LEN + 2 + 1,
558 : ASPATH_STR_DEFAULT_LEN);
559 6 : str_buf = XMALLOC(MTYPE_AS_STR, str_size);
560 :
561 12 : while (seg) {
562 6 : int i;
563 6 : char separator;
564 :
565 : /* Check AS type validity. Set separator for segment */
566 6 : switch (seg->type) {
567 : case AS_SET:
568 : case AS_CONFED_SET:
569 : separator = ',';
570 : break;
571 6 : case AS_SEQUENCE:
572 : case AS_CONFED_SEQUENCE:
573 6 : separator = ' ';
574 6 : break;
575 0 : default:
576 0 : XFREE(MTYPE_AS_STR, str_buf);
577 0 : as->str = NULL;
578 0 : as->str_len = 0;
579 0 : json_object_free(as->json);
580 0 : as->json = NULL;
581 :
582 0 : return;
583 : }
584 :
585 : /* We might need to increase str_buf, particularly if path has
586 : * differing segments types, our initial guesstimate above will
587 : * have been wrong. Need 10 chars for ASN, a separator each and
588 : * potentially two segment delimiters, plus a space between each
589 : * segment and trailing zero.
590 : *
591 : * This definitely didn't work with the value of 5 bytes and
592 : * 32-bit ASNs.
593 : */
594 : #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
595 6 : if ((len + SEGMENT_STR_LEN(seg)) > str_size) {
596 0 : str_size = len + SEGMENT_STR_LEN(seg);
597 0 : str_buf = XREALLOC(MTYPE_AS_STR, str_buf, str_size);
598 : }
599 : #undef ASN_STR_LEN
600 : #undef SEGMENT_STR_LEN
601 :
602 6 : if (seg->type != AS_SEQUENCE)
603 0 : len += snprintf(
604 0 : str_buf + len, str_size - len, "%c",
605 0 : aspath_delimiter_char(seg->type, AS_SEG_START));
606 :
607 6 : if (make_json)
608 0 : jseg_list = json_object_new_array();
609 :
610 : /* write out the ASNs, with their separators, bar the last one*/
611 14 : for (i = 0; i < seg->length; i++) {
612 8 : if (make_json)
613 0 : json_object_array_add(
614 : jseg_list,
615 0 : json_object_new_int64(seg->as[i]));
616 :
617 8 : len += snprintf(str_buf + len, str_size - len, "%u",
618 8 : seg->as[i]);
619 :
620 8 : if (i < (seg->length - 1))
621 2 : len += snprintf(str_buf + len, str_size - len,
622 : "%c", separator);
623 : }
624 :
625 6 : if (make_json) {
626 0 : jseg = json_object_new_object();
627 0 : json_object_string_add(
628 : jseg, "type",
629 0 : aspath_segment_type_str[seg->type]);
630 0 : json_object_object_add(jseg, "list", jseg_list);
631 0 : json_object_array_add(jaspath_segments, jseg);
632 : }
633 :
634 6 : if (seg->type != AS_SEQUENCE)
635 0 : len += snprintf(
636 0 : str_buf + len, str_size - len, "%c",
637 0 : aspath_delimiter_char(seg->type, AS_SEG_END));
638 6 : if (seg->next)
639 0 : len += snprintf(str_buf + len, str_size - len, " ");
640 :
641 6 : seg = seg->next;
642 : }
643 :
644 6 : assert(len < str_size);
645 :
646 6 : str_buf[len] = '\0';
647 6 : as->str = str_buf;
648 6 : as->str_len = len;
649 :
650 6 : if (make_json) {
651 0 : json_object_string_add(as->json, "string", str_buf);
652 0 : json_object_object_add(as->json, "segments", jaspath_segments);
653 0 : json_object_int_add(as->json, "length", aspath_count_hops(as));
654 : }
655 :
656 : return;
657 : }
658 :
659 9 : void aspath_str_update(struct aspath *as, bool make_json)
660 : {
661 9 : XFREE(MTYPE_AS_STR, as->str);
662 :
663 9 : if (as->json) {
664 0 : json_object_free(as->json);
665 0 : as->json = NULL;
666 : }
667 :
668 9 : aspath_make_str_count(as, make_json);
669 9 : }
670 :
671 : /* Intern allocated AS path. */
672 0 : struct aspath *aspath_intern(struct aspath *aspath)
673 : {
674 0 : struct aspath *find;
675 :
676 : /* Assert this AS path structure is not interned and has the string
677 : representation built. */
678 0 : assert(aspath->refcnt == 0);
679 0 : assert(aspath->str);
680 :
681 : /* Check AS path hash. */
682 0 : find = hash_get(ashash, aspath, hash_alloc_intern);
683 0 : if (find != aspath)
684 0 : aspath_free(aspath);
685 :
686 0 : find->refcnt++;
687 :
688 0 : return find;
689 : }
690 :
691 : /* Duplicate aspath structure. Created same aspath structure but
692 : reference count and AS path string is cleared. */
693 3 : struct aspath *aspath_dup(struct aspath *aspath)
694 : {
695 3 : unsigned short buflen = aspath->str_len + 1;
696 3 : struct aspath *new;
697 :
698 3 : new = XCALLOC(MTYPE_AS_PATH, sizeof(struct aspath));
699 3 : new->json = NULL;
700 :
701 3 : if (aspath->segments)
702 1 : new->segments = assegment_dup_all(aspath->segments);
703 :
704 3 : if (!aspath->str)
705 : return new;
706 :
707 3 : new->str = XMALLOC(MTYPE_AS_STR, buflen);
708 3 : new->str_len = aspath->str_len;
709 :
710 : /* copy the string data */
711 3 : if (aspath->str_len > 0)
712 1 : memcpy(new->str, aspath->str, buflen);
713 : else
714 2 : new->str[0] = '\0';
715 :
716 : return new;
717 : }
718 :
719 3 : static void *aspath_hash_alloc(void *arg)
720 : {
721 3 : const struct aspath *aspath = arg;
722 3 : struct aspath *new;
723 :
724 : /* Malformed AS path value. */
725 3 : assert(aspath->str);
726 :
727 : /* New aspath structure is needed. */
728 3 : new = XMALLOC(MTYPE_AS_PATH, sizeof(struct aspath));
729 :
730 : /* Reuse segments and string representation */
731 3 : new->refcnt = 0;
732 3 : new->segments = aspath->segments;
733 3 : new->str = aspath->str;
734 3 : new->str_len = aspath->str_len;
735 3 : new->json = aspath->json;
736 :
737 3 : return new;
738 : }
739 :
740 : /* parse as-segment byte stream in struct assegment */
741 6 : static int assegments_parse(struct stream *s, size_t length,
742 : struct assegment **result, int use32bit)
743 : {
744 6 : struct assegment_header segh;
745 6 : struct assegment *seg, *prev = NULL, *head = NULL;
746 6 : size_t bytes = 0;
747 :
748 : /* empty aspath (ie iBGP or somesuch) */
749 6 : if (length == 0)
750 : return 0;
751 :
752 3 : if (BGP_DEBUG(as4, AS4_SEGMENT))
753 0 : zlog_debug(
754 : "[AS4SEG] Parse aspath segment: got total byte length %lu",
755 : (unsigned long)length);
756 : /* basic checks */
757 3 : if ((STREAM_READABLE(s) < length)
758 3 : || (STREAM_READABLE(s) < AS_HEADER_SIZE)
759 3 : || (length % AS16_VALUE_SIZE))
760 : return -1;
761 :
762 6 : while (bytes < length) {
763 3 : int i;
764 3 : size_t seg_size;
765 :
766 3 : if ((length - bytes) <= AS_HEADER_SIZE) {
767 0 : if (head)
768 0 : assegment_free_all(head);
769 0 : return -1;
770 : }
771 :
772 : /* softly softly, get the header first on its own */
773 3 : segh.type = stream_getc(s);
774 3 : segh.length = stream_getc(s);
775 :
776 3 : seg_size = ASSEGMENT_SIZE(segh.length, use32bit);
777 :
778 3 : if (BGP_DEBUG(as4, AS4_SEGMENT))
779 0 : zlog_debug(
780 : "[AS4SEG] Parse aspath segment: got type %d, length %d",
781 : segh.type, segh.length);
782 :
783 : /* check it.. */
784 3 : if (((bytes + seg_size) > length)
785 : /* 1771bis 4.3b: seg length contains one or more */
786 : || (segh.length == 0)
787 : /* Paranoia in case someone changes type of segment length.
788 : * Shift both values by 0x10 to make the comparison operate
789 : * on more, than 8 bits (otherwise it's a warning, bug
790 : * #564).
791 : */
792 3 : || ((sizeof(segh.length) > 1)
793 : && (0x10 + segh.length > 0x10 + AS_SEGMENT_MAX))) {
794 0 : if (head)
795 0 : assegment_free_all(head);
796 0 : return -1;
797 : }
798 :
799 3 : switch (segh.type) {
800 : case AS_SEQUENCE:
801 : case AS_SET:
802 : case AS_CONFED_SEQUENCE:
803 : case AS_CONFED_SET:
804 3 : break;
805 0 : default:
806 0 : if (head)
807 6 : assegment_free_all(head);
808 : return -1;
809 : }
810 :
811 : /* now its safe to trust lengths */
812 3 : seg = assegment_new(segh.type, segh.length);
813 :
814 3 : if (head)
815 0 : prev->next = seg;
816 : else /* it's the first segment */
817 : head = seg;
818 :
819 7 : for (i = 0; i < segh.length; i++)
820 4 : seg->as[i] =
821 4 : (use32bit) ? stream_getl(s) : stream_getw(s);
822 :
823 3 : bytes += seg_size;
824 :
825 3 : if (BGP_DEBUG(as4, AS4_SEGMENT))
826 0 : zlog_debug(
827 : "[AS4SEG] Parse aspath segment: Bytes now: %lu",
828 : (unsigned long)bytes);
829 :
830 : prev = seg;
831 : }
832 :
833 3 : *result = assegment_normalise(head);
834 3 : return 0;
835 : }
836 :
837 : /* AS path parse function. pnt is a pointer to byte stream and length
838 : is length of byte stream. If there is same AS path in the the AS
839 : path hash then return it else make new AS path structure.
840 :
841 : On error NULL is returned.
842 : */
843 6 : struct aspath *aspath_parse(struct stream *s, size_t length, int use32bit)
844 : {
845 6 : struct aspath as;
846 6 : struct aspath *find;
847 :
848 : /* If length is odd it's malformed AS path. */
849 : /* Nit-picking: if (use32bit == 0) it is malformed if odd,
850 : * otherwise its malformed when length is larger than 2 and (length-2)
851 : * is not dividable by 4.
852 : * But... this time we're lazy
853 : */
854 6 : if (length % AS16_VALUE_SIZE)
855 : return NULL;
856 :
857 6 : memset(&as, 0, sizeof(as));
858 6 : if (assegments_parse(s, length, &as.segments, use32bit) < 0)
859 : return NULL;
860 :
861 : /* If already same aspath exist then return it. */
862 6 : find = hash_get(ashash, &as, aspath_hash_alloc);
863 :
864 : /* if the aspath was already hashed free temporary memory. */
865 6 : if (find->refcnt) {
866 3 : assegment_free_all(as.segments);
867 : /* aspath_key_make() always updates the string */
868 3 : XFREE(MTYPE_AS_STR, as.str);
869 3 : if (as.json) {
870 0 : json_object_free(as.json);
871 0 : as.json = NULL;
872 : }
873 : }
874 :
875 6 : find->refcnt++;
876 :
877 6 : return find;
878 : }
879 :
880 3 : static void assegment_data_put(struct stream *s, as_t *as, int num,
881 : int use32bit)
882 : {
883 3 : int i;
884 3 : assert(num <= AS_SEGMENT_MAX);
885 :
886 7 : for (i = 0; i < num; i++)
887 4 : if (use32bit)
888 0 : stream_putl(s, as[i]);
889 : else {
890 4 : if (as[i] <= BGP_AS_MAX)
891 4 : stream_putw(s, as[i]);
892 : else
893 0 : stream_putw(s, BGP_AS_TRANS);
894 : }
895 3 : }
896 :
897 3 : static size_t assegment_header_put(struct stream *s, uint8_t type, int length)
898 : {
899 3 : size_t lenp;
900 3 : assert(length <= AS_SEGMENT_MAX);
901 3 : stream_putc(s, type);
902 3 : lenp = stream_get_endp(s);
903 3 : stream_putc(s, length);
904 3 : return lenp;
905 : }
906 :
907 : /* write aspath data to stream */
908 3 : size_t aspath_put(struct stream *s, struct aspath *as, int use32bit)
909 : {
910 3 : struct assegment *seg = as->segments;
911 3 : size_t bytes = 0;
912 :
913 3 : if (!seg || seg->length == 0)
914 : return 0;
915 :
916 : /*
917 : * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
918 : * At the moment, we would write out a partial aspath, and our
919 : * peer
920 : * will complain and drop the session :-/
921 : *
922 : * The general assumption here is that many things tested will
923 : * never happen. And, in real live, up to now, they have not.
924 : */
925 9 : while (seg && (ASSEGMENT_LEN(seg, use32bit) <= STREAM_WRITEABLE(s))) {
926 3 : struct assegment *next = seg->next;
927 3 : int written = 0;
928 3 : int asns_packed = 0;
929 3 : size_t lenp;
930 :
931 : /* Overlength segments have to be split up */
932 3 : while ((seg->length - written) > AS_SEGMENT_MAX) {
933 0 : assegment_header_put(s, seg->type, AS_SEGMENT_MAX);
934 0 : assegment_data_put(s, (seg->as + written),
935 : AS_SEGMENT_MAX, use32bit);
936 0 : written += AS_SEGMENT_MAX;
937 0 : bytes += ASSEGMENT_SIZE(AS_SEGMENT_MAX, use32bit);
938 : }
939 :
940 : /* write the final segment, probably is also the first
941 : */
942 3 : lenp = assegment_header_put(s, seg->type,
943 : seg->length - written);
944 3 : assegment_data_put(s, (seg->as + written),
945 3 : seg->length - written, use32bit);
946 :
947 : /* Sequence-type segments can be 'packed' together
948 : * Case of a segment which was overlength and split up
949 : * will be missed here, but that doesn't matter.
950 : */
951 3 : while (next && ASSEGMENTS_PACKABLE(seg, next)) {
952 : /* NB: We should never normally get here given
953 : * we
954 : * normalise aspath data when parse them.
955 : * However, better
956 : * safe than sorry. We potentially could call
957 : * assegment_normalise here instead, but it's
958 : * cheaper and
959 : * easier to do it on the fly here rather than
960 : * go through
961 : * the segment list twice every time we write
962 : * out
963 : * aspath's.
964 : */
965 :
966 : /* Next segment's data can fit in this one */
967 0 : assegment_data_put(s, next->as, next->length, use32bit);
968 :
969 : /* update the length of the segment header */
970 0 : stream_putc_at(s, lenp,
971 0 : seg->length - written + next->length);
972 0 : asns_packed += next->length;
973 :
974 0 : next = next->next;
975 : }
976 :
977 3 : bytes += ASSEGMENT_SIZE(seg->length - written + asns_packed,
978 : use32bit);
979 3 : seg = next;
980 : }
981 : return bytes;
982 : }
983 :
984 : /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
985 : * We have no way to manage the storage, so we use a static stream
986 : * wrapper around aspath_put.
987 : */
988 0 : uint8_t *aspath_snmp_pathseg(struct aspath *as, size_t *varlen)
989 : {
990 : #define SNMP_PATHSEG_MAX 1024
991 :
992 0 : if (!snmp_stream)
993 0 : snmp_stream = stream_new(SNMP_PATHSEG_MAX);
994 : else
995 0 : stream_reset(snmp_stream);
996 :
997 0 : if (!as) {
998 0 : *varlen = 0;
999 0 : return NULL;
1000 : }
1001 0 : aspath_put(snmp_stream, as, 0); /* use 16 bit for now here */
1002 :
1003 0 : *varlen = stream_get_endp(snmp_stream);
1004 0 : return stream_pnt(snmp_stream);
1005 : }
1006 :
1007 0 : static struct assegment *aspath_aggregate_as_set_add(struct aspath *aspath,
1008 : struct assegment *asset,
1009 : as_t as)
1010 : {
1011 0 : int i;
1012 :
1013 : /* If this is first AS set member, create new as-set segment. */
1014 0 : if (asset == NULL) {
1015 0 : asset = assegment_new(AS_SET, 1);
1016 0 : if (!aspath->segments)
1017 0 : aspath->segments = asset;
1018 : else {
1019 : struct assegment *seg = aspath->segments;
1020 0 : while (seg->next)
1021 : seg = seg->next;
1022 0 : seg->next = asset;
1023 : }
1024 0 : asset->type = AS_SET;
1025 0 : asset->length = 1;
1026 0 : asset->as[0] = as;
1027 : } else {
1028 : /* Check this AS value already exists or not. */
1029 0 : for (i = 0; i < asset->length; i++)
1030 0 : if (asset->as[i] == as)
1031 : return asset;
1032 :
1033 0 : asset->length++;
1034 0 : asset->as = XREALLOC(MTYPE_AS_SEG_DATA, asset->as,
1035 : asset->length * AS_VALUE_SIZE);
1036 0 : asset->as[asset->length - 1] = as;
1037 : }
1038 :
1039 :
1040 : return asset;
1041 : }
1042 :
1043 : /* Modify as1 using as2 for aggregation. */
1044 0 : struct aspath *aspath_aggregate(struct aspath *as1, struct aspath *as2)
1045 : {
1046 0 : int i;
1047 0 : int minlen = 0;
1048 0 : int match = 0;
1049 0 : int from;
1050 0 : struct assegment *seg1 = as1->segments;
1051 0 : struct assegment *seg2 = as2->segments;
1052 0 : struct aspath *aspath = NULL;
1053 0 : struct assegment *asset = NULL;
1054 0 : struct assegment *prevseg = NULL;
1055 :
1056 : /* First of all check common leading sequence. */
1057 0 : while (seg1 && seg2) {
1058 : /* Check segment type. */
1059 0 : if (seg1->type != seg2->type)
1060 : break;
1061 :
1062 : /* Minimum segment length. */
1063 0 : minlen = MIN(seg1->length, seg2->length);
1064 :
1065 0 : for (match = 0; match < minlen; match++)
1066 0 : if (seg1->as[match] != seg2->as[match])
1067 : break;
1068 :
1069 0 : if (match) {
1070 0 : struct assegment *seg = assegment_new(seg1->type, 0);
1071 :
1072 0 : seg = assegment_append_asns(seg, seg1->as, match);
1073 :
1074 0 : if (!aspath) {
1075 0 : aspath = aspath_new();
1076 0 : aspath->segments = seg;
1077 : } else
1078 0 : prevseg->next = seg;
1079 :
1080 : prevseg = seg;
1081 : }
1082 :
1083 0 : if (match != minlen || match != seg1->length
1084 0 : || seg1->length != seg2->length)
1085 : break;
1086 : /* We are moving on to the next segment to reset match */
1087 : else
1088 0 : match = 0;
1089 :
1090 0 : seg1 = seg1->next;
1091 0 : seg2 = seg2->next;
1092 : }
1093 :
1094 0 : if (!aspath)
1095 0 : aspath = aspath_new();
1096 :
1097 : /* Make as-set using rest of all information. */
1098 0 : from = match;
1099 0 : while (seg1) {
1100 0 : for (i = from; i < seg1->length; i++)
1101 0 : asset = aspath_aggregate_as_set_add(aspath, asset,
1102 0 : seg1->as[i]);
1103 :
1104 0 : from = 0;
1105 0 : seg1 = seg1->next;
1106 : }
1107 :
1108 : from = match;
1109 0 : while (seg2) {
1110 0 : for (i = from; i < seg2->length; i++)
1111 0 : asset = aspath_aggregate_as_set_add(aspath, asset,
1112 0 : seg2->as[i]);
1113 :
1114 0 : from = 0;
1115 0 : seg2 = seg2->next;
1116 : }
1117 :
1118 0 : assegment_normalise(aspath->segments);
1119 0 : aspath_str_update(aspath, false);
1120 0 : return aspath;
1121 : }
1122 :
1123 : /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1124 : attribute, check the leftmost AS number in the AS_PATH attribute is
1125 : or not the peer's AS number. */
1126 0 : bool aspath_firstas_check(struct aspath *aspath, as_t asno)
1127 : {
1128 0 : if ((aspath == NULL) || (aspath->segments == NULL))
1129 : return false;
1130 :
1131 0 : if (aspath->segments && (aspath->segments->type == AS_SEQUENCE)
1132 0 : && (aspath->segments->as[0] == asno))
1133 0 : return true;
1134 :
1135 : return false;
1136 : }
1137 :
1138 0 : unsigned int aspath_get_first_as(struct aspath *aspath)
1139 : {
1140 0 : if (aspath == NULL || aspath->segments == NULL)
1141 : return 0;
1142 :
1143 0 : return aspath->segments->as[0];
1144 : }
1145 :
1146 0 : unsigned int aspath_get_last_as(struct aspath *aspath)
1147 : {
1148 0 : int i;
1149 0 : unsigned int last_as = 0;
1150 0 : const struct assegment *seg;
1151 :
1152 0 : if (aspath == NULL || aspath->segments == NULL)
1153 : return last_as;
1154 :
1155 : seg = aspath->segments;
1156 :
1157 0 : while (seg) {
1158 0 : if (seg->type == AS_SEQUENCE || seg->type == AS_CONFED_SEQUENCE)
1159 0 : for (i = 0; i < seg->length; i++)
1160 0 : last_as = seg->as[i];
1161 0 : seg = seg->next;
1162 : }
1163 :
1164 : return last_as;
1165 : }
1166 :
1167 : /* AS path loop check. If aspath contains asno then return >= 1. */
1168 4 : int aspath_loop_check(struct aspath *aspath, as_t asno)
1169 : {
1170 4 : struct assegment *seg;
1171 4 : int count = 0;
1172 :
1173 4 : if ((aspath == NULL) || (aspath->segments == NULL))
1174 : return 0;
1175 :
1176 : seg = aspath->segments;
1177 :
1178 8 : while (seg) {
1179 : int i;
1180 :
1181 10 : for (i = 0; i < seg->length; i++)
1182 6 : if (seg->as[i] == asno)
1183 2 : count++;
1184 :
1185 4 : seg = seg->next;
1186 : }
1187 : return count;
1188 : }
1189 :
1190 : /* AS path loop check. If aspath contains asno
1191 : * that is a confed id then return >= 1.
1192 : */
1193 0 : int aspath_loop_check_confed(struct aspath *aspath, as_t asno)
1194 : {
1195 0 : struct assegment *seg;
1196 0 : int count = 0;
1197 :
1198 0 : if (aspath == NULL || aspath->segments == NULL)
1199 : return 0;
1200 :
1201 : seg = aspath->segments;
1202 :
1203 0 : while (seg) {
1204 : unsigned int i;
1205 :
1206 0 : for (i = 0; i < seg->length; i++)
1207 0 : if (seg->type != AS_CONFED_SEQUENCE &&
1208 0 : seg->type != AS_CONFED_SET && seg->as[i] == asno)
1209 0 : count++;
1210 :
1211 0 : seg = seg->next;
1212 : }
1213 : return count;
1214 : }
1215 :
1216 :
1217 : /* When all of AS path is private AS return 1. */
1218 0 : bool aspath_private_as_check(struct aspath *aspath)
1219 : {
1220 0 : struct assegment *seg;
1221 :
1222 0 : if (!(aspath && aspath->segments))
1223 : return false;
1224 :
1225 : seg = aspath->segments;
1226 :
1227 0 : while (seg) {
1228 : int i;
1229 :
1230 0 : for (i = 0; i < seg->length; i++) {
1231 0 : if (!BGP_AS_IS_PRIVATE(seg->as[i]))
1232 : return false;
1233 : }
1234 0 : seg = seg->next;
1235 : }
1236 : return true;
1237 : }
1238 :
1239 : /* Replace all instances of the target ASN with our own ASN */
1240 0 : struct aspath *aspath_replace_specific_asn(struct aspath *aspath,
1241 : as_t target_asn, as_t our_asn)
1242 : {
1243 0 : struct aspath *new;
1244 0 : struct assegment *seg;
1245 :
1246 0 : new = aspath_dup(aspath);
1247 0 : seg = new->segments;
1248 :
1249 0 : while (seg) {
1250 : int i;
1251 :
1252 0 : for (i = 0; i < seg->length; i++) {
1253 0 : if (seg->as[i] == target_asn)
1254 0 : seg->as[i] = our_asn;
1255 : }
1256 0 : seg = seg->next;
1257 : }
1258 :
1259 0 : aspath_str_update(new, false);
1260 0 : return new;
1261 : }
1262 :
1263 : /* Replace all ASNs with our own ASN */
1264 0 : struct aspath *aspath_replace_all_asn(struct aspath *aspath, as_t our_asn)
1265 : {
1266 0 : struct aspath *new;
1267 0 : struct assegment *seg;
1268 :
1269 0 : new = aspath_dup(aspath);
1270 0 : seg = new->segments;
1271 :
1272 0 : while (seg) {
1273 : int i;
1274 :
1275 0 : for (i = 0; i < seg->length; i++)
1276 0 : seg->as[i] = our_asn;
1277 :
1278 0 : seg = seg->next;
1279 : }
1280 :
1281 0 : aspath_str_update(new, false);
1282 0 : return new;
1283 : }
1284 :
1285 : /* Replace all private ASNs with our own ASN */
1286 0 : struct aspath *aspath_replace_private_asns(struct aspath *aspath, as_t asn,
1287 : as_t peer_asn)
1288 : {
1289 0 : struct aspath *new;
1290 0 : struct assegment *seg;
1291 :
1292 0 : new = aspath_dup(aspath);
1293 0 : seg = new->segments;
1294 :
1295 0 : while (seg) {
1296 : int i;
1297 :
1298 0 : for (i = 0; i < seg->length; i++) {
1299 : /* Don't replace if public ASN or peer's ASN */
1300 0 : if (BGP_AS_IS_PRIVATE(seg->as[i])
1301 0 : && (seg->as[i] != peer_asn))
1302 0 : seg->as[i] = asn;
1303 : }
1304 0 : seg = seg->next;
1305 : }
1306 :
1307 0 : aspath_str_update(new, false);
1308 0 : return new;
1309 : }
1310 :
1311 : /* Remove all private ASNs */
1312 0 : struct aspath *aspath_remove_private_asns(struct aspath *aspath, as_t peer_asn)
1313 : {
1314 0 : struct aspath *new;
1315 0 : struct assegment *seg;
1316 0 : struct assegment *new_seg;
1317 0 : struct assegment *last_new_seg;
1318 0 : int i;
1319 0 : int j;
1320 0 : int public = 0;
1321 0 : int peer = 0;
1322 :
1323 0 : new = XCALLOC(MTYPE_AS_PATH, sizeof(struct aspath));
1324 :
1325 0 : new->json = NULL;
1326 0 : new_seg = NULL;
1327 0 : last_new_seg = NULL;
1328 0 : seg = aspath->segments;
1329 0 : while (seg) {
1330 : public = 0;
1331 : peer = 0;
1332 0 : for (i = 0; i < seg->length; i++) {
1333 : // ASN is public
1334 0 : if (!BGP_AS_IS_PRIVATE(seg->as[i]))
1335 0 : public++;
1336 : /* ASN matches peer's.
1337 : * Don't double-count if peer_asn is public.
1338 : */
1339 0 : else if (seg->as[i] == peer_asn)
1340 0 : peer++;
1341 : }
1342 :
1343 : // The entire segment is public so copy it
1344 0 : if (public == seg->length)
1345 0 : new_seg = assegment_dup(seg);
1346 :
1347 : // The segment is a mix of public and private ASNs. Copy as many
1348 : // spots as
1349 : // there are public ASNs then come back and fill in only the
1350 : // public ASNs.
1351 : else {
1352 : /* length needs to account for all retained ASNs
1353 : * (public or peer_asn), not just public
1354 : */
1355 0 : new_seg = assegment_new(seg->type, (public + peer));
1356 0 : j = 0;
1357 0 : for (i = 0; i < seg->length; i++) {
1358 : // keep ASN if public or matches peer's ASN
1359 0 : if (!BGP_AS_IS_PRIVATE(seg->as[i])
1360 0 : || (seg->as[i] == peer_asn)) {
1361 0 : new_seg->as[j] = seg->as[i];
1362 0 : j++;
1363 : }
1364 : }
1365 : }
1366 :
1367 : // This is the first segment so set the aspath segments pointer
1368 : // to this one
1369 0 : if (!last_new_seg)
1370 0 : new->segments = new_seg;
1371 : else
1372 0 : last_new_seg->next = new_seg;
1373 :
1374 0 : last_new_seg = new_seg;
1375 0 : seg = seg->next;
1376 : }
1377 :
1378 0 : aspath_str_update(new, false);
1379 0 : return new;
1380 : }
1381 :
1382 : /* AS path confed check. If aspath contains confed set or sequence then return
1383 : * 1. */
1384 3 : bool aspath_confed_check(struct aspath *aspath)
1385 : {
1386 3 : struct assegment *seg;
1387 :
1388 3 : if (!(aspath && aspath->segments))
1389 : return false;
1390 :
1391 : seg = aspath->segments;
1392 :
1393 6 : while (seg) {
1394 3 : if (seg->type == AS_CONFED_SET
1395 3 : || seg->type == AS_CONFED_SEQUENCE)
1396 : return true;
1397 3 : seg = seg->next;
1398 : }
1399 : return false;
1400 : }
1401 :
1402 : /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1403 : AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1404 0 : bool aspath_left_confed_check(struct aspath *aspath)
1405 : {
1406 :
1407 0 : if (!(aspath && aspath->segments))
1408 : return false;
1409 :
1410 0 : if ((aspath->segments->type == AS_CONFED_SEQUENCE)
1411 0 : || (aspath->segments->type == AS_CONFED_SET))
1412 0 : return true;
1413 :
1414 : return false;
1415 : }
1416 :
1417 : /* Merge as1 to as2. as2 should be uninterned aspath. */
1418 0 : static struct aspath *aspath_merge(struct aspath *as1, struct aspath *as2)
1419 : {
1420 0 : struct assegment *last, *new;
1421 :
1422 0 : if (!as1 || !as2)
1423 : return NULL;
1424 :
1425 0 : last = new = assegment_dup_all(as1->segments);
1426 :
1427 : /* find the last valid segment */
1428 0 : while (last && last->next)
1429 : last = last->next;
1430 :
1431 0 : if (last)
1432 0 : last->next = as2->segments;
1433 0 : as2->segments = new;
1434 0 : aspath_str_update(as2, false);
1435 0 : return as2;
1436 : }
1437 :
1438 : /* Prepend as1 to as2. as2 should be uninterned aspath. */
1439 0 : struct aspath *aspath_prepend(struct aspath *as1, struct aspath *as2)
1440 : {
1441 0 : struct assegment *as1segtail;
1442 0 : struct assegment *as2segtail;
1443 0 : struct assegment *as2seghead;
1444 :
1445 0 : if (!as1 || !as2)
1446 : return NULL;
1447 :
1448 : /* If as2 is empty, only need to dupe as1's chain onto as2 */
1449 0 : if (as2->segments == NULL) {
1450 0 : as2->segments = assegment_dup_all(as1->segments);
1451 0 : aspath_str_update(as2, false);
1452 0 : return as2;
1453 : }
1454 :
1455 : /* If as1 is empty AS, no prepending to do. */
1456 0 : if (as1->segments == NULL)
1457 : return as2;
1458 :
1459 : /* find the tail as1's segment chain. */
1460 : as1segtail = as1->segments;
1461 0 : while (as1segtail && as1segtail->next)
1462 : as1segtail = as1segtail->next;
1463 :
1464 : /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1465 0 : if (as1segtail->type == AS_SEQUENCE
1466 0 : && as2->segments->type == AS_CONFED_SEQUENCE)
1467 0 : as2 = aspath_delete_confed_seq(as2);
1468 :
1469 0 : if (!as2->segments) {
1470 0 : as2->segments = assegment_dup_all(as1->segments);
1471 0 : aspath_str_update(as2, false);
1472 0 : return as2;
1473 : }
1474 :
1475 : /* Compare last segment type of as1 and first segment type of as2. */
1476 0 : if (as1segtail->type != as2->segments->type)
1477 0 : return aspath_merge(as1, as2);
1478 :
1479 0 : if (as1segtail->type == AS_SEQUENCE) {
1480 : /* We have two chains of segments, as1->segments and seg2,
1481 : * and we have to attach them together, merging the attaching
1482 : * segments together into one.
1483 : *
1484 : * 1. dupe as1->segments onto head of as2
1485 : * 2. merge seg2's asns onto last segment of this new chain
1486 : * 3. attach chain after seg2
1487 : */
1488 :
1489 : /* save as2 head */
1490 0 : as2seghead = as2->segments;
1491 :
1492 : /* dupe as1 onto as2's head */
1493 0 : as2segtail = as2->segments = assegment_dup_all(as1->segments);
1494 :
1495 : /* refind the tail of as2 */
1496 0 : while (as2segtail && as2segtail->next)
1497 : as2segtail = as2segtail->next;
1498 :
1499 : /* merge the old head, seg2, into tail, seg1 */
1500 0 : assegment_append_asns(as2segtail, as2seghead->as,
1501 0 : as2seghead->length);
1502 :
1503 : /*
1504 : * bypass the merged seg2, and attach any chain after it
1505 : * to chain descending from as2's head
1506 : */
1507 0 : if (as2segtail)
1508 0 : as2segtail->next = as2seghead->next;
1509 :
1510 : /* as2->segments is now referenceless and useless */
1511 0 : assegment_free(as2seghead);
1512 :
1513 : /* we've now prepended as1's segment chain to as2, merging
1514 : * the inbetween AS_SEQUENCE of seg2 in the process
1515 : */
1516 0 : aspath_str_update(as2, false);
1517 0 : return as2;
1518 : } else {
1519 : /* AS_SET merge code is needed at here. */
1520 0 : return aspath_merge(as1, as2);
1521 : }
1522 : /* XXX: Ermmm, what if as1 has multiple segments?? */
1523 :
1524 : /* Not reached */
1525 : }
1526 :
1527 : /* Iterate over AS_PATH segments and wipe all occurrences of the
1528 : * listed AS numbers. Hence some segments may lose some or even
1529 : * all data on the way, the operation is implemented as a smarter
1530 : * version of aspath_dup(), which allocates memory to hold the new
1531 : * data, not the original. The new AS path is returned.
1532 : */
1533 0 : struct aspath *aspath_filter_exclude(struct aspath *source,
1534 : struct aspath *exclude_list)
1535 : {
1536 0 : struct assegment *srcseg, *exclseg, *lastseg;
1537 0 : struct aspath *newpath;
1538 :
1539 0 : newpath = aspath_new();
1540 0 : lastseg = NULL;
1541 :
1542 0 : for (srcseg = source->segments; srcseg; srcseg = srcseg->next) {
1543 0 : unsigned i, y, newlen = 0, done = 0, skip_as;
1544 : struct assegment *newseg;
1545 :
1546 : /* Find out, how much ASns are we going to pick from this
1547 : * segment.
1548 : * We can't perform filtering right inline, because the size of
1549 : * the new segment isn't known at the moment yet.
1550 : */
1551 0 : for (i = 0; i < srcseg->length; i++) {
1552 0 : skip_as = 0;
1553 0 : for (exclseg = exclude_list->segments;
1554 0 : exclseg && !skip_as; exclseg = exclseg->next)
1555 0 : for (y = 0; y < exclseg->length; y++)
1556 0 : if (srcseg->as[i] == exclseg->as[y]) {
1557 : skip_as = 1;
1558 : // There's no sense in testing
1559 : // the rest of exclusion list,
1560 : // bail out.
1561 : break;
1562 : }
1563 0 : if (!skip_as)
1564 0 : newlen++;
1565 : }
1566 : /* newlen is now the number of ASns to copy */
1567 0 : if (!newlen)
1568 0 : continue;
1569 :
1570 : /* Actual copying. Allocate memory and iterate once more,
1571 : * performing filtering. */
1572 0 : newseg = assegment_new(srcseg->type, newlen);
1573 0 : for (i = 0; i < srcseg->length; i++) {
1574 0 : skip_as = 0;
1575 0 : for (exclseg = exclude_list->segments;
1576 0 : exclseg && !skip_as; exclseg = exclseg->next)
1577 0 : for (y = 0; y < exclseg->length; y++)
1578 0 : if (srcseg->as[i] == exclseg->as[y]) {
1579 : skip_as = 1;
1580 : break;
1581 : }
1582 0 : if (skip_as)
1583 0 : continue;
1584 0 : newseg->as[done++] = srcseg->as[i];
1585 : }
1586 : /* At his point newlen must be equal to done, and both must be
1587 : * positive. Append
1588 : * the filtered segment to the gross result. */
1589 0 : if (!lastseg)
1590 0 : newpath->segments = newseg;
1591 : else
1592 0 : lastseg->next = newseg;
1593 : lastseg = newseg;
1594 : }
1595 0 : aspath_str_update(newpath, false);
1596 : /* We are happy returning even an empty AS_PATH, because the
1597 : * administrator
1598 : * might expect this very behaviour. There's a mean to avoid this, if
1599 : * necessary,
1600 : * by having a match rule against certain AS_PATH regexps in the
1601 : * route-map index.
1602 : */
1603 0 : aspath_free(source);
1604 0 : return newpath;
1605 : }
1606 :
1607 : /* Add specified AS to the leftmost of aspath. */
1608 3 : static struct aspath *aspath_add_asns(struct aspath *aspath, as_t asno,
1609 : uint8_t type, unsigned num)
1610 : {
1611 3 : struct assegment *assegment = aspath->segments;
1612 3 : unsigned i;
1613 :
1614 3 : if (assegment && assegment->type == type) {
1615 : /* extend existing segment */
1616 1 : aspath->segments =
1617 1 : assegment_prepend_asns(aspath->segments, asno, num);
1618 : } else {
1619 : /* prepend with new segment */
1620 2 : struct assegment *newsegment = assegment_new(type, num);
1621 6 : for (i = 0; i < num; i++)
1622 2 : newsegment->as[i] = asno;
1623 :
1624 : /* insert potentially replacing empty segment */
1625 2 : if (assegment && assegment->length == 0) {
1626 0 : newsegment->next = assegment->next;
1627 0 : assegment_free(assegment);
1628 : } else
1629 2 : newsegment->next = assegment;
1630 2 : aspath->segments = newsegment;
1631 : }
1632 :
1633 3 : aspath_str_update(aspath, false);
1634 3 : return aspath;
1635 : }
1636 :
1637 : /* Add specified AS to the leftmost of aspath num times. */
1638 0 : struct aspath *aspath_add_seq_n(struct aspath *aspath, as_t asno, unsigned num)
1639 : {
1640 0 : return aspath_add_asns(aspath, asno, AS_SEQUENCE, num);
1641 : }
1642 :
1643 : /* Add specified AS to the leftmost of aspath. */
1644 3 : struct aspath *aspath_add_seq(struct aspath *aspath, as_t asno)
1645 : {
1646 3 : return aspath_add_asns(aspath, asno, AS_SEQUENCE, 1);
1647 : }
1648 :
1649 : /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1650 : as2's leftmost AS is same return 1. */
1651 0 : bool aspath_cmp_left(const struct aspath *aspath1, const struct aspath *aspath2)
1652 : {
1653 0 : const struct assegment *seg1;
1654 0 : const struct assegment *seg2;
1655 :
1656 0 : if (!(aspath1 && aspath2))
1657 : return false;
1658 :
1659 0 : seg1 = aspath1->segments;
1660 0 : seg2 = aspath2->segments;
1661 :
1662 : /* If both paths are originated in this AS then we do want to compare
1663 : * MED */
1664 0 : if (!seg1 && !seg2)
1665 : return true;
1666 :
1667 : /* find first non-confed segments for each */
1668 0 : while (seg1 && ((seg1->type == AS_CONFED_SEQUENCE)
1669 0 : || (seg1->type == AS_CONFED_SET)))
1670 0 : seg1 = seg1->next;
1671 :
1672 0 : while (seg2 && ((seg2->type == AS_CONFED_SEQUENCE)
1673 0 : || (seg2->type == AS_CONFED_SET)))
1674 0 : seg2 = seg2->next;
1675 :
1676 : /* Check as1's */
1677 0 : if (!(seg1 && seg2 && (seg1->type == AS_SEQUENCE)
1678 0 : && (seg2->type == AS_SEQUENCE)))
1679 : return false;
1680 :
1681 0 : if (seg1->as[0] == seg2->as[0])
1682 0 : return true;
1683 :
1684 : return false;
1685 : }
1686 :
1687 : /* Truncate an aspath after a number of hops, and put the hops remaining
1688 : * at the front of another aspath. Needed for AS4 compat.
1689 : *
1690 : * Returned aspath is a /new/ aspath, which should either by free'd or
1691 : * interned by the caller, as desired.
1692 : */
1693 0 : struct aspath *aspath_reconcile_as4(struct aspath *aspath,
1694 : struct aspath *as4path)
1695 : {
1696 0 : struct assegment *seg, *newseg, *prevseg = NULL;
1697 0 : struct aspath *newpath = NULL, *mergedpath;
1698 0 : int hops, cpasns = 0;
1699 :
1700 0 : if (!aspath || !as4path)
1701 : return NULL;
1702 :
1703 0 : seg = aspath->segments;
1704 :
1705 : /* CONFEDs should get reconciled too.. */
1706 0 : hops = (aspath_count_hops(aspath) + aspath_count_confeds(aspath))
1707 0 : - aspath_count_hops(as4path);
1708 :
1709 0 : if (hops < 0) {
1710 0 : if (BGP_DEBUG(as4, AS4))
1711 0 : flog_warn(
1712 : EC_BGP_ASPATH_FEWER_HOPS,
1713 : "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1714 : /* Something's gone wrong. The RFC says we should now ignore
1715 : * AS4_PATH,
1716 : * which is daft behaviour - it contains vital loop-detection
1717 : * information which must have been removed from AS_PATH.
1718 : */
1719 0 : hops = aspath_count_hops(aspath);
1720 : }
1721 :
1722 0 : if (!hops) {
1723 0 : newpath = aspath_dup(as4path);
1724 0 : aspath_str_update(newpath, false);
1725 0 : return newpath;
1726 : }
1727 :
1728 0 : if (BGP_DEBUG(as4, AS4))
1729 0 : zlog_debug(
1730 : "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1731 : aspath->str, as4path->str);
1732 :
1733 0 : while (seg && hops > 0) {
1734 0 : switch (seg->type) {
1735 0 : case AS_SET:
1736 : case AS_CONFED_SET:
1737 0 : hops--;
1738 0 : cpasns = seg->length;
1739 0 : break;
1740 0 : case AS_CONFED_SEQUENCE:
1741 : /* Should never split a confed-sequence, if hop-count
1742 : * suggests we must then something's gone wrong
1743 : * somewhere.
1744 : *
1745 : * Most important goal is to preserve AS_PATHs prime
1746 : * function
1747 : * as loop-detector, so we fudge the numbers so that the
1748 : * entire
1749 : * confed-sequence is merged in.
1750 : */
1751 0 : if (hops < seg->length) {
1752 0 : if (BGP_DEBUG(as4, AS4))
1753 0 : zlog_debug(
1754 : "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls across 2/4 ASN boundary somewhere, broken..");
1755 0 : hops = seg->length;
1756 : }
1757 : /* fallthru */
1758 : case AS_SEQUENCE:
1759 0 : cpasns = MIN(seg->length, hops);
1760 0 : hops -= seg->length;
1761 : }
1762 :
1763 0 : assert(cpasns <= seg->length);
1764 :
1765 0 : newseg = assegment_new(seg->type, 0);
1766 0 : newseg = assegment_append_asns(newseg, seg->as, cpasns);
1767 :
1768 0 : if (!newpath) {
1769 0 : newpath = aspath_new();
1770 0 : newpath->segments = newseg;
1771 : } else
1772 0 : prevseg->next = newseg;
1773 :
1774 0 : prevseg = newseg;
1775 0 : seg = seg->next;
1776 : }
1777 :
1778 : /* We may be able to join some segments here, and we must
1779 : * do this because... we want normalised aspaths in out hash
1780 : * and we do not want to stumble in aspath_put.
1781 : */
1782 0 : mergedpath = aspath_merge(newpath, aspath_dup(as4path));
1783 0 : aspath_free(newpath);
1784 0 : mergedpath->segments = assegment_normalise(mergedpath->segments);
1785 0 : aspath_str_update(mergedpath, false);
1786 :
1787 0 : if (BGP_DEBUG(as4, AS4))
1788 0 : zlog_debug("[AS4] result of synthesizing is %s",
1789 : mergedpath->str);
1790 :
1791 : return mergedpath;
1792 : }
1793 :
1794 : /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1795 : as2's leftmost AS is same return 1. (confederation as-path
1796 : only). */
1797 0 : bool aspath_cmp_left_confed(const struct aspath *aspath1,
1798 : const struct aspath *aspath2)
1799 : {
1800 0 : if (!(aspath1 && aspath2))
1801 : return false;
1802 :
1803 0 : if (!(aspath1->segments && aspath2->segments))
1804 : return false;
1805 :
1806 0 : if ((aspath1->segments->type != AS_CONFED_SEQUENCE)
1807 0 : || (aspath2->segments->type != AS_CONFED_SEQUENCE))
1808 : return false;
1809 :
1810 0 : if (aspath1->segments->as[0] == aspath2->segments->as[0])
1811 0 : return true;
1812 :
1813 : return false;
1814 : }
1815 :
1816 : /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1817 : * RFC 5065 section 4.1.c.1
1818 : *
1819 : * 1) if any path segments of the AS_PATH are of the type
1820 : * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1821 : * removed from the AS_PATH attribute, leaving the sanitized
1822 : * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1823 : */
1824 3 : struct aspath *aspath_delete_confed_seq(struct aspath *aspath)
1825 : {
1826 3 : struct assegment *seg, *prev, *next;
1827 3 : char removed_confed_segment;
1828 :
1829 3 : if (!(aspath && aspath->segments))
1830 : return aspath;
1831 :
1832 : seg = aspath->segments;
1833 : removed_confed_segment = 0;
1834 2 : next = NULL;
1835 : prev = NULL;
1836 :
1837 2 : while (seg) {
1838 1 : next = seg->next;
1839 :
1840 1 : if (seg->type == AS_CONFED_SEQUENCE
1841 1 : || seg->type == AS_CONFED_SET) {
1842 : /* This is the first segment in the aspath */
1843 0 : if (aspath->segments == seg)
1844 0 : aspath->segments = seg->next;
1845 : else
1846 0 : prev->next = seg->next;
1847 :
1848 0 : assegment_free(seg);
1849 0 : removed_confed_segment = 1;
1850 : } else
1851 : prev = seg;
1852 :
1853 : seg = next;
1854 : }
1855 :
1856 1 : if (removed_confed_segment)
1857 0 : aspath_str_update(aspath, false);
1858 :
1859 : return aspath;
1860 : }
1861 :
1862 : /* Add new AS number to the leftmost part of the aspath as
1863 : AS_CONFED_SEQUENCE. */
1864 0 : struct aspath *aspath_add_confed_seq(struct aspath *aspath, as_t asno)
1865 : {
1866 0 : return aspath_add_asns(aspath, asno, AS_CONFED_SEQUENCE, 1);
1867 : }
1868 :
1869 : /* Add new as value to as path structure. */
1870 0 : static void aspath_as_add(struct aspath *as, as_t asno)
1871 : {
1872 0 : struct assegment *seg = as->segments;
1873 :
1874 0 : if (!seg)
1875 : return;
1876 :
1877 : /* Last segment search procedure. */
1878 0 : while (seg->next)
1879 : seg = seg->next;
1880 :
1881 0 : assegment_append_asns(seg, &asno, 1);
1882 : }
1883 :
1884 : /* Add new as segment to the as path. */
1885 0 : static void aspath_segment_add(struct aspath *as, int type)
1886 : {
1887 0 : struct assegment *seg = as->segments;
1888 0 : struct assegment *new = assegment_new(type, 0);
1889 :
1890 0 : if (seg) {
1891 0 : while (seg->next)
1892 : seg = seg->next;
1893 0 : seg->next = new;
1894 : } else
1895 0 : as->segments = new;
1896 0 : }
1897 :
1898 3 : struct aspath *aspath_empty(void)
1899 : {
1900 3 : return aspath_parse(NULL, 0, 1); /* 32Bit ;-) */
1901 : }
1902 :
1903 0 : struct aspath *aspath_empty_get(void)
1904 : {
1905 0 : struct aspath *aspath;
1906 :
1907 0 : aspath = aspath_new();
1908 0 : aspath_make_str_count(aspath, false);
1909 0 : return aspath;
1910 : }
1911 :
1912 0 : unsigned long aspath_count(void)
1913 : {
1914 0 : return ashash->count;
1915 : }
1916 :
1917 : /*
1918 : Theoretically, one as path can have:
1919 :
1920 : One BGP packet size should be less than 4096.
1921 : One BGP attribute size should be less than 4096 - BGP header size.
1922 : One BGP aspath size should be less than 4096 - BGP header size -
1923 : BGP mandantry attribute size.
1924 : */
1925 :
1926 : /* AS path string lexical token enum. */
1927 : enum as_token {
1928 : as_token_asval,
1929 : as_token_set_start,
1930 : as_token_set_end,
1931 : as_token_confed_seq_start,
1932 : as_token_confed_seq_end,
1933 : as_token_confed_set_start,
1934 : as_token_confed_set_end,
1935 : as_token_unknown
1936 : };
1937 :
1938 : /* Return next token and point for string parse. */
1939 0 : static const char *aspath_gettoken(const char *buf, enum as_token *token,
1940 : unsigned long *asno)
1941 : {
1942 0 : const char *p = buf;
1943 :
1944 : /* Skip separators (space for sequences, ',' for sets). */
1945 0 : while (isspace((unsigned char)*p) || *p == ',')
1946 0 : p++;
1947 :
1948 : /* Check the end of the string and type specify characters
1949 : (e.g. {}()). */
1950 0 : switch (*p) {
1951 : case '\0':
1952 : return NULL;
1953 0 : case '{':
1954 0 : *token = as_token_set_start;
1955 0 : p++;
1956 0 : return p;
1957 0 : case '}':
1958 0 : *token = as_token_set_end;
1959 0 : p++;
1960 0 : return p;
1961 0 : case '(':
1962 0 : *token = as_token_confed_seq_start;
1963 0 : p++;
1964 0 : return p;
1965 0 : case ')':
1966 0 : *token = as_token_confed_seq_end;
1967 0 : p++;
1968 0 : return p;
1969 0 : case '[':
1970 0 : *token = as_token_confed_set_start;
1971 0 : p++;
1972 0 : return p;
1973 0 : case ']':
1974 0 : *token = as_token_confed_set_end;
1975 0 : p++;
1976 0 : return p;
1977 : }
1978 :
1979 : /* Check actual AS value. */
1980 0 : if (isdigit((unsigned char)*p)) {
1981 0 : as_t asval;
1982 :
1983 0 : *token = as_token_asval;
1984 0 : asval = (*p - '0');
1985 0 : p++;
1986 :
1987 0 : while (isdigit((unsigned char)*p)) {
1988 0 : asval *= 10;
1989 0 : asval += (*p - '0');
1990 0 : p++;
1991 : }
1992 0 : *asno = asval;
1993 0 : return p;
1994 : }
1995 :
1996 : /* There is no match then return unknown token. */
1997 0 : *token = as_token_unknown;
1998 0 : p++;
1999 0 : return p;
2000 : }
2001 :
2002 0 : struct aspath *aspath_str2aspath(const char *str)
2003 : {
2004 0 : enum as_token token = as_token_unknown;
2005 0 : unsigned short as_type;
2006 0 : unsigned long asno = 0;
2007 0 : struct aspath *aspath;
2008 0 : int needtype;
2009 :
2010 0 : aspath = aspath_new();
2011 :
2012 : /* We start default type as AS_SEQUENCE. */
2013 0 : as_type = AS_SEQUENCE;
2014 0 : needtype = 1;
2015 :
2016 0 : while ((str = aspath_gettoken(str, &token, &asno)) != NULL) {
2017 0 : switch (token) {
2018 0 : case as_token_asval:
2019 0 : if (needtype) {
2020 0 : aspath_segment_add(aspath, as_type);
2021 0 : needtype = 0;
2022 : }
2023 0 : aspath_as_add(aspath, asno);
2024 0 : break;
2025 0 : case as_token_set_start:
2026 0 : as_type = AS_SET;
2027 0 : aspath_segment_add(aspath, as_type);
2028 0 : needtype = 0;
2029 0 : break;
2030 : case as_token_set_end:
2031 : as_type = AS_SEQUENCE;
2032 : needtype = 1;
2033 : break;
2034 0 : case as_token_confed_seq_start:
2035 0 : as_type = AS_CONFED_SEQUENCE;
2036 0 : aspath_segment_add(aspath, as_type);
2037 0 : needtype = 0;
2038 0 : break;
2039 : case as_token_confed_seq_end:
2040 : as_type = AS_SEQUENCE;
2041 : needtype = 1;
2042 : break;
2043 0 : case as_token_confed_set_start:
2044 0 : as_type = AS_CONFED_SET;
2045 0 : aspath_segment_add(aspath, as_type);
2046 0 : needtype = 0;
2047 0 : break;
2048 : case as_token_confed_set_end:
2049 : as_type = AS_SEQUENCE;
2050 : needtype = 1;
2051 : break;
2052 0 : case as_token_unknown:
2053 : default:
2054 0 : aspath_free(aspath);
2055 0 : return NULL;
2056 : }
2057 : }
2058 :
2059 0 : aspath_make_str_count(aspath, false);
2060 :
2061 0 : return aspath;
2062 : }
2063 :
2064 : /* Make hash value by raw aspath data. */
2065 37 : unsigned int aspath_key_make(const void *p)
2066 : {
2067 37 : const struct aspath *aspath = p;
2068 37 : unsigned int key = 0;
2069 :
2070 37 : if (!aspath->str)
2071 6 : aspath_str_update((struct aspath *)aspath, false);
2072 :
2073 37 : key = jhash(aspath->str, aspath->str_len, 2334325);
2074 :
2075 37 : return key;
2076 : }
2077 :
2078 : /* If two aspath have same value then return 1 else return 0 */
2079 6 : bool aspath_cmp(const void *arg1, const void *arg2)
2080 : {
2081 6 : const struct assegment *seg1 = ((const struct aspath *)arg1)->segments;
2082 6 : const struct assegment *seg2 = ((const struct aspath *)arg2)->segments;
2083 :
2084 9 : while (seg1 || seg2) {
2085 3 : int i;
2086 3 : if ((!seg1 && seg2) || (seg1 && !seg2))
2087 : return false;
2088 3 : if (seg1->type != seg2->type)
2089 : return false;
2090 3 : if (seg1->length != seg2->length)
2091 : return false;
2092 7 : for (i = 0; i < seg1->length; i++)
2093 4 : if (seg1->as[i] != seg2->as[i])
2094 : return false;
2095 3 : seg1 = seg1->next;
2096 3 : seg2 = seg2->next;
2097 : }
2098 : return true;
2099 : }
2100 :
2101 : /* AS path hash initialize. */
2102 2 : void aspath_init(void)
2103 : {
2104 2 : ashash = hash_create_size(32768, aspath_key_make, aspath_cmp,
2105 : "BGP AS Path");
2106 2 : }
2107 :
2108 2 : void aspath_finish(void)
2109 : {
2110 2 : hash_clean(ashash, (void (*)(void *))aspath_free);
2111 2 : hash_free(ashash);
2112 2 : ashash = NULL;
2113 :
2114 2 : if (snmp_stream)
2115 0 : stream_free(snmp_stream);
2116 2 : }
2117 :
2118 : /* return and as path value */
2119 0 : const char *aspath_print(struct aspath *as)
2120 : {
2121 0 : return (as ? as->str : NULL);
2122 : }
2123 :
2124 : /* Printing functions */
2125 : /* Feed the AS_PATH to the vty; the space suffix follows it only in case
2126 : * AS_PATH wasn't empty.
2127 : */
2128 0 : void aspath_print_vty(struct vty *vty, struct aspath *as)
2129 : {
2130 0 : vty_out(vty, "%s%s", as->str, as->str_len ? " " : "");
2131 0 : }
2132 :
2133 0 : static void aspath_show_all_iterator(struct hash_bucket *bucket,
2134 : struct vty *vty)
2135 : {
2136 0 : struct aspath *as;
2137 :
2138 0 : as = (struct aspath *)bucket->data;
2139 :
2140 0 : vty_out(vty, "[%p:%u] (%ld) ", (void *)bucket, bucket->key, as->refcnt);
2141 0 : vty_out(vty, "%s\n", as->str);
2142 0 : }
2143 :
2144 : /* Print all aspath and hash information. This function is used from
2145 : `show [ip] bgp paths' command. */
2146 0 : void aspath_print_all_vty(struct vty *vty)
2147 : {
2148 0 : hash_iterate(ashash, (void (*)(struct hash_bucket *,
2149 : void *))aspath_show_all_iterator,
2150 : vty);
2151 0 : }
2152 :
2153 0 : static struct aspath *bgp_aggr_aspath_lookup(struct bgp_aggregate *aggregate,
2154 : struct aspath *aspath)
2155 : {
2156 0 : return hash_lookup(aggregate->aspath_hash, aspath);
2157 : }
2158 :
2159 0 : static void *bgp_aggr_aspath_hash_alloc(void *p)
2160 : {
2161 0 : struct aspath *ref = (struct aspath *)p;
2162 0 : struct aspath *aspath = NULL;
2163 :
2164 0 : aspath = aspath_dup(ref);
2165 0 : return aspath;
2166 : }
2167 :
2168 0 : static void bgp_aggr_aspath_prepare(struct hash_bucket *hb, void *arg)
2169 : {
2170 0 : struct aspath *hb_aspath = hb->data;
2171 0 : struct aspath **aggr_aspath = arg;
2172 :
2173 0 : if (*aggr_aspath)
2174 0 : *aggr_aspath = aspath_aggregate(*aggr_aspath, hb_aspath);
2175 : else
2176 0 : *aggr_aspath = aspath_dup(hb_aspath);
2177 0 : }
2178 :
2179 0 : void bgp_aggr_aspath_remove(void *arg)
2180 : {
2181 0 : struct aspath *aspath = arg;
2182 :
2183 0 : aspath_free(aspath);
2184 0 : }
2185 :
2186 0 : void bgp_compute_aggregate_aspath(struct bgp_aggregate *aggregate,
2187 : struct aspath *aspath)
2188 : {
2189 0 : bgp_compute_aggregate_aspath_hash(aggregate, aspath);
2190 :
2191 0 : bgp_compute_aggregate_aspath_val(aggregate);
2192 :
2193 0 : }
2194 :
2195 0 : void bgp_compute_aggregate_aspath_hash(struct bgp_aggregate *aggregate,
2196 : struct aspath *aspath)
2197 : {
2198 0 : struct aspath *aggr_aspath = NULL;
2199 :
2200 0 : if ((aggregate == NULL) || (aspath == NULL))
2201 : return;
2202 :
2203 : /* Create hash if not already created.
2204 : */
2205 0 : if (aggregate->aspath_hash == NULL)
2206 0 : aggregate->aspath_hash = hash_create(
2207 : aspath_key_make, aspath_cmp,
2208 : "BGP Aggregator as-path hash");
2209 :
2210 0 : aggr_aspath = bgp_aggr_aspath_lookup(aggregate, aspath);
2211 0 : if (aggr_aspath == NULL) {
2212 : /* Insert as-path into hash.
2213 : */
2214 0 : aggr_aspath = hash_get(aggregate->aspath_hash, aspath,
2215 : bgp_aggr_aspath_hash_alloc);
2216 : }
2217 :
2218 : /* Increment reference counter.
2219 : */
2220 0 : aggr_aspath->refcnt++;
2221 : }
2222 :
2223 0 : void bgp_compute_aggregate_aspath_val(struct bgp_aggregate *aggregate)
2224 : {
2225 0 : if (aggregate == NULL)
2226 : return;
2227 : /* Re-compute aggregate's as-path.
2228 : */
2229 0 : if (aggregate->aspath) {
2230 0 : aspath_free(aggregate->aspath);
2231 0 : aggregate->aspath = NULL;
2232 : }
2233 0 : if (aggregate->aspath_hash
2234 0 : && aggregate->aspath_hash->count) {
2235 0 : hash_iterate(aggregate->aspath_hash,
2236 : bgp_aggr_aspath_prepare,
2237 0 : &aggregate->aspath);
2238 : }
2239 : }
2240 :
2241 0 : void bgp_remove_aspath_from_aggregate(struct bgp_aggregate *aggregate,
2242 : struct aspath *aspath)
2243 : {
2244 0 : struct aspath *aggr_aspath = NULL;
2245 0 : struct aspath *ret_aspath = NULL;
2246 :
2247 0 : if ((!aggregate)
2248 0 : || (!aggregate->aspath_hash)
2249 0 : || (!aspath))
2250 : return;
2251 :
2252 : /* Look-up the aspath in the hash.
2253 : */
2254 0 : aggr_aspath = bgp_aggr_aspath_lookup(aggregate, aspath);
2255 0 : if (aggr_aspath) {
2256 0 : aggr_aspath->refcnt--;
2257 :
2258 0 : if (aggr_aspath->refcnt == 0) {
2259 0 : ret_aspath = hash_release(aggregate->aspath_hash,
2260 : aggr_aspath);
2261 0 : aspath_free(ret_aspath);
2262 0 : ret_aspath = NULL;
2263 :
2264 : /* Remove aggregate's old as-path.
2265 : */
2266 0 : aspath_free(aggregate->aspath);
2267 0 : aggregate->aspath = NULL;
2268 :
2269 0 : bgp_compute_aggregate_aspath_val(aggregate);
2270 : }
2271 : }
2272 : }
2273 :
2274 0 : void bgp_remove_aspath_from_aggregate_hash(struct bgp_aggregate *aggregate,
2275 : struct aspath *aspath)
2276 : {
2277 0 : struct aspath *aggr_aspath = NULL;
2278 0 : struct aspath *ret_aspath = NULL;
2279 :
2280 0 : if ((!aggregate)
2281 0 : || (!aggregate->aspath_hash)
2282 0 : || (!aspath))
2283 : return;
2284 :
2285 : /* Look-up the aspath in the hash.
2286 : */
2287 0 : aggr_aspath = bgp_aggr_aspath_lookup(aggregate, aspath);
2288 0 : if (aggr_aspath) {
2289 0 : aggr_aspath->refcnt--;
2290 :
2291 0 : if (aggr_aspath->refcnt == 0) {
2292 0 : ret_aspath = hash_release(aggregate->aspath_hash,
2293 : aggr_aspath);
2294 0 : aspath_free(ret_aspath);
2295 0 : ret_aspath = NULL;
2296 : }
2297 : }
2298 : }
2299 :
|
