1 /* AS path management routines.
2 * Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro
3 * Copyright (C) 2005 Sun Microsystems, Inc.
5 * This file is part of GNU Zebra.
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
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.
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
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"
40 /* Attr. Flags and Attr. Type Code. */
41 #define AS_HEADER_SIZE 2
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)
48 /* Maximum protocol segment length value */
49 #define AS_SEGMENT_MAX 255
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.
57 * aspath_put returns bytes written, the only definitive record of
58 * size of wire-format attribute..
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))
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))
68 /* AS segment octet length. */
69 #define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S)
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))
80 /* As segment header - the on-wire representation
81 * NOT the internal representation!
83 struct assegment_header
{
88 /* Hash for aspath. This is the top level structure of AS path. */
89 static struct hash
*ashash
;
91 /* Stream for SNMP. See aspath_snmp_pathseg */
92 static struct stream
*snmp_stream
;
94 /* Callers are required to initialize the memory */
95 static as_t
*assegment_data_new(int num
)
97 return (XMALLOC(MTYPE_AS_SEG_DATA
, ASSEGMENT_DATA_SIZE(num
, 1)));
100 static void assegment_data_free(as_t
*asdata
)
102 XFREE(MTYPE_AS_SEG_DATA
, asdata
);
105 const char *const aspath_segment_type_str
[] = {
106 "as-invalid", "as-set", "as-sequence", "as-confed-sequence",
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
115 static struct assegment
*assegment_new(uint8_t type
, unsigned short length
)
117 struct assegment
*new;
119 new = XCALLOC(MTYPE_AS_SEG
, sizeof(struct assegment
));
122 new->as
= assegment_data_new(length
);
124 new->length
= length
;
130 static void assegment_free(struct assegment
*seg
)
135 assegment_data_free(seg
->as
);
136 memset(seg
, 0xfe, sizeof(struct assegment
));
137 XFREE(MTYPE_AS_SEG
, seg
);
142 /* free entire chain of segments */
143 static void assegment_free_all(struct assegment
*seg
)
145 struct assegment
*prev
;
150 assegment_free(prev
);
154 /* Duplicate just the given assegment and its data */
155 static struct assegment
*assegment_dup(struct assegment
*seg
)
157 struct assegment
*new;
159 new = assegment_new(seg
->type
, seg
->length
);
160 memcpy(new->as
, seg
->as
, ASSEGMENT_DATA_SIZE(new->length
, 1));
165 /* Duplicate entire chain of assegments, return the head */
166 static struct assegment
*assegment_dup_all(struct assegment
*seg
)
168 struct assegment
*new = NULL
;
169 struct assegment
*head
= NULL
;
173 new->next
= assegment_dup(seg
);
176 head
= new = assegment_dup(seg
);
183 /* prepend the as number to given segment, given num of times */
184 static struct assegment
*assegment_prepend_asns(struct assegment
*seg
,
193 if (num
>= AS_SEGMENT_MAX
)
194 return seg
; /* we don't do huge prepends */
196 newas
= assegment_data_new(seg
->length
+ num
);
200 for (i
= 0; i
< num
; i
++)
203 memcpy(newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE(seg
->length
, 1));
204 assegment_data_free(seg
->as
);
211 /* append given array of as numbers to the segment */
212 static struct assegment
*assegment_append_asns(struct assegment
*seg
,
213 as_t
*asnos
, int num
)
220 newas
= XREALLOC(MTYPE_AS_SEG_DATA
, seg
->as
,
221 ASSEGMENT_DATA_SIZE(seg
->length
+ num
, 1));
224 memcpy(seg
->as
+ seg
->length
, asnos
,
225 ASSEGMENT_DATA_SIZE(num
, 1));
230 static int int_cmp(const void *p1
, const void *p2
)
232 const as_t
*as1
= p1
;
233 const as_t
*as2
= p2
;
235 return (*as1
== *as2
) ? 0 : ((*as1
> *as2
) ? 1 : -1);
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..
244 static struct assegment
*assegment_normalise(struct assegment
*head
)
246 struct assegment
*seg
= head
, *pin
;
247 struct assegment
*tmp
;
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 ;)
259 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
) {
263 qsort(seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
266 for (i
= 1; i
< seg
->length
; i
++) {
267 if (seg
->as
[tail
] == seg
->as
[i
])
272 seg
->as
[tail
] = seg
->as
[i
];
274 /* seg->length can be 0.. */
276 seg
->length
= tail
+ 1;
279 /* read ahead from the current, pinned segment while the
281 * are packable/mergeable. Append all following packable
283 * to the segment we have pinned and remove these appended
286 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
)) {
290 /* append the next sequence to the pinned sequence */
291 pin
= assegment_append_asns(pin
, seg
->as
, seg
->length
);
293 /* bypass the next sequence */
294 pin
->next
= seg
->next
;
296 /* get rid of the now referenceless segment */
305 static struct aspath
*aspath_new(enum asnotation_mode asnotation
)
309 as
= XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
310 as
->asnotation
= asnotation
;
314 /* Free AS path structure. */
315 void aspath_free(struct aspath
*aspath
)
319 if (aspath
->segments
)
320 assegment_free_all(aspath
->segments
);
321 XFREE(MTYPE_AS_STR
, aspath
->str
);
324 json_object_free(aspath
->json
);
328 XFREE(MTYPE_AS_PATH
, aspath
);
331 /* Unintern aspath from AS path bucket. */
332 void aspath_unintern(struct aspath
**aspath
)
345 if (asp
->refcnt
== 0) {
346 /* This aspath must exist in aspath hash table. */
347 ret
= hash_release(ashash
, asp
);
354 /* Return the start or end delimiters for a particular Segment type */
355 #define AS_SEG_START 0
357 static char aspath_delimiter_char(uint8_t type
, uint8_t which
)
364 } aspath_delim_char
[] = {{AS_SET
, '{', '}'},
365 {AS_CONFED_SET
, '[', ']'},
366 {AS_CONFED_SEQUENCE
, '(', ')'},
369 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++) {
370 if (aspath_delim_char
[i
].type
== type
) {
371 if (which
== AS_SEG_START
)
372 return aspath_delim_char
[i
].start
;
373 else if (which
== AS_SEG_END
)
374 return aspath_delim_char
[i
].end
;
380 /* countup asns from this segment and index onward */
381 static int assegment_count_asns(struct assegment
*seg
, int from
)
386 count
+= seg
->length
;
388 count
+= (seg
->length
- from
);
396 unsigned int aspath_count_confeds(struct aspath
*aspath
)
399 struct assegment
*seg
= aspath
->segments
;
402 if (seg
->type
== AS_CONFED_SEQUENCE
)
403 count
+= seg
->length
;
404 else if (seg
->type
== AS_CONFED_SET
)
412 unsigned int aspath_count_hops(const struct aspath
*aspath
)
415 struct assegment
*seg
= aspath
->segments
;
418 if (seg
->type
== AS_SEQUENCE
)
419 count
+= seg
->length
;
420 else if (seg
->type
== AS_SET
)
428 /* Check if aspath has AS_SET or AS_CONFED_SET */
429 bool aspath_check_as_sets(struct aspath
*aspath
)
431 struct assegment
*seg
= aspath
->segments
;
434 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
)
441 /* Check if aspath has BGP_AS_ZERO */
442 bool aspath_check_as_zero(struct aspath
*aspath
)
444 struct assegment
*seg
= aspath
->segments
;
448 for (i
= 0; i
< seg
->length
; i
++)
449 if (seg
->as
[i
] == BGP_AS_ZERO
)
457 /* Estimate size aspath /might/ take if encoded into an
460 * This is a quick estimate, not definitive! aspath_put()
461 * may return a different number!!
463 unsigned int aspath_size(struct aspath
*aspath
)
466 struct assegment
*seg
= aspath
->segments
;
469 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
475 /* Return highest public ASN in path */
476 as_t
aspath_highest(struct aspath
*aspath
)
478 struct assegment
*seg
= aspath
->segments
;
483 for (i
= 0; i
< seg
->length
; i
++)
484 if (seg
->as
[i
] > highest
485 && !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
486 highest
= seg
->as
[i
];
492 /* Return the left-most ASN in path */
493 as_t
aspath_leftmost(struct aspath
*aspath
)
495 struct assegment
*seg
= aspath
->segments
;
498 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
499 leftmost
= seg
->as
[0];
504 /* Return 1 if there are any 4-byte ASes in the path */
505 bool aspath_has_as4(struct aspath
*aspath
)
507 struct assegment
*seg
= aspath
->segments
;
511 for (i
= 0; i
< seg
->length
; i
++)
512 if (seg
->as
[i
] > BGP_AS_MAX
)
519 /* Convert aspath structure to string expression. */
520 static void aspath_make_str_count(struct aspath
*as
, bool make_json
)
522 struct assegment
*seg
;
526 json_object
*jaspath_segments
= NULL
;
527 json_object
*jseg
= NULL
;
528 json_object
*jseg_list
= NULL
;
531 as
->json
= json_object_new_object();
532 jaspath_segments
= json_object_new_array();
538 json_object_string_add(as
->json
, "string", "Local");
539 json_object_object_add(as
->json
, "segments",
541 json_object_int_add(as
->json
, "length", 0);
543 as
->str
= XMALLOC(MTYPE_AS_STR
, 1);
551 /* ASN takes 5 to 10 chars plus separator, see below.
552 * If there is one differing segment type, we need an additional
553 * 2 chars for segment delimiters, and the final '\0'.
554 * Hopefully this is large enough to avoid hitting the realloc
555 * code below for most common sequences.
557 * This was changed to 10 after the well-known BGP assertion, which
558 * had hit some parts of the Internet in May of 2009.
559 * plain format : '4294967295 ' : 10 + 1
560 * astod format : '65535.65535 ': 11 + 1
562 #define ASN_STR_LEN (11 + 1)
563 str_size
= MAX(assegment_count_asns(seg
, 0) * ASN_STR_LEN
+ 2 + 1,
564 ASPATH_STR_DEFAULT_LEN
);
565 str_buf
= XMALLOC(MTYPE_AS_STR
, str_size
);
571 /* Check AS type validity. Set separator for segment */
578 case AS_CONFED_SEQUENCE
:
582 XFREE(MTYPE_AS_STR
, str_buf
);
585 json_object_free(as
->json
);
591 /* We might need to increase str_buf, particularly if path has
592 * differing segments types, our initial guesstimate above will
593 * have been wrong. Need 11 chars for ASN, a separator each and
594 * potentially two segment delimiters, plus a space between each
595 * segment and trailing zero.
597 * This definitely didn't work with the value of 5 bytes and
600 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
601 if ((len
+ SEGMENT_STR_LEN(seg
)) > str_size
) {
602 str_size
= len
+ SEGMENT_STR_LEN(seg
);
603 str_buf
= XREALLOC(MTYPE_AS_STR
, str_buf
, str_size
);
606 #undef SEGMENT_STR_LEN
608 if (seg
->type
!= AS_SEQUENCE
)
610 str_buf
+ len
, str_size
- len
, "%c",
611 aspath_delimiter_char(seg
->type
, AS_SEG_START
));
614 jseg_list
= json_object_new_array();
616 /* write out the ASNs, with their separators, bar the last one*/
617 for (i
= 0; i
< seg
->length
; i
++) {
619 asn_asn2json_array(jseg_list
, seg
->as
[i
],
621 len
+= snprintfrr(str_buf
+ len
, str_size
- len
,
622 ASN_FORMAT(as
->asnotation
),
625 if (i
< (seg
->length
- 1))
626 len
+= snprintf(str_buf
+ len
, str_size
- len
,
631 jseg
= json_object_new_object();
632 json_object_string_add(
634 aspath_segment_type_str
[seg
->type
]);
635 json_object_object_add(jseg
, "list", jseg_list
);
636 json_object_array_add(jaspath_segments
, jseg
);
639 if (seg
->type
!= AS_SEQUENCE
)
641 str_buf
+ len
, str_size
- len
, "%c",
642 aspath_delimiter_char(seg
->type
, AS_SEG_END
));
644 len
+= snprintf(str_buf
+ len
, str_size
- len
, " ");
649 assert(len
< str_size
);
656 json_object_string_add(as
->json
, "string", str_buf
);
657 json_object_object_add(as
->json
, "segments", jaspath_segments
);
658 json_object_int_add(as
->json
, "length", aspath_count_hops(as
));
664 void aspath_str_update(struct aspath
*as
, bool make_json
)
666 XFREE(MTYPE_AS_STR
, as
->str
);
669 json_object_free(as
->json
);
673 aspath_make_str_count(as
, make_json
);
676 /* Intern allocated AS path. */
677 struct aspath
*aspath_intern(struct aspath
*aspath
)
681 /* Assert this AS path structure is not interned and has the string
682 representation built. */
683 assert(aspath
->refcnt
== 0);
686 /* Check AS path hash. */
687 find
= hash_get(ashash
, aspath
, hash_alloc_intern
);
696 /* Duplicate aspath structure. Created same aspath structure but
697 reference count and AS path string is cleared. */
698 struct aspath
*aspath_dup(struct aspath
*aspath
)
700 unsigned short buflen
= aspath
->str_len
+ 1;
703 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
706 if (aspath
->segments
)
707 new->segments
= assegment_dup_all(aspath
->segments
);
712 new->str
= XMALLOC(MTYPE_AS_STR
, buflen
);
713 new->str_len
= aspath
->str_len
;
714 new->asnotation
= aspath
->asnotation
;
716 /* copy the string data */
717 if (aspath
->str_len
> 0)
718 memcpy(new->str
, aspath
->str
, buflen
);
725 static void *aspath_hash_alloc(void *arg
)
727 const struct aspath
*aspath
= arg
;
730 /* Malformed AS path value. */
733 /* New aspath structure is needed. */
734 new = XMALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
736 /* Reuse segments and string representation */
738 new->segments
= aspath
->segments
;
739 new->str
= aspath
->str
;
740 new->str_len
= aspath
->str_len
;
741 new->json
= aspath
->json
;
742 new->asnotation
= aspath
->asnotation
;
747 /* parse as-segment byte stream in struct assegment */
748 static int assegments_parse(struct stream
*s
, size_t length
,
749 struct assegment
**result
, int use32bit
)
751 struct assegment_header segh
;
752 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
755 /* empty aspath (ie iBGP or somesuch) */
759 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
761 "[AS4SEG] Parse aspath segment: got total byte length %lu",
762 (unsigned long)length
);
764 if ((STREAM_READABLE(s
) < length
)
765 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
766 || (length
% AS16_VALUE_SIZE
))
769 while (bytes
< length
) {
773 if ((length
- bytes
) <= AS_HEADER_SIZE
) {
775 assegment_free_all(head
);
779 /* softly softly, get the header first on its own */
780 segh
.type
= stream_getc(s
);
781 segh
.length
= stream_getc(s
);
783 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
785 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
787 "[AS4SEG] Parse aspath segment: got type %d, length %d",
788 segh
.type
, segh
.length
);
791 if (((bytes
+ seg_size
) > length
)
792 /* 1771bis 4.3b: seg length contains one or more */
793 || (segh
.length
== 0)
794 /* Paranoia in case someone changes type of segment length.
795 * Shift both values by 0x10 to make the comparison operate
796 * on more, than 8 bits (otherwise it's a warning, bug
799 || ((sizeof(segh
.length
) > 1)
800 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
))) {
802 assegment_free_all(head
);
809 case AS_CONFED_SEQUENCE
:
814 assegment_free_all(head
);
818 /* now its safe to trust lengths */
819 seg
= assegment_new(segh
.type
, segh
.length
);
823 else /* it's the first segment */
826 for (i
= 0; i
< segh
.length
; i
++)
828 (use32bit
) ? stream_getl(s
) : stream_getw(s
);
832 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
834 "[AS4SEG] Parse aspath segment: Bytes now: %lu",
835 (unsigned long)bytes
);
840 *result
= assegment_normalise(head
);
844 /* AS path parse function. pnt is a pointer to byte stream and length
845 is length of byte stream. If there is same AS path in the the AS
846 path hash then return it else make new AS path structure.
848 On error NULL is returned.
850 struct aspath
*aspath_parse(struct stream
*s
, size_t length
, int use32bit
,
851 enum asnotation_mode asnotation
)
856 /* If length is odd it's malformed AS path. */
857 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
858 * otherwise its malformed when length is larger than 2 and (length-2)
859 * is not dividable by 4.
860 * But... this time we're lazy
862 if (length
% AS16_VALUE_SIZE
)
865 memset(&as
, 0, sizeof(as
));
866 as
.asnotation
= asnotation
;
867 if (assegments_parse(s
, length
, &as
.segments
, use32bit
) < 0)
870 /* If already same aspath exist then return it. */
871 find
= hash_get(ashash
, &as
, aspath_hash_alloc
);
873 /* if the aspath was already hashed free temporary memory. */
875 assegment_free_all(as
.segments
);
876 /* aspath_key_make() always updates the string */
877 XFREE(MTYPE_AS_STR
, as
.str
);
879 json_object_free(as
.json
);
889 static void assegment_data_put(struct stream
*s
, as_t
*as
, int num
,
893 assert(num
<= AS_SEGMENT_MAX
);
895 for (i
= 0; i
< num
; i
++)
897 stream_putl(s
, as
[i
]);
899 if (as
[i
] <= BGP_AS_MAX
)
900 stream_putw(s
, as
[i
]);
902 stream_putw(s
, BGP_AS_TRANS
);
906 static size_t assegment_header_put(struct stream
*s
, uint8_t type
, int length
)
909 assert(length
<= AS_SEGMENT_MAX
);
910 stream_putc(s
, type
);
911 lenp
= stream_get_endp(s
);
912 stream_putc(s
, length
);
916 /* write aspath data to stream */
917 size_t aspath_put(struct stream
*s
, struct aspath
*as
, int use32bit
)
919 struct assegment
*seg
= as
->segments
;
922 if (!seg
|| seg
->length
== 0)
926 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
927 * At the moment, we would write out a partial aspath, and our
929 * will complain and drop the session :-/
931 * The general assumption here is that many things tested will
932 * never happen. And, in real live, up to now, they have not.
934 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
) <= STREAM_WRITEABLE(s
))) {
935 struct assegment
*next
= seg
->next
;
940 /* Overlength segments have to be split up */
941 while ((seg
->length
- written
) > AS_SEGMENT_MAX
) {
942 assegment_header_put(s
, seg
->type
, AS_SEGMENT_MAX
);
943 assegment_data_put(s
, (seg
->as
+ written
),
944 AS_SEGMENT_MAX
, use32bit
);
945 written
+= AS_SEGMENT_MAX
;
946 bytes
+= ASSEGMENT_SIZE(AS_SEGMENT_MAX
, use32bit
);
949 /* write the final segment, probably is also the first
951 lenp
= assegment_header_put(s
, seg
->type
,
952 seg
->length
- written
);
953 assegment_data_put(s
, (seg
->as
+ written
),
954 seg
->length
- written
, use32bit
);
956 /* Sequence-type segments can be 'packed' together
957 * Case of a segment which was overlength and split up
958 * will be missed here, but that doesn't matter.
960 while (next
&& ASSEGMENTS_PACKABLE(seg
, next
)) {
961 /* NB: We should never normally get here given
963 * normalise aspath data when parse them.
965 * safe than sorry. We potentially could call
966 * assegment_normalise here instead, but it's
968 * easier to do it on the fly here rather than
970 * the segment list twice every time we write
975 /* Next segment's data can fit in this one */
976 assegment_data_put(s
, next
->as
, next
->length
, use32bit
);
978 /* update the length of the segment header */
979 stream_putc_at(s
, lenp
,
980 seg
->length
- written
+ next
->length
);
981 asns_packed
+= next
->length
;
986 bytes
+= ASSEGMENT_SIZE(seg
->length
- written
+ asns_packed
,
993 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
994 * We have no way to manage the storage, so we use a static stream
995 * wrapper around aspath_put.
997 uint8_t *aspath_snmp_pathseg(struct aspath
*as
, size_t *varlen
)
999 #define SNMP_PATHSEG_MAX 1024
1002 snmp_stream
= stream_new(SNMP_PATHSEG_MAX
);
1004 stream_reset(snmp_stream
);
1010 aspath_put(snmp_stream
, as
, 0); /* use 16 bit for now here */
1012 *varlen
= stream_get_endp(snmp_stream
);
1013 return stream_pnt(snmp_stream
);
1016 static struct assegment
*aspath_aggregate_as_set_add(struct aspath
*aspath
,
1017 struct assegment
*asset
,
1022 /* If this is first AS set member, create new as-set segment. */
1023 if (asset
== NULL
) {
1024 asset
= assegment_new(AS_SET
, 1);
1025 if (!aspath
->segments
)
1026 aspath
->segments
= asset
;
1028 struct assegment
*seg
= aspath
->segments
;
1033 asset
->type
= AS_SET
;
1037 /* Check this AS value already exists or not. */
1038 for (i
= 0; i
< asset
->length
; i
++)
1039 if (asset
->as
[i
] == as
)
1043 asset
->as
= XREALLOC(MTYPE_AS_SEG_DATA
, asset
->as
,
1044 asset
->length
* AS_VALUE_SIZE
);
1045 asset
->as
[asset
->length
- 1] = as
;
1052 /* Modify as1 using as2 for aggregation. */
1053 struct aspath
*aspath_aggregate(struct aspath
*as1
, struct aspath
*as2
)
1059 struct assegment
*seg1
= as1
->segments
;
1060 struct assegment
*seg2
= as2
->segments
;
1061 struct aspath
*aspath
= NULL
;
1062 struct assegment
*asset
= NULL
;
1063 struct assegment
*prevseg
= NULL
;
1065 /* First of all check common leading sequence. */
1066 while (seg1
&& seg2
) {
1067 /* Check segment type. */
1068 if (seg1
->type
!= seg2
->type
)
1071 /* Minimum segment length. */
1072 minlen
= MIN(seg1
->length
, seg2
->length
);
1074 for (match
= 0; match
< minlen
; match
++)
1075 if (seg1
->as
[match
] != seg2
->as
[match
])
1079 struct assegment
*seg
= assegment_new(seg1
->type
, 0);
1081 seg
= assegment_append_asns(seg
, seg1
->as
, match
);
1084 aspath
= aspath_new(as1
->asnotation
);
1085 aspath
->segments
= seg
;
1087 prevseg
->next
= seg
;
1092 if (match
!= minlen
|| match
!= seg1
->length
1093 || seg1
->length
!= seg2
->length
)
1095 /* We are moving on to the next segment to reset match */
1104 aspath
= aspath_new(as1
->asnotation
);
1106 /* Make as-set using rest of all information. */
1109 for (i
= from
; i
< seg1
->length
; i
++)
1110 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1119 for (i
= from
; i
< seg2
->length
; i
++)
1120 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1127 assegment_normalise(aspath
->segments
);
1128 aspath_str_update(aspath
, false);
1132 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1133 attribute, check the leftmost AS number in the AS_PATH attribute is
1134 or not the peer's AS number. */
1135 bool aspath_firstas_check(struct aspath
*aspath
, as_t asno
)
1137 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1140 if (aspath
->segments
&& (aspath
->segments
->type
== AS_SEQUENCE
)
1141 && (aspath
->segments
->as
[0] == asno
))
1147 unsigned int aspath_get_first_as(struct aspath
*aspath
)
1149 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1152 return aspath
->segments
->as
[0];
1155 unsigned int aspath_get_last_as(struct aspath
*aspath
)
1158 unsigned int last_as
= 0;
1159 const struct assegment
*seg
;
1161 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1164 seg
= aspath
->segments
;
1167 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1168 for (i
= 0; i
< seg
->length
; i
++)
1169 last_as
= seg
->as
[i
];
1176 /* AS path loop check. If aspath contains asno then return >= 1. */
1177 int aspath_loop_check(struct aspath
*aspath
, as_t asno
)
1179 struct assegment
*seg
;
1182 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1185 seg
= aspath
->segments
;
1190 for (i
= 0; i
< seg
->length
; i
++)
1191 if (seg
->as
[i
] == asno
)
1199 /* AS path loop check. If aspath contains asno
1200 * that is a confed id then return >= 1.
1202 int aspath_loop_check_confed(struct aspath
*aspath
, as_t asno
)
1204 struct assegment
*seg
;
1207 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1210 seg
= aspath
->segments
;
1215 for (i
= 0; i
< seg
->length
; i
++)
1216 if (seg
->type
!= AS_CONFED_SEQUENCE
&&
1217 seg
->type
!= AS_CONFED_SET
&& seg
->as
[i
] == asno
)
1226 /* When all of AS path is private AS return 1. */
1227 bool aspath_private_as_check(struct aspath
*aspath
)
1229 struct assegment
*seg
;
1231 if (!(aspath
&& aspath
->segments
))
1234 seg
= aspath
->segments
;
1239 for (i
= 0; i
< seg
->length
; i
++) {
1240 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1248 /* Replace all instances of the target ASN with our own ASN */
1249 struct aspath
*aspath_replace_specific_asn(struct aspath
*aspath
,
1250 as_t target_asn
, as_t our_asn
)
1253 struct assegment
*seg
;
1255 new = aspath_dup(aspath
);
1256 seg
= new->segments
;
1261 for (i
= 0; i
< seg
->length
; i
++) {
1262 if (seg
->as
[i
] == target_asn
)
1263 seg
->as
[i
] = our_asn
;
1268 aspath_str_update(new, false);
1272 /* Replace all ASNs with our own ASN */
1273 struct aspath
*aspath_replace_all_asn(struct aspath
*aspath
, as_t our_asn
)
1276 struct assegment
*seg
;
1278 new = aspath_dup(aspath
);
1279 seg
= new->segments
;
1284 for (i
= 0; i
< seg
->length
; i
++)
1285 seg
->as
[i
] = our_asn
;
1290 aspath_str_update(new, false);
1294 /* Replace all private ASNs with our own ASN */
1295 struct aspath
*aspath_replace_private_asns(struct aspath
*aspath
, as_t asn
,
1299 struct assegment
*seg
;
1301 new = aspath_dup(aspath
);
1302 seg
= new->segments
;
1307 for (i
= 0; i
< seg
->length
; i
++) {
1308 /* Don't replace if public ASN or peer's ASN */
1309 if (BGP_AS_IS_PRIVATE(seg
->as
[i
])
1310 && (seg
->as
[i
] != peer_asn
))
1316 aspath_str_update(new, false);
1320 /* Remove all private ASNs */
1321 struct aspath
*aspath_remove_private_asns(struct aspath
*aspath
, as_t peer_asn
)
1324 struct assegment
*seg
;
1325 struct assegment
*new_seg
;
1326 struct assegment
*last_new_seg
;
1332 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
1336 last_new_seg
= NULL
;
1337 seg
= aspath
->segments
;
1341 for (i
= 0; i
< seg
->length
; i
++) {
1343 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1345 /* ASN matches peer's.
1346 * Don't double-count if peer_asn is public.
1348 else if (seg
->as
[i
] == peer_asn
)
1352 // The entire segment is public so copy it
1353 if (public == seg
->length
)
1354 new_seg
= assegment_dup(seg
);
1356 // The segment is a mix of public and private ASNs. Copy as many
1358 // there are public ASNs then come back and fill in only the
1361 /* length needs to account for all retained ASNs
1362 * (public or peer_asn), not just public
1364 new_seg
= assegment_new(seg
->type
, (public + peer
));
1366 for (i
= 0; i
< seg
->length
; i
++) {
1367 // keep ASN if public or matches peer's ASN
1368 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])
1369 || (seg
->as
[i
] == peer_asn
)) {
1370 new_seg
->as
[j
] = seg
->as
[i
];
1376 // This is the first segment so set the aspath segments pointer
1379 new->segments
= new_seg
;
1381 last_new_seg
->next
= new_seg
;
1383 last_new_seg
= new_seg
;
1387 aspath_str_update(new, false);
1391 /* AS path confed check. If aspath contains confed set or sequence then return
1393 bool aspath_confed_check(struct aspath
*aspath
)
1395 struct assegment
*seg
;
1397 if (!(aspath
&& aspath
->segments
))
1400 seg
= aspath
->segments
;
1403 if (seg
->type
== AS_CONFED_SET
1404 || seg
->type
== AS_CONFED_SEQUENCE
)
1411 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1412 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1413 bool aspath_left_confed_check(struct aspath
*aspath
)
1416 if (!(aspath
&& aspath
->segments
))
1419 if ((aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1420 || (aspath
->segments
->type
== AS_CONFED_SET
))
1426 /* Merge as1 to as2. as2 should be uninterned aspath. */
1427 static struct aspath
*aspath_merge(struct aspath
*as1
, struct aspath
*as2
)
1429 struct assegment
*last
, *new;
1434 last
= new = assegment_dup_all(as1
->segments
);
1436 /* find the last valid segment */
1437 while (last
&& last
->next
)
1441 last
->next
= as2
->segments
;
1442 as2
->segments
= new;
1443 aspath_str_update(as2
, false);
1447 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1448 struct aspath
*aspath_prepend(struct aspath
*as1
, struct aspath
*as2
)
1450 struct assegment
*as1segtail
;
1451 struct assegment
*as2segtail
;
1452 struct assegment
*as2seghead
;
1457 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1458 if (as2
->segments
== NULL
) {
1459 as2
->segments
= assegment_dup_all(as1
->segments
);
1460 aspath_str_update(as2
, false);
1464 /* If as1 is empty AS, no prepending to do. */
1465 if (as1
->segments
== NULL
)
1468 /* find the tail as1's segment chain. */
1469 as1segtail
= as1
->segments
;
1470 while (as1segtail
&& as1segtail
->next
)
1471 as1segtail
= as1segtail
->next
;
1473 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1474 if (as1segtail
->type
== AS_SEQUENCE
1475 && as2
->segments
->type
== AS_CONFED_SEQUENCE
)
1476 as2
= aspath_delete_confed_seq(as2
);
1478 if (!as2
->segments
) {
1479 as2
->segments
= assegment_dup_all(as1
->segments
);
1480 aspath_str_update(as2
, false);
1484 /* Compare last segment type of as1 and first segment type of as2. */
1485 if (as1segtail
->type
!= as2
->segments
->type
)
1486 return aspath_merge(as1
, as2
);
1488 if (as1segtail
->type
== AS_SEQUENCE
) {
1489 /* We have two chains of segments, as1->segments and seg2,
1490 * and we have to attach them together, merging the attaching
1491 * segments together into one.
1493 * 1. dupe as1->segments onto head of as2
1494 * 2. merge seg2's asns onto last segment of this new chain
1495 * 3. attach chain after seg2
1499 as2seghead
= as2
->segments
;
1501 /* dupe as1 onto as2's head */
1502 as2segtail
= as2
->segments
= assegment_dup_all(as1
->segments
);
1504 /* refind the tail of as2 */
1505 while (as2segtail
&& as2segtail
->next
)
1506 as2segtail
= as2segtail
->next
;
1508 /* merge the old head, seg2, into tail, seg1 */
1509 assegment_append_asns(as2segtail
, as2seghead
->as
,
1510 as2seghead
->length
);
1513 * bypass the merged seg2, and attach any chain after it
1514 * to chain descending from as2's head
1517 as2segtail
->next
= as2seghead
->next
;
1519 /* as2->segments is now referenceless and useless */
1520 assegment_free(as2seghead
);
1522 /* we've now prepended as1's segment chain to as2, merging
1523 * the inbetween AS_SEQUENCE of seg2 in the process
1525 aspath_str_update(as2
, false);
1528 /* AS_SET merge code is needed at here. */
1529 return aspath_merge(as1
, as2
);
1531 /* XXX: Ermmm, what if as1 has multiple segments?? */
1536 /* Iterate over AS_PATH segments and wipe all occurrences of the
1537 * listed AS numbers. Hence some segments may lose some or even
1538 * all data on the way, the operation is implemented as a smarter
1539 * version of aspath_dup(), which allocates memory to hold the new
1540 * data, not the original. The new AS path is returned.
1542 struct aspath
*aspath_filter_exclude(struct aspath
*source
,
1543 struct aspath
*exclude_list
)
1545 struct assegment
*srcseg
, *exclseg
, *lastseg
;
1546 struct aspath
*newpath
;
1548 newpath
= aspath_new(source
->asnotation
);
1551 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
) {
1552 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1553 struct assegment
*newseg
;
1555 /* Find out, how much ASns are we going to pick from this
1557 * We can't perform filtering right inline, because the size of
1558 * the new segment isn't known at the moment yet.
1560 for (i
= 0; i
< srcseg
->length
; i
++) {
1562 for (exclseg
= exclude_list
->segments
;
1563 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1564 for (y
= 0; y
< exclseg
->length
; y
++)
1565 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1567 // There's no sense in testing
1568 // the rest of exclusion list,
1575 /* newlen is now the number of ASns to copy */
1579 /* Actual copying. Allocate memory and iterate once more,
1580 * performing filtering. */
1581 newseg
= assegment_new(srcseg
->type
, newlen
);
1582 for (i
= 0; i
< srcseg
->length
; i
++) {
1584 for (exclseg
= exclude_list
->segments
;
1585 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1586 for (y
= 0; y
< exclseg
->length
; y
++)
1587 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1593 newseg
->as
[done
++] = srcseg
->as
[i
];
1595 /* At his point newlen must be equal to done, and both must be
1597 * the filtered segment to the gross result. */
1599 newpath
->segments
= newseg
;
1601 lastseg
->next
= newseg
;
1604 aspath_str_update(newpath
, false);
1605 /* We are happy returning even an empty AS_PATH, because the
1607 * might expect this very behaviour. There's a mean to avoid this, if
1609 * by having a match rule against certain AS_PATH regexps in the
1612 aspath_free(source
);
1616 /* Add specified AS to the leftmost of aspath. */
1617 static struct aspath
*aspath_add_asns(struct aspath
*aspath
, as_t asno
,
1618 uint8_t type
, unsigned num
)
1620 struct assegment
*assegment
= aspath
->segments
;
1623 if (assegment
&& assegment
->type
== type
) {
1624 /* extend existing segment */
1626 assegment_prepend_asns(aspath
->segments
, asno
, num
);
1628 /* prepend with new segment */
1629 struct assegment
*newsegment
= assegment_new(type
, num
);
1630 for (i
= 0; i
< num
; i
++)
1631 newsegment
->as
[i
] = asno
;
1633 /* insert potentially replacing empty segment */
1634 if (assegment
&& assegment
->length
== 0) {
1635 newsegment
->next
= assegment
->next
;
1636 assegment_free(assegment
);
1638 newsegment
->next
= assegment
;
1639 aspath
->segments
= newsegment
;
1642 aspath_str_update(aspath
, false);
1646 /* Add specified AS to the leftmost of aspath num times. */
1647 struct aspath
*aspath_add_seq_n(struct aspath
*aspath
, as_t asno
, unsigned num
)
1649 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, num
);
1652 /* Add specified AS to the leftmost of aspath. */
1653 struct aspath
*aspath_add_seq(struct aspath
*aspath
, as_t asno
)
1655 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, 1);
1658 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1659 as2's leftmost AS is same return 1. */
1660 bool aspath_cmp_left(const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1662 const struct assegment
*seg1
;
1663 const struct assegment
*seg2
;
1665 if (!(aspath1
&& aspath2
))
1668 seg1
= aspath1
->segments
;
1669 seg2
= aspath2
->segments
;
1671 /* If both paths are originated in this AS then we do want to compare
1676 /* find first non-confed segments for each */
1677 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1678 || (seg1
->type
== AS_CONFED_SET
)))
1681 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1682 || (seg2
->type
== AS_CONFED_SET
)))
1686 if (!(seg1
&& seg2
&& (seg1
->type
== AS_SEQUENCE
)
1687 && (seg2
->type
== AS_SEQUENCE
)))
1690 if (seg1
->as
[0] == seg2
->as
[0])
1696 /* Truncate an aspath after a number of hops, and put the hops remaining
1697 * at the front of another aspath. Needed for AS4 compat.
1699 * Returned aspath is a /new/ aspath, which should either by free'd or
1700 * interned by the caller, as desired.
1702 struct aspath
*aspath_reconcile_as4(struct aspath
*aspath
,
1703 struct aspath
*as4path
)
1705 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1706 struct aspath
*newpath
= NULL
, *mergedpath
;
1707 int hops
, cpasns
= 0;
1709 if (!aspath
|| !as4path
)
1712 seg
= aspath
->segments
;
1714 /* CONFEDs should get reconciled too.. */
1715 hops
= (aspath_count_hops(aspath
) + aspath_count_confeds(aspath
))
1716 - aspath_count_hops(as4path
);
1719 if (BGP_DEBUG(as4
, AS4
))
1721 EC_BGP_ASPATH_FEWER_HOPS
,
1722 "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1723 /* Something's gone wrong. The RFC says we should now ignore
1725 * which is daft behaviour - it contains vital loop-detection
1726 * information which must have been removed from AS_PATH.
1728 hops
= aspath_count_hops(aspath
);
1732 newpath
= aspath_dup(as4path
);
1733 aspath_str_update(newpath
, false);
1737 if (BGP_DEBUG(as4
, AS4
))
1739 "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1740 aspath
->str
, as4path
->str
);
1742 while (seg
&& hops
> 0) {
1743 switch (seg
->type
) {
1747 cpasns
= seg
->length
;
1749 case AS_CONFED_SEQUENCE
:
1750 /* Should never split a confed-sequence, if hop-count
1751 * suggests we must then something's gone wrong
1754 * Most important goal is to preserve AS_PATHs prime
1756 * as loop-detector, so we fudge the numbers so that the
1758 * confed-sequence is merged in.
1760 if (hops
< seg
->length
) {
1761 if (BGP_DEBUG(as4
, AS4
))
1763 "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls across 2/4 ASN boundary somewhere, broken..");
1768 cpasns
= MIN(seg
->length
, hops
);
1769 hops
-= seg
->length
;
1772 assert(cpasns
<= seg
->length
);
1774 newseg
= assegment_new(seg
->type
, 0);
1775 newseg
= assegment_append_asns(newseg
, seg
->as
, cpasns
);
1778 newpath
= aspath_new(aspath
->asnotation
);
1779 newpath
->segments
= newseg
;
1781 prevseg
->next
= newseg
;
1787 /* We may be able to join some segments here, and we must
1788 * do this because... we want normalised aspaths in out hash
1789 * and we do not want to stumble in aspath_put.
1791 mergedpath
= aspath_merge(newpath
, aspath_dup(as4path
));
1792 aspath_free(newpath
);
1793 mergedpath
->segments
= assegment_normalise(mergedpath
->segments
);
1794 aspath_str_update(mergedpath
, false);
1796 if (BGP_DEBUG(as4
, AS4
))
1797 zlog_debug("[AS4] result of synthesizing is %s",
1803 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1804 as2's leftmost AS is same return 1. (confederation as-path
1806 bool aspath_cmp_left_confed(const struct aspath
*aspath1
,
1807 const struct aspath
*aspath2
)
1809 if (!(aspath1
&& aspath2
))
1812 if (!(aspath1
->segments
&& aspath2
->segments
))
1815 if ((aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1816 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
))
1819 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1825 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1826 * RFC 5065 section 4.1.c.1
1828 * 1) if any path segments of the AS_PATH are of the type
1829 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1830 * removed from the AS_PATH attribute, leaving the sanitized
1831 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1833 struct aspath
*aspath_delete_confed_seq(struct aspath
*aspath
)
1835 struct assegment
*seg
, *prev
, *next
;
1836 char removed_confed_segment
;
1838 if (!(aspath
&& aspath
->segments
))
1841 seg
= aspath
->segments
;
1842 removed_confed_segment
= 0;
1849 if (seg
->type
== AS_CONFED_SEQUENCE
1850 || seg
->type
== AS_CONFED_SET
) {
1851 /* This is the first segment in the aspath */
1852 if (aspath
->segments
== seg
)
1853 aspath
->segments
= seg
->next
;
1855 prev
->next
= seg
->next
;
1857 assegment_free(seg
);
1858 removed_confed_segment
= 1;
1865 if (removed_confed_segment
)
1866 aspath_str_update(aspath
, false);
1871 /* Add new AS number to the leftmost part of the aspath as
1872 AS_CONFED_SEQUENCE. */
1873 struct aspath
*aspath_add_confed_seq(struct aspath
*aspath
, as_t asno
)
1875 return aspath_add_asns(aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1878 /* Add new as value to as path structure. */
1879 static void aspath_as_add(struct aspath
*as
, as_t asno
)
1881 struct assegment
*seg
= as
->segments
;
1886 /* Last segment search procedure. */
1890 assegment_append_asns(seg
, &asno
, 1);
1893 /* Add new as segment to the as path. */
1894 static void aspath_segment_add(struct aspath
*as
, int type
)
1896 struct assegment
*seg
= as
->segments
;
1897 struct assegment
*new = assegment_new(type
, 0);
1907 struct aspath
*aspath_empty(enum asnotation_mode asnotation
)
1909 return aspath_parse(NULL
, 0, 1, asnotation
); /* 32Bit ;-) */
1912 struct aspath
*aspath_empty_get(void)
1914 struct aspath
*aspath
;
1916 aspath
= aspath_new(bgp_get_asnotation(NULL
));
1917 aspath_make_str_count(aspath
, false);
1921 unsigned long aspath_count(void)
1923 return ashash
->count
;
1927 Theoretically, one as path can have:
1929 One BGP packet size should be less than 4096.
1930 One BGP attribute size should be less than 4096 - BGP header size.
1931 One BGP aspath size should be less than 4096 - BGP header size -
1932 BGP mandantry attribute size.
1935 /* AS path string lexical token enum. */
1940 as_token_confed_seq_start
,
1941 as_token_confed_seq_end
,
1942 as_token_confed_set_start
,
1943 as_token_confed_set_end
,
1947 /* Return next token and point for string parse. */
1948 static const char *aspath_gettoken(const char *buf
, enum as_token
*token
,
1949 unsigned long *asno
)
1951 const char *p
= buf
;
1955 /* Skip separators (space for sequences, ',' for sets). */
1956 while (isspace((unsigned char)*p
) || *p
== ',')
1959 /* Check the end of the string and type specify characters
1965 *token
= as_token_set_start
;
1969 *token
= as_token_set_end
;
1973 *token
= as_token_confed_seq_start
;
1977 *token
= as_token_confed_seq_end
;
1981 *token
= as_token_confed_set_start
;
1985 *token
= as_token_confed_set_end
;
1991 p
= asn_str2asn_parse(p
, &asval
, &found
);
1994 *token
= as_token_asval
;
1996 *token
= as_token_unknown
;
2000 struct aspath
*aspath_str2aspath(const char *str
,
2001 enum asnotation_mode asnotation
)
2003 enum as_token token
= as_token_unknown
;
2004 unsigned short as_type
;
2005 unsigned long asno
= 0;
2006 struct aspath
*aspath
;
2009 aspath
= aspath_new(asnotation
);
2011 /* We start default type as AS_SEQUENCE. */
2012 as_type
= AS_SEQUENCE
;
2015 while ((str
= aspath_gettoken(str
, &token
, &asno
)) != NULL
) {
2017 case as_token_asval
:
2019 aspath_segment_add(aspath
, as_type
);
2022 aspath_as_add(aspath
, asno
);
2024 case as_token_set_start
:
2026 aspath_segment_add(aspath
, as_type
);
2029 case as_token_set_end
:
2030 as_type
= AS_SEQUENCE
;
2033 case as_token_confed_seq_start
:
2034 as_type
= AS_CONFED_SEQUENCE
;
2035 aspath_segment_add(aspath
, as_type
);
2038 case as_token_confed_seq_end
:
2039 as_type
= AS_SEQUENCE
;
2042 case as_token_confed_set_start
:
2043 as_type
= AS_CONFED_SET
;
2044 aspath_segment_add(aspath
, as_type
);
2047 case as_token_confed_set_end
:
2048 as_type
= AS_SEQUENCE
;
2051 case as_token_unknown
:
2053 aspath_free(aspath
);
2058 aspath_make_str_count(aspath
, false);
2063 /* Make hash value by raw aspath data. */
2064 unsigned int aspath_key_make(const void *p
)
2066 const struct aspath
*aspath
= p
;
2067 unsigned int key
= 0;
2070 aspath_str_update((struct aspath
*)aspath
, false);
2072 key
= jhash(aspath
->str
, aspath
->str_len
, 2334325);
2077 /* If two aspath have same value then return 1 else return 0 */
2078 bool aspath_cmp(const void *arg1
, const void *arg2
)
2080 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2081 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2083 if (((const struct aspath
*)arg1
)->asnotation
!=
2084 ((const struct aspath
*)arg2
)->asnotation
)
2087 while (seg1
|| seg2
) {
2089 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2091 if (seg1
->type
!= seg2
->type
)
2093 if (seg1
->length
!= seg2
->length
)
2095 for (i
= 0; i
< seg1
->length
; i
++)
2096 if (seg1
->as
[i
] != seg2
->as
[i
])
2104 /* AS path hash initialize. */
2105 void aspath_init(void)
2107 ashash
= hash_create_size(32768, aspath_key_make
, aspath_cmp
,
2111 void aspath_finish(void)
2113 hash_clean(ashash
, (void (*)(void *))aspath_free
);
2118 stream_free(snmp_stream
);
2121 /* return and as path value */
2122 const char *aspath_print(struct aspath
*as
)
2124 return (as
? as
->str
: NULL
);
2127 /* Printing functions */
2128 /* Feed the AS_PATH to the vty; the space suffix follows it only in case
2129 * AS_PATH wasn't empty.
2131 void aspath_print_vty(struct vty
*vty
, struct aspath
*as
)
2133 vty_out(vty
, "%s%s", as
->str
, as
->str_len
? " " : "");
2136 static void aspath_show_all_iterator(struct hash_bucket
*bucket
,
2141 as
= (struct aspath
*)bucket
->data
;
2143 vty_out(vty
, "[%p:%u] (%ld) ", (void *)bucket
, bucket
->key
, as
->refcnt
);
2144 vty_out(vty
, "%s\n", as
->str
);
2147 /* Print all aspath and hash information. This function is used from
2148 `show [ip] bgp paths' command. */
2149 void aspath_print_all_vty(struct vty
*vty
)
2151 hash_iterate(ashash
, (void (*)(struct hash_bucket
*,
2152 void *))aspath_show_all_iterator
,
2156 static struct aspath
*bgp_aggr_aspath_lookup(struct bgp_aggregate
*aggregate
,
2157 struct aspath
*aspath
)
2159 return hash_lookup(aggregate
->aspath_hash
, aspath
);
2162 static void *bgp_aggr_aspath_hash_alloc(void *p
)
2164 struct aspath
*ref
= (struct aspath
*)p
;
2165 struct aspath
*aspath
= NULL
;
2167 aspath
= aspath_dup(ref
);
2171 static void bgp_aggr_aspath_prepare(struct hash_bucket
*hb
, void *arg
)
2173 struct aspath
*hb_aspath
= hb
->data
;
2174 struct aspath
**aggr_aspath
= arg
;
2177 *aggr_aspath
= aspath_aggregate(*aggr_aspath
, hb_aspath
);
2179 *aggr_aspath
= aspath_dup(hb_aspath
);
2182 void bgp_aggr_aspath_remove(void *arg
)
2184 struct aspath
*aspath
= arg
;
2186 aspath_free(aspath
);
2189 void bgp_compute_aggregate_aspath(struct bgp_aggregate
*aggregate
,
2190 struct aspath
*aspath
)
2192 bgp_compute_aggregate_aspath_hash(aggregate
, aspath
);
2194 bgp_compute_aggregate_aspath_val(aggregate
);
2198 void bgp_compute_aggregate_aspath_hash(struct bgp_aggregate
*aggregate
,
2199 struct aspath
*aspath
)
2201 struct aspath
*aggr_aspath
= NULL
;
2203 if ((aggregate
== NULL
) || (aspath
== NULL
))
2206 /* Create hash if not already created.
2208 if (aggregate
->aspath_hash
== NULL
)
2209 aggregate
->aspath_hash
= hash_create(
2210 aspath_key_make
, aspath_cmp
,
2211 "BGP Aggregator as-path hash");
2213 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2214 if (aggr_aspath
== NULL
) {
2215 /* Insert as-path into hash.
2217 aggr_aspath
= hash_get(aggregate
->aspath_hash
, aspath
,
2218 bgp_aggr_aspath_hash_alloc
);
2221 /* Increment reference counter.
2223 aggr_aspath
->refcnt
++;
2226 void bgp_compute_aggregate_aspath_val(struct bgp_aggregate
*aggregate
)
2228 if (aggregate
== NULL
)
2230 /* Re-compute aggregate's as-path.
2232 if (aggregate
->aspath
) {
2233 aspath_free(aggregate
->aspath
);
2234 aggregate
->aspath
= NULL
;
2236 if (aggregate
->aspath_hash
2237 && aggregate
->aspath_hash
->count
) {
2238 hash_iterate(aggregate
->aspath_hash
,
2239 bgp_aggr_aspath_prepare
,
2240 &aggregate
->aspath
);
2244 void bgp_remove_aspath_from_aggregate(struct bgp_aggregate
*aggregate
,
2245 struct aspath
*aspath
)
2247 struct aspath
*aggr_aspath
= NULL
;
2248 struct aspath
*ret_aspath
= NULL
;
2251 || (!aggregate
->aspath_hash
)
2255 /* Look-up the aspath in the hash.
2257 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2259 aggr_aspath
->refcnt
--;
2261 if (aggr_aspath
->refcnt
== 0) {
2262 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2264 aspath_free(ret_aspath
);
2267 /* Remove aggregate's old as-path.
2269 aspath_free(aggregate
->aspath
);
2270 aggregate
->aspath
= NULL
;
2272 bgp_compute_aggregate_aspath_val(aggregate
);
2277 void bgp_remove_aspath_from_aggregate_hash(struct bgp_aggregate
*aggregate
,
2278 struct aspath
*aspath
)
2280 struct aspath
*aggr_aspath
= NULL
;
2281 struct aspath
*ret_aspath
= NULL
;
2284 || (!aggregate
->aspath_hash
)
2288 /* Look-up the aspath in the hash.
2290 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2292 aggr_aspath
->refcnt
--;
2294 if (aggr_aspath
->refcnt
== 0) {
2295 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2297 aspath_free(ret_aspath
);