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(void)
307 return XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
310 /* Free AS path structure. */
311 void aspath_free(struct aspath
*aspath
)
315 if (aspath
->segments
)
316 assegment_free_all(aspath
->segments
);
317 XFREE(MTYPE_AS_STR
, aspath
->str
);
320 json_object_free(aspath
->json
);
324 XFREE(MTYPE_AS_PATH
, aspath
);
327 /* Unintern aspath from AS path bucket. */
328 void aspath_unintern(struct aspath
**aspath
)
341 if (asp
->refcnt
== 0) {
342 /* This aspath must exist in aspath hash table. */
343 ret
= hash_release(ashash
, asp
);
350 /* Return the start or end delimiters for a particular Segment type */
351 #define AS_SEG_START 0
353 static char aspath_delimiter_char(uint8_t type
, uint8_t which
)
360 } aspath_delim_char
[] = {{AS_SET
, '{', '}'},
361 {AS_CONFED_SET
, '[', ']'},
362 {AS_CONFED_SEQUENCE
, '(', ')'},
365 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++) {
366 if (aspath_delim_char
[i
].type
== type
) {
367 if (which
== AS_SEG_START
)
368 return aspath_delim_char
[i
].start
;
369 else if (which
== AS_SEG_END
)
370 return aspath_delim_char
[i
].end
;
376 /* countup asns from this segment and index onward */
377 static int assegment_count_asns(struct assegment
*seg
, int from
)
382 count
+= seg
->length
;
384 count
+= (seg
->length
- from
);
392 unsigned int aspath_count_confeds(struct aspath
*aspath
)
395 struct assegment
*seg
= aspath
->segments
;
398 if (seg
->type
== AS_CONFED_SEQUENCE
)
399 count
+= seg
->length
;
400 else if (seg
->type
== AS_CONFED_SET
)
408 unsigned int aspath_count_hops(const struct aspath
*aspath
)
411 struct assegment
*seg
= aspath
->segments
;
414 if (seg
->type
== AS_SEQUENCE
)
415 count
+= seg
->length
;
416 else if (seg
->type
== AS_SET
)
424 /* Check if aspath has AS_SET or AS_CONFED_SET */
425 bool aspath_check_as_sets(struct aspath
*aspath
)
427 struct assegment
*seg
= aspath
->segments
;
430 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
)
437 /* Check if aspath has BGP_AS_ZERO */
438 bool aspath_check_as_zero(struct aspath
*aspath
)
440 struct assegment
*seg
= aspath
->segments
;
444 for (i
= 0; i
< seg
->length
; i
++)
445 if (seg
->as
[i
] == BGP_AS_ZERO
)
453 /* Estimate size aspath /might/ take if encoded into an
456 * This is a quick estimate, not definitive! aspath_put()
457 * may return a different number!!
459 unsigned int aspath_size(struct aspath
*aspath
)
462 struct assegment
*seg
= aspath
->segments
;
465 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
471 /* Return highest public ASN in path */
472 as_t
aspath_highest(struct aspath
*aspath
)
474 struct assegment
*seg
= aspath
->segments
;
479 for (i
= 0; i
< seg
->length
; i
++)
480 if (seg
->as
[i
] > highest
481 && !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
482 highest
= seg
->as
[i
];
488 /* Return the left-most ASN in path */
489 as_t
aspath_leftmost(struct aspath
*aspath
)
491 struct assegment
*seg
= aspath
->segments
;
494 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
495 leftmost
= seg
->as
[0];
500 /* Return 1 if there are any 4-byte ASes in the path */
501 bool aspath_has_as4(struct aspath
*aspath
)
503 struct assegment
*seg
= aspath
->segments
;
507 for (i
= 0; i
< seg
->length
; i
++)
508 if (seg
->as
[i
] > BGP_AS_MAX
)
515 /* Convert aspath structure to string expression. */
516 static void aspath_make_str_count(struct aspath
*as
, bool make_json
)
518 struct assegment
*seg
;
522 json_object
*jaspath_segments
= NULL
;
523 json_object
*jseg
= NULL
;
524 json_object
*jseg_list
= NULL
;
527 as
->json
= json_object_new_object();
528 jaspath_segments
= json_object_new_array();
534 json_object_string_add(as
->json
, "string", "Local");
535 json_object_object_add(as
->json
, "segments",
537 json_object_int_add(as
->json
, "length", 0);
539 as
->str
= XMALLOC(MTYPE_AS_STR
, 1);
547 /* ASN takes 5 to 10 chars plus separator, see below.
548 * If there is one differing segment type, we need an additional
549 * 2 chars for segment delimiters, and the final '\0'.
550 * Hopefully this is large enough to avoid hitting the realloc
551 * code below for most common sequences.
553 * This was changed to 10 after the well-known BGP assertion, which
554 * had hit some parts of the Internet in May of 2009.
556 #define ASN_STR_LEN (10 + 1)
557 str_size
= MAX(assegment_count_asns(seg
, 0) * ASN_STR_LEN
+ 2 + 1,
558 ASPATH_STR_DEFAULT_LEN
);
559 str_buf
= XMALLOC(MTYPE_AS_STR
, str_size
);
565 /* Check AS type validity. Set separator for segment */
572 case AS_CONFED_SEQUENCE
:
576 XFREE(MTYPE_AS_STR
, str_buf
);
579 json_object_free(as
->json
);
585 /* We might need to increase str_buf, particularly if path has
586 * differing segments types, our initial guesstimate above will
587 * have been wrong. Need 10 chars for ASN, a separator each and
588 * potentially two segment delimiters, plus a space between each
589 * segment and trailing zero.
591 * This definitely didn't work with the value of 5 bytes and
594 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
595 if ((len
+ SEGMENT_STR_LEN(seg
)) > str_size
) {
596 str_size
= len
+ SEGMENT_STR_LEN(seg
);
597 str_buf
= XREALLOC(MTYPE_AS_STR
, str_buf
, str_size
);
600 #undef SEGMENT_STR_LEN
602 if (seg
->type
!= AS_SEQUENCE
)
604 str_buf
+ len
, str_size
- len
, "%c",
605 aspath_delimiter_char(seg
->type
, AS_SEG_START
));
608 jseg_list
= json_object_new_array();
610 /* write out the ASNs, with their separators, bar the last one*/
611 for (i
= 0; i
< seg
->length
; i
++) {
613 json_object_array_add(
615 json_object_new_int64(seg
->as
[i
]));
617 len
+= snprintf(str_buf
+ len
, str_size
- len
, "%u",
620 if (i
< (seg
->length
- 1))
621 len
+= snprintf(str_buf
+ len
, str_size
- len
,
626 jseg
= json_object_new_object();
627 json_object_string_add(
629 aspath_segment_type_str
[seg
->type
]);
630 json_object_object_add(jseg
, "list", jseg_list
);
631 json_object_array_add(jaspath_segments
, jseg
);
634 if (seg
->type
!= AS_SEQUENCE
)
636 str_buf
+ len
, str_size
- len
, "%c",
637 aspath_delimiter_char(seg
->type
, AS_SEG_END
));
639 len
+= snprintf(str_buf
+ len
, str_size
- len
, " ");
644 assert(len
< str_size
);
651 json_object_string_add(as
->json
, "string", str_buf
);
652 json_object_object_add(as
->json
, "segments", jaspath_segments
);
653 json_object_int_add(as
->json
, "length", aspath_count_hops(as
));
659 void aspath_str_update(struct aspath
*as
, bool make_json
)
661 XFREE(MTYPE_AS_STR
, as
->str
);
664 json_object_free(as
->json
);
668 aspath_make_str_count(as
, make_json
);
671 /* Intern allocated AS path. */
672 struct aspath
*aspath_intern(struct aspath
*aspath
)
676 /* Assert this AS path structure is not interned and has the string
677 representation built. */
678 assert(aspath
->refcnt
== 0);
681 /* Check AS path hash. */
682 find
= hash_get(ashash
, aspath
, hash_alloc_intern
);
691 /* Duplicate aspath structure. Created same aspath structure but
692 reference count and AS path string is cleared. */
693 struct aspath
*aspath_dup(struct aspath
*aspath
)
695 unsigned short buflen
= aspath
->str_len
+ 1;
698 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
701 if (aspath
->segments
)
702 new->segments
= assegment_dup_all(aspath
->segments
);
707 new->str
= XMALLOC(MTYPE_AS_STR
, buflen
);
708 new->str_len
= aspath
->str_len
;
710 /* copy the string data */
711 if (aspath
->str_len
> 0)
712 memcpy(new->str
, aspath
->str
, buflen
);
719 static void *aspath_hash_alloc(void *arg
)
721 const struct aspath
*aspath
= arg
;
724 /* Malformed AS path value. */
727 /* New aspath structure is needed. */
728 new = XMALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
730 /* Reuse segments and string representation */
732 new->segments
= aspath
->segments
;
733 new->str
= aspath
->str
;
734 new->str_len
= aspath
->str_len
;
735 new->json
= aspath
->json
;
740 /* parse as-segment byte stream in struct assegment */
741 static int assegments_parse(struct stream
*s
, size_t length
,
742 struct assegment
**result
, int use32bit
)
744 struct assegment_header segh
;
745 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
748 /* empty aspath (ie iBGP or somesuch) */
752 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
754 "[AS4SEG] Parse aspath segment: got total byte length %lu",
755 (unsigned long)length
);
757 if ((STREAM_READABLE(s
) < length
)
758 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
759 || (length
% AS16_VALUE_SIZE
))
762 while (bytes
< length
) {
766 if ((length
- bytes
) <= AS_HEADER_SIZE
) {
768 assegment_free_all(head
);
772 /* softly softly, get the header first on its own */
773 segh
.type
= stream_getc(s
);
774 segh
.length
= stream_getc(s
);
776 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
778 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
780 "[AS4SEG] Parse aspath segment: got type %d, length %d",
781 segh
.type
, segh
.length
);
784 if (((bytes
+ seg_size
) > length
)
785 /* 1771bis 4.3b: seg length contains one or more */
786 || (segh
.length
== 0)
787 /* Paranoia in case someone changes type of segment length.
788 * Shift both values by 0x10 to make the comparison operate
789 * on more, than 8 bits (otherwise it's a warning, bug
792 || ((sizeof(segh
.length
) > 1)
793 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
))) {
795 assegment_free_all(head
);
802 case AS_CONFED_SEQUENCE
:
807 assegment_free_all(head
);
811 /* now its safe to trust lengths */
812 seg
= assegment_new(segh
.type
, segh
.length
);
816 else /* it's the first segment */
819 for (i
= 0; i
< segh
.length
; i
++)
821 (use32bit
) ? stream_getl(s
) : stream_getw(s
);
825 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
827 "[AS4SEG] Parse aspath segment: Bytes now: %lu",
828 (unsigned long)bytes
);
833 *result
= assegment_normalise(head
);
837 /* AS path parse function. pnt is a pointer to byte stream and length
838 is length of byte stream. If there is same AS path in the the AS
839 path hash then return it else make new AS path structure.
841 On error NULL is returned.
843 struct aspath
*aspath_parse(struct stream
*s
, size_t length
, int use32bit
)
848 /* If length is odd it's malformed AS path. */
849 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
850 * otherwise its malformed when length is larger than 2 and (length-2)
851 * is not dividable by 4.
852 * But... this time we're lazy
854 if (length
% AS16_VALUE_SIZE
)
857 memset(&as
, 0, sizeof(as
));
858 if (assegments_parse(s
, length
, &as
.segments
, use32bit
) < 0)
861 /* If already same aspath exist then return it. */
862 find
= hash_get(ashash
, &as
, aspath_hash_alloc
);
864 /* if the aspath was already hashed free temporary memory. */
866 assegment_free_all(as
.segments
);
867 /* aspath_key_make() always updates the string */
868 XFREE(MTYPE_AS_STR
, as
.str
);
870 json_object_free(as
.json
);
880 static void assegment_data_put(struct stream
*s
, as_t
*as
, int num
,
884 assert(num
<= AS_SEGMENT_MAX
);
886 for (i
= 0; i
< num
; i
++)
888 stream_putl(s
, as
[i
]);
890 if (as
[i
] <= BGP_AS_MAX
)
891 stream_putw(s
, as
[i
]);
893 stream_putw(s
, BGP_AS_TRANS
);
897 static size_t assegment_header_put(struct stream
*s
, uint8_t type
, int length
)
900 assert(length
<= AS_SEGMENT_MAX
);
901 stream_putc(s
, type
);
902 lenp
= stream_get_endp(s
);
903 stream_putc(s
, length
);
907 /* write aspath data to stream */
908 size_t aspath_put(struct stream
*s
, struct aspath
*as
, int use32bit
)
910 struct assegment
*seg
= as
->segments
;
913 if (!seg
|| seg
->length
== 0)
917 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
918 * At the moment, we would write out a partial aspath, and our
920 * will complain and drop the session :-/
922 * The general assumption here is that many things tested will
923 * never happen. And, in real live, up to now, they have not.
925 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
) <= STREAM_WRITEABLE(s
))) {
926 struct assegment
*next
= seg
->next
;
931 /* Overlength segments have to be split up */
932 while ((seg
->length
- written
) > AS_SEGMENT_MAX
) {
933 assegment_header_put(s
, seg
->type
, AS_SEGMENT_MAX
);
934 assegment_data_put(s
, (seg
->as
+ written
),
935 AS_SEGMENT_MAX
, use32bit
);
936 written
+= AS_SEGMENT_MAX
;
937 bytes
+= ASSEGMENT_SIZE(AS_SEGMENT_MAX
, use32bit
);
940 /* write the final segment, probably is also the first
942 lenp
= assegment_header_put(s
, seg
->type
,
943 seg
->length
- written
);
944 assegment_data_put(s
, (seg
->as
+ written
),
945 seg
->length
- written
, use32bit
);
947 /* Sequence-type segments can be 'packed' together
948 * Case of a segment which was overlength and split up
949 * will be missed here, but that doesn't matter.
951 while (next
&& ASSEGMENTS_PACKABLE(seg
, next
)) {
952 /* NB: We should never normally get here given
954 * normalise aspath data when parse them.
956 * safe than sorry. We potentially could call
957 * assegment_normalise here instead, but it's
959 * easier to do it on the fly here rather than
961 * the segment list twice every time we write
966 /* Next segment's data can fit in this one */
967 assegment_data_put(s
, next
->as
, next
->length
, use32bit
);
969 /* update the length of the segment header */
970 stream_putc_at(s
, lenp
,
971 seg
->length
- written
+ next
->length
);
972 asns_packed
+= next
->length
;
977 bytes
+= ASSEGMENT_SIZE(seg
->length
- written
+ asns_packed
,
984 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
985 * We have no way to manage the storage, so we use a static stream
986 * wrapper around aspath_put.
988 uint8_t *aspath_snmp_pathseg(struct aspath
*as
, size_t *varlen
)
990 #define SNMP_PATHSEG_MAX 1024
993 snmp_stream
= stream_new(SNMP_PATHSEG_MAX
);
995 stream_reset(snmp_stream
);
1001 aspath_put(snmp_stream
, as
, 0); /* use 16 bit for now here */
1003 *varlen
= stream_get_endp(snmp_stream
);
1004 return stream_pnt(snmp_stream
);
1007 static struct assegment
*aspath_aggregate_as_set_add(struct aspath
*aspath
,
1008 struct assegment
*asset
,
1013 /* If this is first AS set member, create new as-set segment. */
1014 if (asset
== NULL
) {
1015 asset
= assegment_new(AS_SET
, 1);
1016 if (!aspath
->segments
)
1017 aspath
->segments
= asset
;
1019 struct assegment
*seg
= aspath
->segments
;
1024 asset
->type
= AS_SET
;
1028 /* Check this AS value already exists or not. */
1029 for (i
= 0; i
< asset
->length
; i
++)
1030 if (asset
->as
[i
] == as
)
1034 asset
->as
= XREALLOC(MTYPE_AS_SEG_DATA
, asset
->as
,
1035 asset
->length
* AS_VALUE_SIZE
);
1036 asset
->as
[asset
->length
- 1] = as
;
1043 /* Modify as1 using as2 for aggregation. */
1044 struct aspath
*aspath_aggregate(struct aspath
*as1
, struct aspath
*as2
)
1050 struct assegment
*seg1
= as1
->segments
;
1051 struct assegment
*seg2
= as2
->segments
;
1052 struct aspath
*aspath
= NULL
;
1053 struct assegment
*asset
= NULL
;
1054 struct assegment
*prevseg
= NULL
;
1056 /* First of all check common leading sequence. */
1057 while (seg1
&& seg2
) {
1058 /* Check segment type. */
1059 if (seg1
->type
!= seg2
->type
)
1062 /* Minimum segment length. */
1063 minlen
= MIN(seg1
->length
, seg2
->length
);
1065 for (match
= 0; match
< minlen
; match
++)
1066 if (seg1
->as
[match
] != seg2
->as
[match
])
1070 struct assegment
*seg
= assegment_new(seg1
->type
, 0);
1072 seg
= assegment_append_asns(seg
, seg1
->as
, match
);
1075 aspath
= aspath_new();
1076 aspath
->segments
= seg
;
1078 prevseg
->next
= seg
;
1083 if (match
!= minlen
|| match
!= seg1
->length
1084 || seg1
->length
!= seg2
->length
)
1086 /* We are moving on to the next segment to reset match */
1095 aspath
= aspath_new();
1097 /* Make as-set using rest of all information. */
1100 for (i
= from
; i
< seg1
->length
; i
++)
1101 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1110 for (i
= from
; i
< seg2
->length
; i
++)
1111 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1118 assegment_normalise(aspath
->segments
);
1119 aspath_str_update(aspath
, false);
1123 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1124 attribute, check the leftmost AS number in the AS_PATH attribute is
1125 or not the peer's AS number. */
1126 bool aspath_firstas_check(struct aspath
*aspath
, as_t asno
)
1128 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1131 if (aspath
->segments
&& (aspath
->segments
->type
== AS_SEQUENCE
)
1132 && (aspath
->segments
->as
[0] == asno
))
1138 unsigned int aspath_get_first_as(struct aspath
*aspath
)
1140 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1143 return aspath
->segments
->as
[0];
1146 unsigned int aspath_get_last_as(struct aspath
*aspath
)
1149 unsigned int last_as
= 0;
1150 const struct assegment
*seg
;
1152 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1155 seg
= aspath
->segments
;
1158 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1159 for (i
= 0; i
< seg
->length
; i
++)
1160 last_as
= seg
->as
[i
];
1167 /* AS path loop check. If aspath contains asno then return >= 1. */
1168 int aspath_loop_check(struct aspath
*aspath
, as_t asno
)
1170 struct assegment
*seg
;
1173 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1176 seg
= aspath
->segments
;
1181 for (i
= 0; i
< seg
->length
; i
++)
1182 if (seg
->as
[i
] == asno
)
1190 /* AS path loop check. If aspath contains asno
1191 * that is a confed id then return >= 1.
1193 int aspath_loop_check_confed(struct aspath
*aspath
, as_t asno
)
1195 struct assegment
*seg
;
1198 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1201 seg
= aspath
->segments
;
1206 for (i
= 0; i
< seg
->length
; i
++)
1207 if (seg
->type
!= AS_CONFED_SEQUENCE
&&
1208 seg
->type
!= AS_CONFED_SET
&& seg
->as
[i
] == asno
)
1217 /* When all of AS path is private AS return 1. */
1218 bool aspath_private_as_check(struct aspath
*aspath
)
1220 struct assegment
*seg
;
1222 if (!(aspath
&& aspath
->segments
))
1225 seg
= aspath
->segments
;
1230 for (i
= 0; i
< seg
->length
; i
++) {
1231 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1239 /* Replace all instances of the target ASN with our own ASN */
1240 struct aspath
*aspath_replace_specific_asn(struct aspath
*aspath
,
1241 as_t target_asn
, as_t our_asn
)
1244 struct assegment
*seg
;
1246 new = aspath_dup(aspath
);
1247 seg
= new->segments
;
1252 for (i
= 0; i
< seg
->length
; i
++) {
1253 if (seg
->as
[i
] == target_asn
)
1254 seg
->as
[i
] = our_asn
;
1259 aspath_str_update(new, false);
1263 /* Replace all ASNs with our own ASN */
1264 struct aspath
*aspath_replace_all_asn(struct aspath
*aspath
, as_t our_asn
)
1267 struct assegment
*seg
;
1269 new = aspath_dup(aspath
);
1270 seg
= new->segments
;
1275 for (i
= 0; i
< seg
->length
; i
++)
1276 seg
->as
[i
] = our_asn
;
1281 aspath_str_update(new, false);
1285 /* Replace all private ASNs with our own ASN */
1286 struct aspath
*aspath_replace_private_asns(struct aspath
*aspath
, as_t asn
,
1290 struct assegment
*seg
;
1292 new = aspath_dup(aspath
);
1293 seg
= new->segments
;
1298 for (i
= 0; i
< seg
->length
; i
++) {
1299 /* Don't replace if public ASN or peer's ASN */
1300 if (BGP_AS_IS_PRIVATE(seg
->as
[i
])
1301 && (seg
->as
[i
] != peer_asn
))
1307 aspath_str_update(new, false);
1311 /* Remove all private ASNs */
1312 struct aspath
*aspath_remove_private_asns(struct aspath
*aspath
, as_t peer_asn
)
1315 struct assegment
*seg
;
1316 struct assegment
*new_seg
;
1317 struct assegment
*last_new_seg
;
1323 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
1327 last_new_seg
= NULL
;
1328 seg
= aspath
->segments
;
1332 for (i
= 0; i
< seg
->length
; i
++) {
1334 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1336 /* ASN matches peer's.
1337 * Don't double-count if peer_asn is public.
1339 else if (seg
->as
[i
] == peer_asn
)
1343 // The entire segment is public so copy it
1344 if (public == seg
->length
)
1345 new_seg
= assegment_dup(seg
);
1347 // The segment is a mix of public and private ASNs. Copy as many
1349 // there are public ASNs then come back and fill in only the
1352 /* length needs to account for all retained ASNs
1353 * (public or peer_asn), not just public
1355 new_seg
= assegment_new(seg
->type
, (public + peer
));
1357 for (i
= 0; i
< seg
->length
; i
++) {
1358 // keep ASN if public or matches peer's ASN
1359 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])
1360 || (seg
->as
[i
] == peer_asn
)) {
1361 new_seg
->as
[j
] = seg
->as
[i
];
1367 // This is the first segment so set the aspath segments pointer
1370 new->segments
= new_seg
;
1372 last_new_seg
->next
= new_seg
;
1374 last_new_seg
= new_seg
;
1378 aspath_str_update(new, false);
1382 /* AS path confed check. If aspath contains confed set or sequence then return
1384 bool aspath_confed_check(struct aspath
*aspath
)
1386 struct assegment
*seg
;
1388 if (!(aspath
&& aspath
->segments
))
1391 seg
= aspath
->segments
;
1394 if (seg
->type
== AS_CONFED_SET
1395 || seg
->type
== AS_CONFED_SEQUENCE
)
1402 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1403 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1404 bool aspath_left_confed_check(struct aspath
*aspath
)
1407 if (!(aspath
&& aspath
->segments
))
1410 if ((aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1411 || (aspath
->segments
->type
== AS_CONFED_SET
))
1417 /* Merge as1 to as2. as2 should be uninterned aspath. */
1418 static struct aspath
*aspath_merge(struct aspath
*as1
, struct aspath
*as2
)
1420 struct assegment
*last
, *new;
1425 last
= new = assegment_dup_all(as1
->segments
);
1427 /* find the last valid segment */
1428 while (last
&& last
->next
)
1432 last
->next
= as2
->segments
;
1433 as2
->segments
= new;
1434 aspath_str_update(as2
, false);
1438 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1439 struct aspath
*aspath_prepend(struct aspath
*as1
, struct aspath
*as2
)
1441 struct assegment
*as1segtail
;
1442 struct assegment
*as2segtail
;
1443 struct assegment
*as2seghead
;
1448 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1449 if (as2
->segments
== NULL
) {
1450 as2
->segments
= assegment_dup_all(as1
->segments
);
1451 aspath_str_update(as2
, false);
1455 /* If as1 is empty AS, no prepending to do. */
1456 if (as1
->segments
== NULL
)
1459 /* find the tail as1's segment chain. */
1460 as1segtail
= as1
->segments
;
1461 while (as1segtail
&& as1segtail
->next
)
1462 as1segtail
= as1segtail
->next
;
1464 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1465 if (as1segtail
->type
== AS_SEQUENCE
1466 && as2
->segments
->type
== AS_CONFED_SEQUENCE
)
1467 as2
= aspath_delete_confed_seq(as2
);
1469 if (!as2
->segments
) {
1470 as2
->segments
= assegment_dup_all(as1
->segments
);
1471 aspath_str_update(as2
, false);
1475 /* Compare last segment type of as1 and first segment type of as2. */
1476 if (as1segtail
->type
!= as2
->segments
->type
)
1477 return aspath_merge(as1
, as2
);
1479 if (as1segtail
->type
== AS_SEQUENCE
) {
1480 /* We have two chains of segments, as1->segments and seg2,
1481 * and we have to attach them together, merging the attaching
1482 * segments together into one.
1484 * 1. dupe as1->segments onto head of as2
1485 * 2. merge seg2's asns onto last segment of this new chain
1486 * 3. attach chain after seg2
1490 as2seghead
= as2
->segments
;
1492 /* dupe as1 onto as2's head */
1493 as2segtail
= as2
->segments
= assegment_dup_all(as1
->segments
);
1495 /* refind the tail of as2 */
1496 while (as2segtail
&& as2segtail
->next
)
1497 as2segtail
= as2segtail
->next
;
1499 /* merge the old head, seg2, into tail, seg1 */
1500 assegment_append_asns(as2segtail
, as2seghead
->as
,
1501 as2seghead
->length
);
1504 * bypass the merged seg2, and attach any chain after it
1505 * to chain descending from as2's head
1508 as2segtail
->next
= as2seghead
->next
;
1510 /* as2->segments is now referenceless and useless */
1511 assegment_free(as2seghead
);
1513 /* we've now prepended as1's segment chain to as2, merging
1514 * the inbetween AS_SEQUENCE of seg2 in the process
1516 aspath_str_update(as2
, false);
1519 /* AS_SET merge code is needed at here. */
1520 return aspath_merge(as1
, as2
);
1522 /* XXX: Ermmm, what if as1 has multiple segments?? */
1527 /* Iterate over AS_PATH segments and wipe all occurrences of the
1528 * listed AS numbers. Hence some segments may lose some or even
1529 * all data on the way, the operation is implemented as a smarter
1530 * version of aspath_dup(), which allocates memory to hold the new
1531 * data, not the original. The new AS path is returned.
1533 struct aspath
*aspath_filter_exclude(struct aspath
*source
,
1534 struct aspath
*exclude_list
)
1536 struct assegment
*srcseg
, *exclseg
, *lastseg
;
1537 struct aspath
*newpath
;
1539 newpath
= aspath_new();
1542 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
) {
1543 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1544 struct assegment
*newseg
;
1546 /* Find out, how much ASns are we going to pick from this
1548 * We can't perform filtering right inline, because the size of
1549 * the new segment isn't known at the moment yet.
1551 for (i
= 0; i
< srcseg
->length
; i
++) {
1553 for (exclseg
= exclude_list
->segments
;
1554 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1555 for (y
= 0; y
< exclseg
->length
; y
++)
1556 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1558 // There's no sense in testing
1559 // the rest of exclusion list,
1566 /* newlen is now the number of ASns to copy */
1570 /* Actual copying. Allocate memory and iterate once more,
1571 * performing filtering. */
1572 newseg
= assegment_new(srcseg
->type
, newlen
);
1573 for (i
= 0; i
< srcseg
->length
; i
++) {
1575 for (exclseg
= exclude_list
->segments
;
1576 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1577 for (y
= 0; y
< exclseg
->length
; y
++)
1578 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1584 newseg
->as
[done
++] = srcseg
->as
[i
];
1586 /* At his point newlen must be equal to done, and both must be
1588 * the filtered segment to the gross result. */
1590 newpath
->segments
= newseg
;
1592 lastseg
->next
= newseg
;
1595 aspath_str_update(newpath
, false);
1596 /* We are happy returning even an empty AS_PATH, because the
1598 * might expect this very behaviour. There's a mean to avoid this, if
1600 * by having a match rule against certain AS_PATH regexps in the
1603 aspath_free(source
);
1607 /* Add specified AS to the leftmost of aspath. */
1608 static struct aspath
*aspath_add_asns(struct aspath
*aspath
, as_t asno
,
1609 uint8_t type
, unsigned num
)
1611 struct assegment
*assegment
= aspath
->segments
;
1614 if (assegment
&& assegment
->type
== type
) {
1615 /* extend existing segment */
1617 assegment_prepend_asns(aspath
->segments
, asno
, num
);
1619 /* prepend with new segment */
1620 struct assegment
*newsegment
= assegment_new(type
, num
);
1621 for (i
= 0; i
< num
; i
++)
1622 newsegment
->as
[i
] = asno
;
1624 /* insert potentially replacing empty segment */
1625 if (assegment
&& assegment
->length
== 0) {
1626 newsegment
->next
= assegment
->next
;
1627 assegment_free(assegment
);
1629 newsegment
->next
= assegment
;
1630 aspath
->segments
= newsegment
;
1633 aspath_str_update(aspath
, false);
1637 /* Add specified AS to the leftmost of aspath num times. */
1638 struct aspath
*aspath_add_seq_n(struct aspath
*aspath
, as_t asno
, unsigned num
)
1640 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, num
);
1643 /* Add specified AS to the leftmost of aspath. */
1644 struct aspath
*aspath_add_seq(struct aspath
*aspath
, as_t asno
)
1646 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, 1);
1649 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1650 as2's leftmost AS is same return 1. */
1651 bool aspath_cmp_left(const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1653 const struct assegment
*seg1
;
1654 const struct assegment
*seg2
;
1656 if (!(aspath1
&& aspath2
))
1659 seg1
= aspath1
->segments
;
1660 seg2
= aspath2
->segments
;
1662 /* If both paths are originated in this AS then we do want to compare
1667 /* find first non-confed segments for each */
1668 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1669 || (seg1
->type
== AS_CONFED_SET
)))
1672 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1673 || (seg2
->type
== AS_CONFED_SET
)))
1677 if (!(seg1
&& seg2
&& (seg1
->type
== AS_SEQUENCE
)
1678 && (seg2
->type
== AS_SEQUENCE
)))
1681 if (seg1
->as
[0] == seg2
->as
[0])
1687 /* Truncate an aspath after a number of hops, and put the hops remaining
1688 * at the front of another aspath. Needed for AS4 compat.
1690 * Returned aspath is a /new/ aspath, which should either by free'd or
1691 * interned by the caller, as desired.
1693 struct aspath
*aspath_reconcile_as4(struct aspath
*aspath
,
1694 struct aspath
*as4path
)
1696 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1697 struct aspath
*newpath
= NULL
, *mergedpath
;
1698 int hops
, cpasns
= 0;
1700 if (!aspath
|| !as4path
)
1703 seg
= aspath
->segments
;
1705 /* CONFEDs should get reconciled too.. */
1706 hops
= (aspath_count_hops(aspath
) + aspath_count_confeds(aspath
))
1707 - aspath_count_hops(as4path
);
1710 if (BGP_DEBUG(as4
, AS4
))
1712 EC_BGP_ASPATH_FEWER_HOPS
,
1713 "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1714 /* Something's gone wrong. The RFC says we should now ignore
1716 * which is daft behaviour - it contains vital loop-detection
1717 * information which must have been removed from AS_PATH.
1719 hops
= aspath_count_hops(aspath
);
1723 newpath
= aspath_dup(as4path
);
1724 aspath_str_update(newpath
, false);
1728 if (BGP_DEBUG(as4
, AS4
))
1730 "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1731 aspath
->str
, as4path
->str
);
1733 while (seg
&& hops
> 0) {
1734 switch (seg
->type
) {
1738 cpasns
= seg
->length
;
1740 case AS_CONFED_SEQUENCE
:
1741 /* Should never split a confed-sequence, if hop-count
1742 * suggests we must then something's gone wrong
1745 * Most important goal is to preserve AS_PATHs prime
1747 * as loop-detector, so we fudge the numbers so that the
1749 * confed-sequence is merged in.
1751 if (hops
< seg
->length
) {
1752 if (BGP_DEBUG(as4
, AS4
))
1754 "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls across 2/4 ASN boundary somewhere, broken..");
1759 cpasns
= MIN(seg
->length
, hops
);
1760 hops
-= seg
->length
;
1763 assert(cpasns
<= seg
->length
);
1765 newseg
= assegment_new(seg
->type
, 0);
1766 newseg
= assegment_append_asns(newseg
, seg
->as
, cpasns
);
1769 newpath
= aspath_new();
1770 newpath
->segments
= newseg
;
1772 prevseg
->next
= newseg
;
1778 /* We may be able to join some segments here, and we must
1779 * do this because... we want normalised aspaths in out hash
1780 * and we do not want to stumble in aspath_put.
1782 mergedpath
= aspath_merge(newpath
, aspath_dup(as4path
));
1783 aspath_free(newpath
);
1784 mergedpath
->segments
= assegment_normalise(mergedpath
->segments
);
1785 aspath_str_update(mergedpath
, false);
1787 if (BGP_DEBUG(as4
, AS4
))
1788 zlog_debug("[AS4] result of synthesizing is %s",
1794 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1795 as2's leftmost AS is same return 1. (confederation as-path
1797 bool aspath_cmp_left_confed(const struct aspath
*aspath1
,
1798 const struct aspath
*aspath2
)
1800 if (!(aspath1
&& aspath2
))
1803 if (!(aspath1
->segments
&& aspath2
->segments
))
1806 if ((aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1807 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
))
1810 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1816 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1817 * RFC 5065 section 4.1.c.1
1819 * 1) if any path segments of the AS_PATH are of the type
1820 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1821 * removed from the AS_PATH attribute, leaving the sanitized
1822 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1824 struct aspath
*aspath_delete_confed_seq(struct aspath
*aspath
)
1826 struct assegment
*seg
, *prev
, *next
;
1827 char removed_confed_segment
;
1829 if (!(aspath
&& aspath
->segments
))
1832 seg
= aspath
->segments
;
1833 removed_confed_segment
= 0;
1840 if (seg
->type
== AS_CONFED_SEQUENCE
1841 || seg
->type
== AS_CONFED_SET
) {
1842 /* This is the first segment in the aspath */
1843 if (aspath
->segments
== seg
)
1844 aspath
->segments
= seg
->next
;
1846 prev
->next
= seg
->next
;
1848 assegment_free(seg
);
1849 removed_confed_segment
= 1;
1856 if (removed_confed_segment
)
1857 aspath_str_update(aspath
, false);
1862 /* Add new AS number to the leftmost part of the aspath as
1863 AS_CONFED_SEQUENCE. */
1864 struct aspath
*aspath_add_confed_seq(struct aspath
*aspath
, as_t asno
)
1866 return aspath_add_asns(aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1869 /* Add new as value to as path structure. */
1870 static void aspath_as_add(struct aspath
*as
, as_t asno
)
1872 struct assegment
*seg
= as
->segments
;
1877 /* Last segment search procedure. */
1881 assegment_append_asns(seg
, &asno
, 1);
1884 /* Add new as segment to the as path. */
1885 static void aspath_segment_add(struct aspath
*as
, int type
)
1887 struct assegment
*seg
= as
->segments
;
1888 struct assegment
*new = assegment_new(type
, 0);
1898 struct aspath
*aspath_empty(void)
1900 return aspath_parse(NULL
, 0, 1); /* 32Bit ;-) */
1903 struct aspath
*aspath_empty_get(void)
1905 struct aspath
*aspath
;
1907 aspath
= aspath_new();
1908 aspath_make_str_count(aspath
, false);
1912 unsigned long aspath_count(void)
1914 return ashash
->count
;
1918 Theoretically, one as path can have:
1920 One BGP packet size should be less than 4096.
1921 One BGP attribute size should be less than 4096 - BGP header size.
1922 One BGP aspath size should be less than 4096 - BGP header size -
1923 BGP mandantry attribute size.
1926 /* AS path string lexical token enum. */
1931 as_token_confed_seq_start
,
1932 as_token_confed_seq_end
,
1933 as_token_confed_set_start
,
1934 as_token_confed_set_end
,
1938 /* Return next token and point for string parse. */
1939 static const char *aspath_gettoken(const char *buf
, enum as_token
*token
,
1940 unsigned long *asno
)
1942 const char *p
= buf
;
1944 /* Skip separators (space for sequences, ',' for sets). */
1945 while (isspace((unsigned char)*p
) || *p
== ',')
1948 /* Check the end of the string and type specify characters
1954 *token
= as_token_set_start
;
1958 *token
= as_token_set_end
;
1962 *token
= as_token_confed_seq_start
;
1966 *token
= as_token_confed_seq_end
;
1970 *token
= as_token_confed_set_start
;
1974 *token
= as_token_confed_set_end
;
1979 /* Check actual AS value. */
1980 if (isdigit((unsigned char)*p
)) {
1983 *token
= as_token_asval
;
1987 while (isdigit((unsigned char)*p
)) {
1989 asval
+= (*p
- '0');
1996 /* There is no match then return unknown token. */
1997 *token
= as_token_unknown
;
2002 struct aspath
*aspath_str2aspath(const char *str
)
2004 enum as_token token
= as_token_unknown
;
2005 unsigned short as_type
;
2006 unsigned long asno
= 0;
2007 struct aspath
*aspath
;
2010 aspath
= aspath_new();
2012 /* We start default type as AS_SEQUENCE. */
2013 as_type
= AS_SEQUENCE
;
2016 while ((str
= aspath_gettoken(str
, &token
, &asno
)) != NULL
) {
2018 case as_token_asval
:
2020 aspath_segment_add(aspath
, as_type
);
2023 aspath_as_add(aspath
, asno
);
2025 case as_token_set_start
:
2027 aspath_segment_add(aspath
, as_type
);
2030 case as_token_set_end
:
2031 as_type
= AS_SEQUENCE
;
2034 case as_token_confed_seq_start
:
2035 as_type
= AS_CONFED_SEQUENCE
;
2036 aspath_segment_add(aspath
, as_type
);
2039 case as_token_confed_seq_end
:
2040 as_type
= AS_SEQUENCE
;
2043 case as_token_confed_set_start
:
2044 as_type
= AS_CONFED_SET
;
2045 aspath_segment_add(aspath
, as_type
);
2048 case as_token_confed_set_end
:
2049 as_type
= AS_SEQUENCE
;
2052 case as_token_unknown
:
2054 aspath_free(aspath
);
2059 aspath_make_str_count(aspath
, false);
2064 /* Make hash value by raw aspath data. */
2065 unsigned int aspath_key_make(const void *p
)
2067 const struct aspath
*aspath
= p
;
2068 unsigned int key
= 0;
2071 aspath_str_update((struct aspath
*)aspath
, false);
2073 key
= jhash(aspath
->str
, aspath
->str_len
, 2334325);
2078 /* If two aspath have same value then return 1 else return 0 */
2079 bool aspath_cmp(const void *arg1
, const void *arg2
)
2081 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2082 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2084 while (seg1
|| seg2
) {
2086 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2088 if (seg1
->type
!= seg2
->type
)
2090 if (seg1
->length
!= seg2
->length
)
2092 for (i
= 0; i
< seg1
->length
; i
++)
2093 if (seg1
->as
[i
] != seg2
->as
[i
])
2101 /* AS path hash initialize. */
2102 void aspath_init(void)
2104 ashash
= hash_create_size(32768, aspath_key_make
, aspath_cmp
,
2108 void aspath_finish(void)
2110 hash_clean(ashash
, (void (*)(void *))aspath_free
);
2115 stream_free(snmp_stream
);
2118 /* return and as path value */
2119 const char *aspath_print(struct aspath
*as
)
2121 return (as
? as
->str
: NULL
);
2124 /* Printing functions */
2125 /* Feed the AS_PATH to the vty; the space suffix follows it only in case
2126 * AS_PATH wasn't empty.
2128 void aspath_print_vty(struct vty
*vty
, struct aspath
*as
)
2130 vty_out(vty
, "%s%s", as
->str
, as
->str_len
? " " : "");
2133 static void aspath_show_all_iterator(struct hash_bucket
*bucket
,
2138 as
= (struct aspath
*)bucket
->data
;
2140 vty_out(vty
, "[%p:%u] (%ld) ", (void *)bucket
, bucket
->key
, as
->refcnt
);
2141 vty_out(vty
, "%s\n", as
->str
);
2144 /* Print all aspath and hash information. This function is used from
2145 `show [ip] bgp paths' command. */
2146 void aspath_print_all_vty(struct vty
*vty
)
2148 hash_iterate(ashash
, (void (*)(struct hash_bucket
*,
2149 void *))aspath_show_all_iterator
,
2153 static struct aspath
*bgp_aggr_aspath_lookup(struct bgp_aggregate
*aggregate
,
2154 struct aspath
*aspath
)
2156 return hash_lookup(aggregate
->aspath_hash
, aspath
);
2159 static void *bgp_aggr_aspath_hash_alloc(void *p
)
2161 struct aspath
*ref
= (struct aspath
*)p
;
2162 struct aspath
*aspath
= NULL
;
2164 aspath
= aspath_dup(ref
);
2168 static void bgp_aggr_aspath_prepare(struct hash_bucket
*hb
, void *arg
)
2170 struct aspath
*hb_aspath
= hb
->data
;
2171 struct aspath
**aggr_aspath
= arg
;
2174 *aggr_aspath
= aspath_aggregate(*aggr_aspath
, hb_aspath
);
2176 *aggr_aspath
= aspath_dup(hb_aspath
);
2179 void bgp_aggr_aspath_remove(void *arg
)
2181 struct aspath
*aspath
= arg
;
2183 aspath_free(aspath
);
2186 void bgp_compute_aggregate_aspath(struct bgp_aggregate
*aggregate
,
2187 struct aspath
*aspath
)
2189 bgp_compute_aggregate_aspath_hash(aggregate
, aspath
);
2191 bgp_compute_aggregate_aspath_val(aggregate
);
2195 void bgp_compute_aggregate_aspath_hash(struct bgp_aggregate
*aggregate
,
2196 struct aspath
*aspath
)
2198 struct aspath
*aggr_aspath
= NULL
;
2200 if ((aggregate
== NULL
) || (aspath
== NULL
))
2203 /* Create hash if not already created.
2205 if (aggregate
->aspath_hash
== NULL
)
2206 aggregate
->aspath_hash
= hash_create(
2207 aspath_key_make
, aspath_cmp
,
2208 "BGP Aggregator as-path hash");
2210 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2211 if (aggr_aspath
== NULL
) {
2212 /* Insert as-path into hash.
2214 aggr_aspath
= hash_get(aggregate
->aspath_hash
, aspath
,
2215 bgp_aggr_aspath_hash_alloc
);
2218 /* Increment reference counter.
2220 aggr_aspath
->refcnt
++;
2223 void bgp_compute_aggregate_aspath_val(struct bgp_aggregate
*aggregate
)
2225 if (aggregate
== NULL
)
2227 /* Re-compute aggregate's as-path.
2229 if (aggregate
->aspath
) {
2230 aspath_free(aggregate
->aspath
);
2231 aggregate
->aspath
= NULL
;
2233 if (aggregate
->aspath_hash
2234 && aggregate
->aspath_hash
->count
) {
2235 hash_iterate(aggregate
->aspath_hash
,
2236 bgp_aggr_aspath_prepare
,
2237 &aggregate
->aspath
);
2241 void bgp_remove_aspath_from_aggregate(struct bgp_aggregate
*aggregate
,
2242 struct aspath
*aspath
)
2244 struct aspath
*aggr_aspath
= NULL
;
2245 struct aspath
*ret_aspath
= NULL
;
2248 || (!aggregate
->aspath_hash
)
2252 /* Look-up the aspath in the hash.
2254 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2256 aggr_aspath
->refcnt
--;
2258 if (aggr_aspath
->refcnt
== 0) {
2259 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2261 aspath_free(ret_aspath
);
2264 /* Remove aggregate's old as-path.
2266 aspath_free(aggregate
->aspath
);
2267 aggregate
->aspath
= NULL
;
2269 bgp_compute_aggregate_aspath_val(aggregate
);
2274 void bgp_remove_aspath_from_aggregate_hash(struct bgp_aggregate
*aggregate
,
2275 struct aspath
*aspath
)
2277 struct aspath
*aggr_aspath
= NULL
;
2278 struct aspath
*ret_aspath
= NULL
;
2281 || (!aggregate
->aspath_hash
)
2285 /* Look-up the aspath in the hash.
2287 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2289 aggr_aspath
->refcnt
--;
2291 if (aggr_aspath
->refcnt
== 0) {
2292 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2294 aspath_free(ret_aspath
);