1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* AS path management routines.
3 * Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro
4 * Copyright (C) 2005 Sun Microsystems, Inc.
19 #include "bgpd/bgpd.h"
20 #include "bgpd/bgp_aspath.h"
21 #include "bgpd/bgp_debug.h"
22 #include "bgpd/bgp_attr.h"
23 #include "bgpd/bgp_errors.h"
25 /* Attr. Flags and Attr. Type Code. */
26 #define AS_HEADER_SIZE 2
28 /* Now FOUR octets are used for AS value. */
29 #define AS_VALUE_SIZE sizeof(as_t)
30 /* This is the old one */
31 #define AS16_VALUE_SIZE sizeof(as16_t)
33 /* Maximum protocol segment length value */
34 #define AS_SEGMENT_MAX 255
36 /* The following length and size macros relate specifically to Quagga's
37 * internal representation of AS-Segments, not per se to the on-wire
38 * sizes and lengths. At present (200508) they sort of match, however
39 * the ONLY functions which should now about the on-wire syntax are
40 * aspath_put, assegment_put and assegment_parse.
42 * aspath_put returns bytes written, the only definitive record of
43 * size of wire-format attribute..
46 /* Calculated size in bytes of ASN segment data to hold N ASN's */
47 #define ASSEGMENT_DATA_SIZE(N, S) \
48 ((N) * ((S) ? AS_VALUE_SIZE : AS16_VALUE_SIZE))
50 /* Calculated size of segment struct to hold N ASN's */
51 #define ASSEGMENT_SIZE(N,S) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N,S))
53 /* AS segment octet length. */
54 #define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S)
56 /* AS_SEQUENCE segments can be packed together */
57 /* Can the types of X and Y be considered for packing? */
58 #define ASSEGMENT_TYPES_PACKABLE(X, Y) \
59 (((X)->type == (Y)->type) && ((X)->type == AS_SEQUENCE))
60 /* Types and length of X,Y suitable for packing? */
61 #define ASSEGMENTS_PACKABLE(X, Y) \
62 (ASSEGMENT_TYPES_PACKABLE((X), (Y)) \
63 && (((X)->length + (Y)->length) <= AS_SEGMENT_MAX))
65 /* As segment header - the on-wire representation
66 * NOT the internal representation!
68 struct assegment_header
{
73 /* Hash for aspath. This is the top level structure of AS path. */
74 static struct hash
*ashash
;
76 /* Stream for SNMP. See aspath_snmp_pathseg */
77 static struct stream
*snmp_stream
;
79 /* Callers are required to initialize the memory */
80 static as_t
*assegment_data_new(int num
)
82 return (XMALLOC(MTYPE_AS_SEG_DATA
, ASSEGMENT_DATA_SIZE(num
, 1)));
85 static void assegment_data_free(as_t
*asdata
)
87 XFREE(MTYPE_AS_SEG_DATA
, asdata
);
90 const char *const aspath_segment_type_str
[] = {
91 "as-invalid", "as-set", "as-sequence", "as-confed-sequence",
95 /* Get a new segment. Note that 0 is an allowed length,
96 * and will result in a segment with no allocated data segment.
97 * the caller should immediately assign data to the segment, as the segment
98 * otherwise is not generally valid
100 static struct assegment
*assegment_new(uint8_t type
, unsigned short length
)
102 struct assegment
*new;
104 new = XCALLOC(MTYPE_AS_SEG
, sizeof(struct assegment
));
107 new->as
= assegment_data_new(length
);
109 new->length
= length
;
115 static void assegment_free(struct assegment
*seg
)
120 assegment_data_free(seg
->as
);
121 memset(seg
, 0xfe, sizeof(struct assegment
));
122 XFREE(MTYPE_AS_SEG
, seg
);
127 /* free entire chain of segments */
128 static void assegment_free_all(struct assegment
*seg
)
130 struct assegment
*prev
;
135 assegment_free(prev
);
139 /* Duplicate just the given assegment and its data */
140 static struct assegment
*assegment_dup(struct assegment
*seg
)
142 struct assegment
*new;
144 new = assegment_new(seg
->type
, seg
->length
);
145 memcpy(new->as
, seg
->as
, ASSEGMENT_DATA_SIZE(new->length
, 1));
150 /* Duplicate entire chain of assegments, return the head */
151 static struct assegment
*assegment_dup_all(struct assegment
*seg
)
153 struct assegment
*new = NULL
;
154 struct assegment
*head
= NULL
;
158 new->next
= assegment_dup(seg
);
161 head
= new = assegment_dup(seg
);
168 /* prepend the as number to given segment, given num of times */
169 static struct assegment
*assegment_prepend_asns(struct assegment
*seg
,
178 if (num
>= AS_SEGMENT_MAX
)
179 return seg
; /* we don't do huge prepends */
181 newas
= assegment_data_new(seg
->length
+ num
);
185 for (i
= 0; i
< num
; i
++)
188 memcpy(newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE(seg
->length
, 1));
189 assegment_data_free(seg
->as
);
196 /* append given array of as numbers to the segment */
197 static struct assegment
*assegment_append_asns(struct assegment
*seg
,
198 as_t
*asnos
, int num
)
205 newas
= XREALLOC(MTYPE_AS_SEG_DATA
, seg
->as
,
206 ASSEGMENT_DATA_SIZE(seg
->length
+ num
, 1));
209 memcpy(seg
->as
+ seg
->length
, asnos
,
210 ASSEGMENT_DATA_SIZE(num
, 1));
215 static int int_cmp(const void *p1
, const void *p2
)
217 const as_t
*as1
= p1
;
218 const as_t
*as2
= p2
;
220 return (*as1
== *as2
) ? 0 : ((*as1
> *as2
) ? 1 : -1);
223 /* normalise the segment.
224 * In particular, merge runs of AS_SEQUENCEs into one segment
225 * Internally, we do not care about the wire segment length limit, and
226 * we want each distinct AS_PATHs to have the exact same internal
227 * representation - eg, so that our hashing actually works..
229 static struct assegment
*assegment_normalise(struct assegment
*head
)
231 struct assegment
*seg
= head
, *pin
;
232 struct assegment
*tmp
;
240 /* Sort values SET segments, for determinism in paths to aid
241 * creation of hash values / path comparisons
242 * and because it helps other lesser implementations ;)
244 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
) {
248 qsort(seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
251 for (i
= 1; i
< seg
->length
; i
++) {
252 if (seg
->as
[tail
] == seg
->as
[i
])
257 seg
->as
[tail
] = seg
->as
[i
];
259 /* seg->length can be 0.. */
261 seg
->length
= tail
+ 1;
264 /* read ahead from the current, pinned segment while the
266 * are packable/mergeable. Append all following packable
268 * to the segment we have pinned and remove these appended
271 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
)) {
275 /* append the next sequence to the pinned sequence */
276 pin
= assegment_append_asns(pin
, seg
->as
, seg
->length
);
278 /* bypass the next sequence */
279 pin
->next
= seg
->next
;
281 /* get rid of the now referenceless segment */
290 static struct aspath
*aspath_new(enum asnotation_mode asnotation
)
294 as
= XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
295 as
->asnotation
= asnotation
;
299 /* Free AS path structure. */
300 void aspath_free(struct aspath
*aspath
)
304 if (aspath
->segments
)
305 assegment_free_all(aspath
->segments
);
306 XFREE(MTYPE_AS_STR
, aspath
->str
);
309 json_object_free(aspath
->json
);
313 XFREE(MTYPE_AS_PATH
, aspath
);
316 /* Unintern aspath from AS path bucket. */
317 void aspath_unintern(struct aspath
**aspath
)
330 if (asp
->refcnt
== 0) {
331 /* This aspath must exist in aspath hash table. */
332 ret
= hash_release(ashash
, asp
);
339 /* Return the start or end delimiters for a particular Segment type */
340 #define AS_SEG_START 0
342 static char aspath_delimiter_char(uint8_t type
, uint8_t which
)
349 } aspath_delim_char
[] = {{AS_SET
, '{', '}'},
350 {AS_CONFED_SET
, '[', ']'},
351 {AS_CONFED_SEQUENCE
, '(', ')'},
354 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++) {
355 if (aspath_delim_char
[i
].type
== type
) {
356 if (which
== AS_SEG_START
)
357 return aspath_delim_char
[i
].start
;
358 else if (which
== AS_SEG_END
)
359 return aspath_delim_char
[i
].end
;
365 /* countup asns from this segment and index onward */
366 static int assegment_count_asns(struct assegment
*seg
, int from
)
371 count
+= seg
->length
;
373 count
+= (seg
->length
- from
);
381 unsigned int aspath_count_confeds(struct aspath
*aspath
)
384 struct assegment
*seg
= aspath
->segments
;
387 if (seg
->type
== AS_CONFED_SEQUENCE
)
388 count
+= seg
->length
;
389 else if (seg
->type
== AS_CONFED_SET
)
397 unsigned int aspath_count_hops(const struct aspath
*aspath
)
400 struct assegment
*seg
= aspath
->segments
;
403 if (seg
->type
== AS_SEQUENCE
)
404 count
+= seg
->length
;
405 else if (seg
->type
== AS_SET
)
413 /* Check if aspath has AS_SET or AS_CONFED_SET */
414 bool aspath_check_as_sets(struct aspath
*aspath
)
416 struct assegment
*seg
= aspath
->segments
;
419 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
)
426 /* Check if aspath has BGP_AS_ZERO */
427 bool aspath_check_as_zero(struct aspath
*aspath
)
429 struct assegment
*seg
= aspath
->segments
;
433 for (i
= 0; i
< seg
->length
; i
++)
434 if (seg
->as
[i
] == BGP_AS_ZERO
)
442 /* Estimate size aspath /might/ take if encoded into an
445 * This is a quick estimate, not definitive! aspath_put()
446 * may return a different number!!
448 unsigned int aspath_size(struct aspath
*aspath
)
451 struct assegment
*seg
= aspath
->segments
;
454 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
460 /* Return highest public ASN in path */
461 as_t
aspath_highest(struct aspath
*aspath
)
463 struct assegment
*seg
= aspath
->segments
;
468 for (i
= 0; i
< seg
->length
; i
++)
469 if (seg
->as
[i
] > highest
470 && !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
471 highest
= seg
->as
[i
];
477 /* Return the left-most ASN in path */
478 as_t
aspath_leftmost(struct aspath
*aspath
)
480 struct assegment
*seg
= aspath
->segments
;
483 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
484 leftmost
= seg
->as
[0];
489 /* Return 1 if there are any 4-byte ASes in the path */
490 bool aspath_has_as4(struct aspath
*aspath
)
492 struct assegment
*seg
= aspath
->segments
;
496 for (i
= 0; i
< seg
->length
; i
++)
497 if (seg
->as
[i
] > BGP_AS_MAX
)
504 /* Convert aspath structure to string expression. */
505 static void aspath_make_str_count(struct aspath
*as
, bool make_json
)
507 struct assegment
*seg
;
511 json_object
*jaspath_segments
= NULL
;
512 json_object
*jseg
= NULL
;
513 json_object
*jseg_list
= NULL
;
516 as
->json
= json_object_new_object();
517 jaspath_segments
= json_object_new_array();
523 json_object_string_add(as
->json
, "string", "Local");
524 json_object_object_add(as
->json
, "segments",
526 json_object_int_add(as
->json
, "length", 0);
528 as
->str
= XMALLOC(MTYPE_AS_STR
, 1);
536 /* ASN takes 5 to 10 chars plus separator, see below.
537 * If there is one differing segment type, we need an additional
538 * 2 chars for segment delimiters, and the final '\0'.
539 * Hopefully this is large enough to avoid hitting the realloc
540 * code below for most common sequences.
542 * This was changed to 10 after the well-known BGP assertion, which
543 * had hit some parts of the Internet in May of 2009.
544 * plain format : '4294967295 ' : 10 + 1
545 * astod format : '65535.65535 ': 11 + 1
547 #define ASN_STR_LEN (11 + 1)
548 str_size
= MAX(assegment_count_asns(seg
, 0) * ASN_STR_LEN
+ 2 + 1,
549 ASPATH_STR_DEFAULT_LEN
);
550 str_buf
= XMALLOC(MTYPE_AS_STR
, str_size
);
556 /* Check AS type validity. Set separator for segment */
563 case AS_CONFED_SEQUENCE
:
567 XFREE(MTYPE_AS_STR
, str_buf
);
570 json_object_free(as
->json
);
576 /* We might need to increase str_buf, particularly if path has
577 * differing segments types, our initial guesstimate above will
578 * have been wrong. Need 11 chars for ASN, a separator each and
579 * potentially two segment delimiters, plus a space between each
580 * segment and trailing zero.
582 * This definitely didn't work with the value of 5 bytes and
585 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
586 if ((len
+ SEGMENT_STR_LEN(seg
)) > str_size
) {
587 str_size
= len
+ SEGMENT_STR_LEN(seg
);
588 str_buf
= XREALLOC(MTYPE_AS_STR
, str_buf
, str_size
);
591 #undef SEGMENT_STR_LEN
593 if (seg
->type
!= AS_SEQUENCE
)
595 str_buf
+ len
, str_size
- len
, "%c",
596 aspath_delimiter_char(seg
->type
, AS_SEG_START
));
599 jseg_list
= json_object_new_array();
601 /* write out the ASNs, with their separators, bar the last one*/
602 for (i
= 0; i
< seg
->length
; i
++) {
604 asn_asn2json_array(jseg_list
, seg
->as
[i
],
606 len
+= snprintfrr(str_buf
+ len
, str_size
- len
,
607 ASN_FORMAT(as
->asnotation
),
610 if (i
< (seg
->length
- 1))
611 len
+= snprintf(str_buf
+ len
, str_size
- len
,
616 jseg
= json_object_new_object();
617 json_object_string_add(
619 aspath_segment_type_str
[seg
->type
]);
620 json_object_object_add(jseg
, "list", jseg_list
);
621 json_object_array_add(jaspath_segments
, jseg
);
624 if (seg
->type
!= AS_SEQUENCE
)
626 str_buf
+ len
, str_size
- len
, "%c",
627 aspath_delimiter_char(seg
->type
, AS_SEG_END
));
629 len
+= snprintf(str_buf
+ len
, str_size
- len
, " ");
634 assert(len
< str_size
);
641 json_object_string_add(as
->json
, "string", str_buf
);
642 json_object_object_add(as
->json
, "segments", jaspath_segments
);
643 json_object_int_add(as
->json
, "length", aspath_count_hops(as
));
649 void aspath_str_update(struct aspath
*as
, bool make_json
)
651 XFREE(MTYPE_AS_STR
, as
->str
);
654 json_object_free(as
->json
);
658 aspath_make_str_count(as
, make_json
);
661 /* Intern allocated AS path. */
662 struct aspath
*aspath_intern(struct aspath
*aspath
)
666 /* Assert this AS path structure is not interned and has the string
667 representation built. */
668 assert(aspath
->refcnt
== 0);
671 /* Check AS path hash. */
672 find
= hash_get(ashash
, aspath
, hash_alloc_intern
);
681 /* Duplicate aspath structure. Created same aspath structure but
682 reference count and AS path string is cleared. */
683 struct aspath
*aspath_dup(struct aspath
*aspath
)
685 unsigned short buflen
= aspath
->str_len
+ 1;
688 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
691 if (aspath
->segments
)
692 new->segments
= assegment_dup_all(aspath
->segments
);
697 new->str
= XMALLOC(MTYPE_AS_STR
, buflen
);
698 new->str_len
= aspath
->str_len
;
699 new->asnotation
= aspath
->asnotation
;
701 /* copy the string data */
702 if (aspath
->str_len
> 0)
703 memcpy(new->str
, aspath
->str
, buflen
);
710 static void *aspath_hash_alloc(void *arg
)
712 const struct aspath
*aspath
= arg
;
715 /* Malformed AS path value. */
718 /* New aspath structure is needed. */
719 new = XMALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
721 /* Reuse segments and string representation */
723 new->segments
= aspath
->segments
;
724 new->str
= aspath
->str
;
725 new->str_len
= aspath
->str_len
;
726 new->json
= aspath
->json
;
727 new->asnotation
= aspath
->asnotation
;
732 /* parse as-segment byte stream in struct assegment */
733 static int assegments_parse(struct stream
*s
, size_t length
,
734 struct assegment
**result
, int use32bit
)
736 struct assegment_header segh
;
737 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
740 /* empty aspath (ie iBGP or somesuch) */
744 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
746 "[AS4SEG] Parse aspath segment: got total byte length %lu",
747 (unsigned long)length
);
749 if ((STREAM_READABLE(s
) < length
)
750 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
751 || (length
% AS16_VALUE_SIZE
))
754 while (bytes
< length
) {
758 if ((length
- bytes
) <= AS_HEADER_SIZE
) {
760 assegment_free_all(head
);
764 /* softly softly, get the header first on its own */
765 segh
.type
= stream_getc(s
);
766 segh
.length
= stream_getc(s
);
768 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
770 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
772 "[AS4SEG] Parse aspath segment: got type %d, length %d",
773 segh
.type
, segh
.length
);
776 if (((bytes
+ seg_size
) > length
)
777 /* 1771bis 4.3b: seg length contains one or more */
778 || (segh
.length
== 0)
779 /* Paranoia in case someone changes type of segment length.
780 * Shift both values by 0x10 to make the comparison operate
781 * on more, than 8 bits (otherwise it's a warning, bug
784 || ((sizeof(segh
.length
) > 1)
785 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
))) {
787 assegment_free_all(head
);
794 case AS_CONFED_SEQUENCE
:
799 assegment_free_all(head
);
803 /* now its safe to trust lengths */
804 seg
= assegment_new(segh
.type
, segh
.length
);
808 else /* it's the first segment */
811 for (i
= 0; i
< segh
.length
; i
++)
813 (use32bit
) ? stream_getl(s
) : stream_getw(s
);
817 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
819 "[AS4SEG] Parse aspath segment: Bytes now: %lu",
820 (unsigned long)bytes
);
825 *result
= assegment_normalise(head
);
829 /* AS path parse function. pnt is a pointer to byte stream and length
830 is length of byte stream. If there is same AS path in the the AS
831 path hash then return it else make new AS path structure.
833 On error NULL is returned.
835 struct aspath
*aspath_parse(struct stream
*s
, size_t length
, int use32bit
,
836 enum asnotation_mode asnotation
)
841 /* If length is odd it's malformed AS path. */
842 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
843 * otherwise its malformed when length is larger than 2 and (length-2)
844 * is not dividable by 4.
845 * But... this time we're lazy
847 if (length
% AS16_VALUE_SIZE
)
850 memset(&as
, 0, sizeof(as
));
851 as
.asnotation
= asnotation
;
852 if (assegments_parse(s
, length
, &as
.segments
, use32bit
) < 0)
855 /* If already same aspath exist then return it. */
856 find
= hash_get(ashash
, &as
, aspath_hash_alloc
);
858 /* if the aspath was already hashed free temporary memory. */
860 assegment_free_all(as
.segments
);
861 /* aspath_key_make() always updates the string */
862 XFREE(MTYPE_AS_STR
, as
.str
);
864 json_object_free(as
.json
);
874 static void assegment_data_put(struct stream
*s
, as_t
*as
, int num
,
878 assert(num
<= AS_SEGMENT_MAX
);
880 for (i
= 0; i
< num
; i
++)
882 stream_putl(s
, as
[i
]);
884 if (as
[i
] <= BGP_AS_MAX
)
885 stream_putw(s
, as
[i
]);
887 stream_putw(s
, BGP_AS_TRANS
);
891 static size_t assegment_header_put(struct stream
*s
, uint8_t type
, int length
)
894 assert(length
<= AS_SEGMENT_MAX
);
895 stream_putc(s
, type
);
896 lenp
= stream_get_endp(s
);
897 stream_putc(s
, length
);
901 /* write aspath data to stream */
902 size_t aspath_put(struct stream
*s
, struct aspath
*as
, int use32bit
)
904 struct assegment
*seg
= as
->segments
;
907 if (!seg
|| seg
->length
== 0)
911 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
912 * At the moment, we would write out a partial aspath, and our
914 * will complain and drop the session :-/
916 * The general assumption here is that many things tested will
917 * never happen. And, in real live, up to now, they have not.
919 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
) <= STREAM_WRITEABLE(s
))) {
920 struct assegment
*next
= seg
->next
;
925 /* Overlength segments have to be split up */
926 while ((seg
->length
- written
) > AS_SEGMENT_MAX
) {
927 assegment_header_put(s
, seg
->type
, AS_SEGMENT_MAX
);
928 assegment_data_put(s
, (seg
->as
+ written
),
929 AS_SEGMENT_MAX
, use32bit
);
930 written
+= AS_SEGMENT_MAX
;
931 bytes
+= ASSEGMENT_SIZE(AS_SEGMENT_MAX
, use32bit
);
934 /* write the final segment, probably is also the first
936 lenp
= assegment_header_put(s
, seg
->type
,
937 seg
->length
- written
);
938 assegment_data_put(s
, (seg
->as
+ written
),
939 seg
->length
- written
, use32bit
);
941 /* Sequence-type segments can be 'packed' together
942 * Case of a segment which was overlength and split up
943 * will be missed here, but that doesn't matter.
945 while (next
&& ASSEGMENTS_PACKABLE(seg
, next
)) {
946 /* NB: We should never normally get here given
948 * normalise aspath data when parse them.
950 * safe than sorry. We potentially could call
951 * assegment_normalise here instead, but it's
953 * easier to do it on the fly here rather than
955 * the segment list twice every time we write
960 /* Next segment's data can fit in this one */
961 assegment_data_put(s
, next
->as
, next
->length
, use32bit
);
963 /* update the length of the segment header */
964 stream_putc_at(s
, lenp
,
965 seg
->length
- written
+ next
->length
);
966 asns_packed
+= next
->length
;
971 bytes
+= ASSEGMENT_SIZE(seg
->length
- written
+ asns_packed
,
978 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
979 * We have no way to manage the storage, so we use a static stream
980 * wrapper around aspath_put.
982 uint8_t *aspath_snmp_pathseg(struct aspath
*as
, size_t *varlen
)
984 #define SNMP_PATHSEG_MAX 1024
987 snmp_stream
= stream_new(SNMP_PATHSEG_MAX
);
989 stream_reset(snmp_stream
);
995 aspath_put(snmp_stream
, as
, 0); /* use 16 bit for now here */
997 *varlen
= stream_get_endp(snmp_stream
);
998 return stream_pnt(snmp_stream
);
1001 static struct assegment
*aspath_aggregate_as_set_add(struct aspath
*aspath
,
1002 struct assegment
*asset
,
1007 /* If this is first AS set member, create new as-set segment. */
1008 if (asset
== NULL
) {
1009 asset
= assegment_new(AS_SET
, 1);
1010 if (!aspath
->segments
)
1011 aspath
->segments
= asset
;
1013 struct assegment
*seg
= aspath
->segments
;
1018 asset
->type
= AS_SET
;
1022 /* Check this AS value already exists or not. */
1023 for (i
= 0; i
< asset
->length
; i
++)
1024 if (asset
->as
[i
] == as
)
1028 asset
->as
= XREALLOC(MTYPE_AS_SEG_DATA
, asset
->as
,
1029 asset
->length
* AS_VALUE_SIZE
);
1030 asset
->as
[asset
->length
- 1] = as
;
1037 /* Modify as1 using as2 for aggregation. */
1038 struct aspath
*aspath_aggregate(struct aspath
*as1
, struct aspath
*as2
)
1044 struct assegment
*seg1
= as1
->segments
;
1045 struct assegment
*seg2
= as2
->segments
;
1046 struct aspath
*aspath
= NULL
;
1047 struct assegment
*asset
= NULL
;
1048 struct assegment
*prevseg
= NULL
;
1050 /* First of all check common leading sequence. */
1051 while (seg1
&& seg2
) {
1052 /* Check segment type. */
1053 if (seg1
->type
!= seg2
->type
)
1056 /* Minimum segment length. */
1057 minlen
= MIN(seg1
->length
, seg2
->length
);
1059 for (match
= 0; match
< minlen
; match
++)
1060 if (seg1
->as
[match
] != seg2
->as
[match
])
1064 struct assegment
*seg
= assegment_new(seg1
->type
, 0);
1066 seg
= assegment_append_asns(seg
, seg1
->as
, match
);
1069 aspath
= aspath_new(as1
->asnotation
);
1070 aspath
->segments
= seg
;
1072 prevseg
->next
= seg
;
1077 if (match
!= minlen
|| match
!= seg1
->length
1078 || seg1
->length
!= seg2
->length
)
1080 /* We are moving on to the next segment to reset match */
1089 aspath
= aspath_new(as1
->asnotation
);
1091 /* Make as-set using rest of all information. */
1094 for (i
= from
; i
< seg1
->length
; i
++)
1095 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1104 for (i
= from
; i
< seg2
->length
; i
++)
1105 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1112 assegment_normalise(aspath
->segments
);
1113 aspath_str_update(aspath
, false);
1117 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1118 attribute, check the leftmost AS number in the AS_PATH attribute is
1119 or not the peer's AS number. */
1120 bool aspath_firstas_check(struct aspath
*aspath
, as_t asno
)
1122 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1125 if (aspath
->segments
&& (aspath
->segments
->type
== AS_SEQUENCE
)
1126 && (aspath
->segments
->as
[0] == asno
))
1132 unsigned int aspath_get_first_as(struct aspath
*aspath
)
1134 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1137 return aspath
->segments
->as
[0];
1140 unsigned int aspath_get_last_as(struct aspath
*aspath
)
1143 unsigned int last_as
= 0;
1144 const struct assegment
*seg
;
1146 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1149 seg
= aspath
->segments
;
1152 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1153 for (i
= 0; i
< seg
->length
; i
++)
1154 last_as
= seg
->as
[i
];
1161 /* AS path loop check. If aspath contains asno then return >= 1. */
1162 int aspath_loop_check(struct aspath
*aspath
, as_t asno
)
1164 struct assegment
*seg
;
1167 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1170 seg
= aspath
->segments
;
1175 for (i
= 0; i
< seg
->length
; i
++)
1176 if (seg
->as
[i
] == asno
)
1184 /* AS path loop check. If aspath contains asno
1185 * that is a confed id then return >= 1.
1187 int aspath_loop_check_confed(struct aspath
*aspath
, as_t asno
)
1189 struct assegment
*seg
;
1192 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1195 seg
= aspath
->segments
;
1200 for (i
= 0; i
< seg
->length
; i
++)
1201 if (seg
->type
!= AS_CONFED_SEQUENCE
&&
1202 seg
->type
!= AS_CONFED_SET
&& seg
->as
[i
] == asno
)
1211 /* When all of AS path is private AS return 1. */
1212 bool aspath_private_as_check(struct aspath
*aspath
)
1214 struct assegment
*seg
;
1216 if (!(aspath
&& aspath
->segments
))
1219 seg
= aspath
->segments
;
1224 for (i
= 0; i
< seg
->length
; i
++) {
1225 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1233 /* Replace all instances of the target ASN with our own ASN */
1234 struct aspath
*aspath_replace_specific_asn(struct aspath
*aspath
,
1235 as_t target_asn
, as_t our_asn
)
1238 struct assegment
*seg
;
1240 new = aspath_dup(aspath
);
1241 seg
= new->segments
;
1246 for (i
= 0; i
< seg
->length
; i
++) {
1247 if (seg
->as
[i
] == target_asn
)
1248 seg
->as
[i
] = our_asn
;
1253 aspath_str_update(new, false);
1257 /* Replace all ASNs with our own ASN */
1258 struct aspath
*aspath_replace_all_asn(struct aspath
*aspath
, as_t our_asn
)
1261 struct assegment
*seg
;
1263 new = aspath_dup(aspath
);
1264 seg
= new->segments
;
1269 for (i
= 0; i
< seg
->length
; i
++)
1270 seg
->as
[i
] = our_asn
;
1275 aspath_str_update(new, false);
1279 /* Replace all private ASNs with our own ASN */
1280 struct aspath
*aspath_replace_private_asns(struct aspath
*aspath
, as_t asn
,
1284 struct assegment
*seg
;
1286 new = aspath_dup(aspath
);
1287 seg
= new->segments
;
1292 for (i
= 0; i
< seg
->length
; i
++) {
1293 /* Don't replace if public ASN or peer's ASN */
1294 if (BGP_AS_IS_PRIVATE(seg
->as
[i
])
1295 && (seg
->as
[i
] != peer_asn
))
1301 aspath_str_update(new, false);
1305 /* Remove all private ASNs */
1306 struct aspath
*aspath_remove_private_asns(struct aspath
*aspath
, as_t peer_asn
)
1309 struct assegment
*seg
;
1310 struct assegment
*new_seg
;
1311 struct assegment
*last_new_seg
;
1317 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
1321 last_new_seg
= NULL
;
1322 seg
= aspath
->segments
;
1326 for (i
= 0; i
< seg
->length
; i
++) {
1328 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1330 /* ASN matches peer's.
1331 * Don't double-count if peer_asn is public.
1333 else if (seg
->as
[i
] == peer_asn
)
1337 // The entire segment is public so copy it
1338 if (public == seg
->length
)
1339 new_seg
= assegment_dup(seg
);
1341 // The segment is a mix of public and private ASNs. Copy as many
1343 // there are public ASNs then come back and fill in only the
1346 /* length needs to account for all retained ASNs
1347 * (public or peer_asn), not just public
1349 new_seg
= assegment_new(seg
->type
, (public + peer
));
1351 for (i
= 0; i
< seg
->length
; i
++) {
1352 // keep ASN if public or matches peer's ASN
1353 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])
1354 || (seg
->as
[i
] == peer_asn
)) {
1355 new_seg
->as
[j
] = seg
->as
[i
];
1361 // This is the first segment so set the aspath segments pointer
1364 new->segments
= new_seg
;
1366 last_new_seg
->next
= new_seg
;
1368 last_new_seg
= new_seg
;
1372 aspath_str_update(new, false);
1376 /* AS path confed check. If aspath contains confed set or sequence then return
1378 bool aspath_confed_check(struct aspath
*aspath
)
1380 struct assegment
*seg
;
1382 if (!(aspath
&& aspath
->segments
))
1385 seg
= aspath
->segments
;
1388 if (seg
->type
== AS_CONFED_SET
1389 || seg
->type
== AS_CONFED_SEQUENCE
)
1396 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1397 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1398 bool aspath_left_confed_check(struct aspath
*aspath
)
1401 if (!(aspath
&& aspath
->segments
))
1404 if ((aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1405 || (aspath
->segments
->type
== AS_CONFED_SET
))
1411 /* Merge as1 to as2. as2 should be uninterned aspath. */
1412 static struct aspath
*aspath_merge(struct aspath
*as1
, struct aspath
*as2
)
1414 struct assegment
*last
, *new;
1419 last
= new = assegment_dup_all(as1
->segments
);
1421 /* find the last valid segment */
1422 while (last
&& last
->next
)
1426 last
->next
= as2
->segments
;
1427 as2
->segments
= new;
1428 aspath_str_update(as2
, false);
1432 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1433 struct aspath
*aspath_prepend(struct aspath
*as1
, struct aspath
*as2
)
1435 struct assegment
*as1segtail
;
1436 struct assegment
*as2segtail
;
1437 struct assegment
*as2seghead
;
1442 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1443 if (as2
->segments
== NULL
) {
1444 as2
->segments
= assegment_dup_all(as1
->segments
);
1445 aspath_str_update(as2
, false);
1449 /* If as1 is empty AS, no prepending to do. */
1450 if (as1
->segments
== NULL
)
1453 /* find the tail as1's segment chain. */
1454 as1segtail
= as1
->segments
;
1455 while (as1segtail
&& as1segtail
->next
)
1456 as1segtail
= as1segtail
->next
;
1458 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1459 if (as1segtail
->type
== AS_SEQUENCE
1460 && as2
->segments
->type
== AS_CONFED_SEQUENCE
)
1461 as2
= aspath_delete_confed_seq(as2
);
1463 if (!as2
->segments
) {
1464 as2
->segments
= assegment_dup_all(as1
->segments
);
1465 aspath_str_update(as2
, false);
1469 /* Compare last segment type of as1 and first segment type of as2. */
1470 if (as1segtail
->type
!= as2
->segments
->type
)
1471 return aspath_merge(as1
, as2
);
1473 if (as1segtail
->type
== AS_SEQUENCE
) {
1474 /* We have two chains of segments, as1->segments and seg2,
1475 * and we have to attach them together, merging the attaching
1476 * segments together into one.
1478 * 1. dupe as1->segments onto head of as2
1479 * 2. merge seg2's asns onto last segment of this new chain
1480 * 3. attach chain after seg2
1484 as2seghead
= as2
->segments
;
1486 /* dupe as1 onto as2's head */
1487 as2segtail
= as2
->segments
= assegment_dup_all(as1
->segments
);
1489 /* refind the tail of as2 */
1490 while (as2segtail
&& as2segtail
->next
)
1491 as2segtail
= as2segtail
->next
;
1493 /* merge the old head, seg2, into tail, seg1 */
1494 assegment_append_asns(as2segtail
, as2seghead
->as
,
1495 as2seghead
->length
);
1498 * bypass the merged seg2, and attach any chain after it
1499 * to chain descending from as2's head
1502 as2segtail
->next
= as2seghead
->next
;
1504 /* as2->segments is now referenceless and useless */
1505 assegment_free(as2seghead
);
1507 /* we've now prepended as1's segment chain to as2, merging
1508 * the inbetween AS_SEQUENCE of seg2 in the process
1510 aspath_str_update(as2
, false);
1513 /* AS_SET merge code is needed at here. */
1514 return aspath_merge(as1
, as2
);
1516 /* XXX: Ermmm, what if as1 has multiple segments?? */
1521 /* Iterate over AS_PATH segments and wipe all occurrences of the
1522 * listed AS numbers. Hence some segments may lose some or even
1523 * all data on the way, the operation is implemented as a smarter
1524 * version of aspath_dup(), which allocates memory to hold the new
1525 * data, not the original. The new AS path is returned.
1527 struct aspath
*aspath_filter_exclude(struct aspath
*source
,
1528 struct aspath
*exclude_list
)
1530 struct assegment
*srcseg
, *exclseg
, *lastseg
;
1531 struct aspath
*newpath
;
1533 newpath
= aspath_new(source
->asnotation
);
1536 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
) {
1537 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1538 struct assegment
*newseg
;
1540 /* Find out, how much ASns are we going to pick from this
1542 * We can't perform filtering right inline, because the size of
1543 * the new segment isn't known at the moment yet.
1545 for (i
= 0; i
< srcseg
->length
; i
++) {
1547 for (exclseg
= exclude_list
->segments
;
1548 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1549 for (y
= 0; y
< exclseg
->length
; y
++)
1550 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1552 // There's no sense in testing
1553 // the rest of exclusion list,
1560 /* newlen is now the number of ASns to copy */
1564 /* Actual copying. Allocate memory and iterate once more,
1565 * performing filtering. */
1566 newseg
= assegment_new(srcseg
->type
, newlen
);
1567 for (i
= 0; i
< srcseg
->length
; i
++) {
1569 for (exclseg
= exclude_list
->segments
;
1570 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1571 for (y
= 0; y
< exclseg
->length
; y
++)
1572 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1578 newseg
->as
[done
++] = srcseg
->as
[i
];
1580 /* At his point newlen must be equal to done, and both must be
1582 * the filtered segment to the gross result. */
1584 newpath
->segments
= newseg
;
1586 lastseg
->next
= newseg
;
1589 aspath_str_update(newpath
, false);
1590 /* We are happy returning even an empty AS_PATH, because the
1592 * might expect this very behaviour. There's a mean to avoid this, if
1594 * by having a match rule against certain AS_PATH regexps in the
1597 aspath_free(source
);
1601 /* Add specified AS to the leftmost of aspath. */
1602 static struct aspath
*aspath_add_asns(struct aspath
*aspath
, as_t asno
,
1603 uint8_t type
, unsigned num
)
1605 struct assegment
*assegment
= aspath
->segments
;
1608 if (assegment
&& assegment
->type
== type
) {
1609 /* extend existing segment */
1611 assegment_prepend_asns(aspath
->segments
, asno
, num
);
1613 /* prepend with new segment */
1614 struct assegment
*newsegment
= assegment_new(type
, num
);
1615 for (i
= 0; i
< num
; i
++)
1616 newsegment
->as
[i
] = asno
;
1618 /* insert potentially replacing empty segment */
1619 if (assegment
&& assegment
->length
== 0) {
1620 newsegment
->next
= assegment
->next
;
1621 assegment_free(assegment
);
1623 newsegment
->next
= assegment
;
1624 aspath
->segments
= newsegment
;
1627 aspath_str_update(aspath
, false);
1631 /* Add specified AS to the leftmost of aspath num times. */
1632 struct aspath
*aspath_add_seq_n(struct aspath
*aspath
, as_t asno
, unsigned num
)
1634 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, num
);
1637 /* Add specified AS to the leftmost of aspath. */
1638 struct aspath
*aspath_add_seq(struct aspath
*aspath
, as_t asno
)
1640 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, 1);
1643 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1644 as2's leftmost AS is same return 1. */
1645 bool aspath_cmp_left(const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1647 const struct assegment
*seg1
;
1648 const struct assegment
*seg2
;
1650 if (!(aspath1
&& aspath2
))
1653 seg1
= aspath1
->segments
;
1654 seg2
= aspath2
->segments
;
1656 /* If both paths are originated in this AS then we do want to compare
1661 /* find first non-confed segments for each */
1662 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1663 || (seg1
->type
== AS_CONFED_SET
)))
1666 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1667 || (seg2
->type
== AS_CONFED_SET
)))
1671 if (!(seg1
&& seg2
&& (seg1
->type
== AS_SEQUENCE
)
1672 && (seg2
->type
== AS_SEQUENCE
)))
1675 if (seg1
->as
[0] == seg2
->as
[0])
1681 /* Truncate an aspath after a number of hops, and put the hops remaining
1682 * at the front of another aspath. Needed for AS4 compat.
1684 * Returned aspath is a /new/ aspath, which should either by free'd or
1685 * interned by the caller, as desired.
1687 struct aspath
*aspath_reconcile_as4(struct aspath
*aspath
,
1688 struct aspath
*as4path
)
1690 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1691 struct aspath
*newpath
= NULL
, *mergedpath
;
1692 int hops
, cpasns
= 0;
1694 if (!aspath
|| !as4path
)
1697 seg
= aspath
->segments
;
1699 /* CONFEDs should get reconciled too.. */
1700 hops
= (aspath_count_hops(aspath
) + aspath_count_confeds(aspath
))
1701 - aspath_count_hops(as4path
);
1704 if (BGP_DEBUG(as4
, AS4
))
1706 EC_BGP_ASPATH_FEWER_HOPS
,
1707 "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1708 /* Something's gone wrong. The RFC says we should now ignore
1710 * which is daft behaviour - it contains vital loop-detection
1711 * information which must have been removed from AS_PATH.
1713 hops
= aspath_count_hops(aspath
);
1717 newpath
= aspath_dup(as4path
);
1718 aspath_str_update(newpath
, false);
1722 if (BGP_DEBUG(as4
, AS4
))
1724 "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1725 aspath
->str
, as4path
->str
);
1727 while (seg
&& hops
> 0) {
1728 switch (seg
->type
) {
1732 cpasns
= seg
->length
;
1734 case AS_CONFED_SEQUENCE
:
1735 /* Should never split a confed-sequence, if hop-count
1736 * suggests we must then something's gone wrong
1739 * Most important goal is to preserve AS_PATHs prime
1741 * as loop-detector, so we fudge the numbers so that the
1743 * confed-sequence is merged in.
1745 if (hops
< seg
->length
) {
1746 if (BGP_DEBUG(as4
, AS4
))
1748 "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls across 2/4 ASN boundary somewhere, broken..");
1753 cpasns
= MIN(seg
->length
, hops
);
1754 hops
-= seg
->length
;
1757 assert(cpasns
<= seg
->length
);
1759 newseg
= assegment_new(seg
->type
, 0);
1760 newseg
= assegment_append_asns(newseg
, seg
->as
, cpasns
);
1763 newpath
= aspath_new(aspath
->asnotation
);
1764 newpath
->segments
= newseg
;
1766 prevseg
->next
= newseg
;
1772 /* We may be able to join some segments here, and we must
1773 * do this because... we want normalised aspaths in out hash
1774 * and we do not want to stumble in aspath_put.
1776 mergedpath
= aspath_merge(newpath
, aspath_dup(as4path
));
1777 aspath_free(newpath
);
1778 mergedpath
->segments
= assegment_normalise(mergedpath
->segments
);
1779 aspath_str_update(mergedpath
, false);
1781 if (BGP_DEBUG(as4
, AS4
))
1782 zlog_debug("[AS4] result of synthesizing is %s",
1788 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1789 as2's leftmost AS is same return 1. (confederation as-path
1791 bool aspath_cmp_left_confed(const struct aspath
*aspath1
,
1792 const struct aspath
*aspath2
)
1794 if (!(aspath1
&& aspath2
))
1797 if (!(aspath1
->segments
&& aspath2
->segments
))
1800 if ((aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1801 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
))
1804 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1810 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1811 * RFC 5065 section 4.1.c.1
1813 * 1) if any path segments of the AS_PATH are of the type
1814 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1815 * removed from the AS_PATH attribute, leaving the sanitized
1816 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1818 struct aspath
*aspath_delete_confed_seq(struct aspath
*aspath
)
1820 struct assegment
*seg
, *prev
, *next
;
1821 char removed_confed_segment
;
1823 if (!(aspath
&& aspath
->segments
))
1826 seg
= aspath
->segments
;
1827 removed_confed_segment
= 0;
1834 if (seg
->type
== AS_CONFED_SEQUENCE
1835 || seg
->type
== AS_CONFED_SET
) {
1836 /* This is the first segment in the aspath */
1837 if (aspath
->segments
== seg
)
1838 aspath
->segments
= seg
->next
;
1840 prev
->next
= seg
->next
;
1842 assegment_free(seg
);
1843 removed_confed_segment
= 1;
1850 if (removed_confed_segment
)
1851 aspath_str_update(aspath
, false);
1856 /* Add new AS number to the leftmost part of the aspath as
1857 AS_CONFED_SEQUENCE. */
1858 struct aspath
*aspath_add_confed_seq(struct aspath
*aspath
, as_t asno
)
1860 return aspath_add_asns(aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1863 /* Add new as value to as path structure. */
1864 static void aspath_as_add(struct aspath
*as
, as_t asno
)
1866 struct assegment
*seg
= as
->segments
;
1871 /* Last segment search procedure. */
1875 assegment_append_asns(seg
, &asno
, 1);
1878 /* Add new as segment to the as path. */
1879 static void aspath_segment_add(struct aspath
*as
, int type
)
1881 struct assegment
*seg
= as
->segments
;
1882 struct assegment
*new = assegment_new(type
, 0);
1892 struct aspath
*aspath_empty(enum asnotation_mode asnotation
)
1894 return aspath_parse(NULL
, 0, 1, asnotation
); /* 32Bit ;-) */
1897 struct aspath
*aspath_empty_get(void)
1899 struct aspath
*aspath
;
1901 aspath
= aspath_new(bgp_get_asnotation(NULL
));
1902 aspath_make_str_count(aspath
, false);
1906 unsigned long aspath_count(void)
1908 return ashash
->count
;
1912 Theoretically, one as path can have:
1914 One BGP packet size should be less than 4096.
1915 One BGP attribute size should be less than 4096 - BGP header size.
1916 One BGP aspath size should be less than 4096 - BGP header size -
1917 BGP mandantry attribute size.
1920 /* AS path string lexical token enum. */
1925 as_token_confed_seq_start
,
1926 as_token_confed_seq_end
,
1927 as_token_confed_set_start
,
1928 as_token_confed_set_end
,
1932 /* Return next token and point for string parse. */
1933 static const char *aspath_gettoken(const char *buf
, enum as_token
*token
,
1934 unsigned long *asno
)
1936 const char *p
= buf
;
1940 /* Skip separators (space for sequences, ',' for sets). */
1941 while (isspace((unsigned char)*p
) || *p
== ',')
1944 /* Check the end of the string and type specify characters
1950 *token
= as_token_set_start
;
1954 *token
= as_token_set_end
;
1958 *token
= as_token_confed_seq_start
;
1962 *token
= as_token_confed_seq_end
;
1966 *token
= as_token_confed_set_start
;
1970 *token
= as_token_confed_set_end
;
1976 p
= asn_str2asn_parse(p
, &asval
, &found
);
1979 *token
= as_token_asval
;
1981 *token
= as_token_unknown
;
1985 struct aspath
*aspath_str2aspath(const char *str
,
1986 enum asnotation_mode asnotation
)
1988 enum as_token token
= as_token_unknown
;
1989 unsigned short as_type
;
1990 unsigned long asno
= 0;
1991 struct aspath
*aspath
;
1994 aspath
= aspath_new(asnotation
);
1996 /* We start default type as AS_SEQUENCE. */
1997 as_type
= AS_SEQUENCE
;
2000 while ((str
= aspath_gettoken(str
, &token
, &asno
)) != NULL
) {
2002 case as_token_asval
:
2004 aspath_segment_add(aspath
, as_type
);
2007 aspath_as_add(aspath
, asno
);
2009 case as_token_set_start
:
2011 aspath_segment_add(aspath
, as_type
);
2014 case as_token_set_end
:
2015 as_type
= AS_SEQUENCE
;
2018 case as_token_confed_seq_start
:
2019 as_type
= AS_CONFED_SEQUENCE
;
2020 aspath_segment_add(aspath
, as_type
);
2023 case as_token_confed_seq_end
:
2024 as_type
= AS_SEQUENCE
;
2027 case as_token_confed_set_start
:
2028 as_type
= AS_CONFED_SET
;
2029 aspath_segment_add(aspath
, as_type
);
2032 case as_token_confed_set_end
:
2033 as_type
= AS_SEQUENCE
;
2036 case as_token_unknown
:
2038 aspath_free(aspath
);
2043 aspath_make_str_count(aspath
, false);
2048 /* Make hash value by raw aspath data. */
2049 unsigned int aspath_key_make(const void *p
)
2051 const struct aspath
*aspath
= p
;
2052 unsigned int key
= 0;
2055 aspath_str_update((struct aspath
*)aspath
, false);
2057 key
= jhash(aspath
->str
, aspath
->str_len
, 2334325);
2062 /* If two aspath have same value then return 1 else return 0 */
2063 bool aspath_cmp(const void *arg1
, const void *arg2
)
2065 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2066 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2068 if (((const struct aspath
*)arg1
)->asnotation
!=
2069 ((const struct aspath
*)arg2
)->asnotation
)
2072 while (seg1
|| seg2
) {
2074 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2076 if (seg1
->type
!= seg2
->type
)
2078 if (seg1
->length
!= seg2
->length
)
2080 for (i
= 0; i
< seg1
->length
; i
++)
2081 if (seg1
->as
[i
] != seg2
->as
[i
])
2089 /* AS path hash initialize. */
2090 void aspath_init(void)
2092 ashash
= hash_create_size(32768, aspath_key_make
, aspath_cmp
,
2096 void aspath_finish(void)
2098 hash_clean_and_free(&ashash
, (void (*)(void *))aspath_free
);
2101 stream_free(snmp_stream
);
2104 /* return and as path value */
2105 const char *aspath_print(struct aspath
*as
)
2107 return (as
? as
->str
: NULL
);
2110 /* Printing functions */
2111 /* Feed the AS_PATH to the vty; the space suffix follows it only in case
2112 * AS_PATH wasn't empty.
2114 void aspath_print_vty(struct vty
*vty
, struct aspath
*as
)
2116 vty_out(vty
, "%s%s", as
->str
, as
->str_len
? " " : "");
2119 static void aspath_show_all_iterator(struct hash_bucket
*bucket
,
2124 as
= (struct aspath
*)bucket
->data
;
2126 vty_out(vty
, "[%p:%u] (%ld) ", (void *)bucket
, bucket
->key
, as
->refcnt
);
2127 vty_out(vty
, "%s\n", as
->str
);
2130 /* Print all aspath and hash information. This function is used from
2131 `show [ip] bgp paths' command. */
2132 void aspath_print_all_vty(struct vty
*vty
)
2134 hash_iterate(ashash
, (void (*)(struct hash_bucket
*,
2135 void *))aspath_show_all_iterator
,
2139 static struct aspath
*bgp_aggr_aspath_lookup(struct bgp_aggregate
*aggregate
,
2140 struct aspath
*aspath
)
2142 return hash_lookup(aggregate
->aspath_hash
, aspath
);
2145 static void *bgp_aggr_aspath_hash_alloc(void *p
)
2147 struct aspath
*ref
= (struct aspath
*)p
;
2148 struct aspath
*aspath
= NULL
;
2150 aspath
= aspath_dup(ref
);
2154 static void bgp_aggr_aspath_prepare(struct hash_bucket
*hb
, void *arg
)
2156 struct aspath
*hb_aspath
= hb
->data
;
2157 struct aspath
**aggr_aspath
= arg
;
2158 struct aspath
*aspath
= NULL
;
2161 aspath
= aspath_aggregate(*aggr_aspath
, hb_aspath
);
2162 aspath_free(*aggr_aspath
);
2163 *aggr_aspath
= aspath
;
2165 *aggr_aspath
= aspath_dup(hb_aspath
);
2169 void bgp_aggr_aspath_remove(void *arg
)
2171 struct aspath
*aspath
= arg
;
2173 aspath_free(aspath
);
2176 void bgp_compute_aggregate_aspath(struct bgp_aggregate
*aggregate
,
2177 struct aspath
*aspath
)
2179 bgp_compute_aggregate_aspath_hash(aggregate
, aspath
);
2181 bgp_compute_aggregate_aspath_val(aggregate
);
2185 void bgp_compute_aggregate_aspath_hash(struct bgp_aggregate
*aggregate
,
2186 struct aspath
*aspath
)
2188 struct aspath
*aggr_aspath
= NULL
;
2190 if ((aggregate
== NULL
) || (aspath
== NULL
))
2193 /* Create hash if not already created.
2195 if (aggregate
->aspath_hash
== NULL
)
2196 aggregate
->aspath_hash
= hash_create(
2197 aspath_key_make
, aspath_cmp
,
2198 "BGP Aggregator as-path hash");
2200 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2201 if (aggr_aspath
== NULL
) {
2202 /* Insert as-path into hash.
2204 aggr_aspath
= hash_get(aggregate
->aspath_hash
, aspath
,
2205 bgp_aggr_aspath_hash_alloc
);
2208 /* Increment reference counter.
2210 aggr_aspath
->refcnt
++;
2213 void bgp_compute_aggregate_aspath_val(struct bgp_aggregate
*aggregate
)
2215 if (aggregate
== NULL
)
2217 /* Re-compute aggregate's as-path.
2219 if (aggregate
->aspath
) {
2220 aspath_free(aggregate
->aspath
);
2221 aggregate
->aspath
= NULL
;
2223 if (aggregate
->aspath_hash
2224 && aggregate
->aspath_hash
->count
) {
2225 hash_iterate(aggregate
->aspath_hash
,
2226 bgp_aggr_aspath_prepare
,
2227 &aggregate
->aspath
);
2231 void bgp_remove_aspath_from_aggregate(struct bgp_aggregate
*aggregate
,
2232 struct aspath
*aspath
)
2234 struct aspath
*aggr_aspath
= NULL
;
2235 struct aspath
*ret_aspath
= NULL
;
2238 || (!aggregate
->aspath_hash
)
2242 /* Look-up the aspath in the hash.
2244 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2246 aggr_aspath
->refcnt
--;
2248 if (aggr_aspath
->refcnt
== 0) {
2249 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2251 aspath_free(ret_aspath
);
2254 /* Remove aggregate's old as-path.
2256 aspath_free(aggregate
->aspath
);
2257 aggregate
->aspath
= NULL
;
2259 bgp_compute_aggregate_aspath_val(aggregate
);
2264 void bgp_remove_aspath_from_aggregate_hash(struct bgp_aggregate
*aggregate
,
2265 struct aspath
*aspath
)
2267 struct aspath
*aggr_aspath
= NULL
;
2268 struct aspath
*ret_aspath
= NULL
;
2271 || (!aggregate
->aspath_hash
)
2275 /* Look-up the aspath in the hash.
2277 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2279 aggr_aspath
->refcnt
--;
2281 if (aggr_aspath
->refcnt
== 0) {
2282 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2284 aspath_free(ret_aspath
);