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
)
331 struct aspath
*asp
= *aspath
;
336 if (asp
->refcnt
== 0) {
337 /* This aspath must exist in aspath hash table. */
338 ret
= hash_release(ashash
, asp
);
345 /* Return the start or end delimiters for a particular Segment type */
346 #define AS_SEG_START 0
348 static char aspath_delimiter_char(uint8_t type
, uint8_t which
)
355 } aspath_delim_char
[] = {{AS_SET
, '{', '}'},
356 {AS_CONFED_SET
, '[', ']'},
357 {AS_CONFED_SEQUENCE
, '(', ')'},
360 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++) {
361 if (aspath_delim_char
[i
].type
== type
) {
362 if (which
== AS_SEG_START
)
363 return aspath_delim_char
[i
].start
;
364 else if (which
== AS_SEG_END
)
365 return aspath_delim_char
[i
].end
;
371 /* countup asns from this segment and index onward */
372 static int assegment_count_asns(struct assegment
*seg
, int from
)
377 count
+= seg
->length
;
379 count
+= (seg
->length
- from
);
387 unsigned int aspath_count_confeds(struct aspath
*aspath
)
390 struct assegment
*seg
= aspath
->segments
;
393 if (seg
->type
== AS_CONFED_SEQUENCE
)
394 count
+= seg
->length
;
395 else if (seg
->type
== AS_CONFED_SET
)
403 unsigned int aspath_count_hops(const struct aspath
*aspath
)
406 struct assegment
*seg
= aspath
->segments
;
409 if (seg
->type
== AS_SEQUENCE
)
410 count
+= seg
->length
;
411 else if (seg
->type
== AS_SET
)
419 /* Check if aspath has AS_SET or AS_CONFED_SET */
420 bool aspath_check_as_sets(struct aspath
*aspath
)
422 struct assegment
*seg
= aspath
->segments
;
425 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
)
432 /* Check if aspath has BGP_AS_ZERO */
433 bool aspath_check_as_zero(struct aspath
*aspath
)
435 struct assegment
*seg
= aspath
->segments
;
439 for (i
= 0; i
< seg
->length
; i
++)
440 if (seg
->as
[i
] == BGP_AS_ZERO
)
448 /* Estimate size aspath /might/ take if encoded into an
451 * This is a quick estimate, not definitive! aspath_put()
452 * may return a different number!!
454 unsigned int aspath_size(struct aspath
*aspath
)
457 struct assegment
*seg
= aspath
->segments
;
460 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
466 /* Return highest public ASN in path */
467 as_t
aspath_highest(struct aspath
*aspath
)
469 struct assegment
*seg
= aspath
->segments
;
474 for (i
= 0; i
< seg
->length
; i
++)
475 if (seg
->as
[i
] > highest
476 && !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
477 highest
= seg
->as
[i
];
483 /* Return the left-most ASN in path */
484 as_t
aspath_leftmost(struct aspath
*aspath
)
486 struct assegment
*seg
= aspath
->segments
;
489 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
490 leftmost
= seg
->as
[0];
495 /* Return 1 if there are any 4-byte ASes in the path */
496 bool aspath_has_as4(struct aspath
*aspath
)
498 struct assegment
*seg
= aspath
->segments
;
502 for (i
= 0; i
< seg
->length
; i
++)
503 if (seg
->as
[i
] > BGP_AS_MAX
)
510 /* Convert aspath structure to string expression. */
511 static void aspath_make_str_count(struct aspath
*as
, bool make_json
)
513 struct assegment
*seg
;
517 json_object
*jaspath_segments
= NULL
;
518 json_object
*jseg
= NULL
;
519 json_object
*jseg_list
= NULL
;
522 as
->json
= json_object_new_object();
523 jaspath_segments
= json_object_new_array();
529 json_object_string_add(as
->json
, "string", "Local");
530 json_object_object_add(as
->json
, "segments",
532 json_object_int_add(as
->json
, "length", 0);
534 as
->str
= XMALLOC(MTYPE_AS_STR
, 1);
542 /* ASN takes 5 to 10 chars plus seperator, see below.
543 * If there is one differing segment type, we need an additional
544 * 2 chars for segment delimiters, and the final '\0'.
545 * Hopefully this is large enough to avoid hitting the realloc
546 * code below for most common sequences.
548 * This was changed to 10 after the well-known BGP assertion, which
549 * had hit some parts of the Internet in May of 2009.
551 #define ASN_STR_LEN (10 + 1)
552 str_size
= MAX(assegment_count_asns(seg
, 0) * ASN_STR_LEN
+ 2 + 1,
553 ASPATH_STR_DEFAULT_LEN
);
554 str_buf
= XMALLOC(MTYPE_AS_STR
, str_size
);
560 /* Check AS type validity. Set seperator for segment */
567 case AS_CONFED_SEQUENCE
:
571 XFREE(MTYPE_AS_STR
, str_buf
);
574 json_object_free(as
->json
);
580 /* We might need to increase str_buf, particularly if path has
581 * differing segments types, our initial guesstimate above will
582 * have been wrong. Need 10 chars for ASN, a seperator each and
583 * potentially two segment delimiters, plus a space between each
584 * segment and trailing zero.
586 * This definitely didn't work with the value of 5 bytes and
589 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
590 if ((len
+ SEGMENT_STR_LEN(seg
)) > str_size
) {
591 str_size
= len
+ SEGMENT_STR_LEN(seg
);
592 str_buf
= XREALLOC(MTYPE_AS_STR
, str_buf
, str_size
);
595 #undef SEGMENT_STR_LEN
597 if (seg
->type
!= AS_SEQUENCE
)
599 str_buf
+ len
, str_size
- len
, "%c",
600 aspath_delimiter_char(seg
->type
, AS_SEG_START
));
603 jseg_list
= json_object_new_array();
605 /* write out the ASNs, with their seperators, bar the last one*/
606 for (i
= 0; i
< seg
->length
; i
++) {
608 json_object_array_add(
610 json_object_new_int64(seg
->as
[i
]));
612 len
+= snprintf(str_buf
+ len
, str_size
- len
, "%u",
615 if (i
< (seg
->length
- 1))
616 len
+= snprintf(str_buf
+ len
, str_size
- len
,
621 jseg
= json_object_new_object();
622 json_object_string_add(
624 aspath_segment_type_str
[seg
->type
]);
625 json_object_object_add(jseg
, "list", jseg_list
);
626 json_object_array_add(jaspath_segments
, jseg
);
629 if (seg
->type
!= AS_SEQUENCE
)
631 str_buf
+ len
, str_size
- len
, "%c",
632 aspath_delimiter_char(seg
->type
, AS_SEG_END
));
634 len
+= snprintf(str_buf
+ len
, str_size
- len
, " ");
639 assert(len
< str_size
);
646 json_object_string_add(as
->json
, "string", str_buf
);
647 json_object_object_add(as
->json
, "segments", jaspath_segments
);
648 json_object_int_add(as
->json
, "length", aspath_count_hops(as
));
654 void aspath_str_update(struct aspath
*as
, bool make_json
)
656 XFREE(MTYPE_AS_STR
, as
->str
);
659 json_object_free(as
->json
);
663 aspath_make_str_count(as
, make_json
);
666 /* Intern allocated AS path. */
667 struct aspath
*aspath_intern(struct aspath
*aspath
)
671 /* Assert this AS path structure is not interned and has the string
672 representation built. */
673 assert(aspath
->refcnt
== 0);
676 /* Check AS path hash. */
677 find
= hash_get(ashash
, aspath
, hash_alloc_intern
);
686 /* Duplicate aspath structure. Created same aspath structure but
687 reference count and AS path string is cleared. */
688 struct aspath
*aspath_dup(struct aspath
*aspath
)
690 unsigned short buflen
= aspath
->str_len
+ 1;
693 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
696 if (aspath
->segments
)
697 new->segments
= assegment_dup_all(aspath
->segments
);
702 new->str
= XMALLOC(MTYPE_AS_STR
, buflen
);
703 new->str_len
= aspath
->str_len
;
705 /* copy the string data */
706 if (aspath
->str_len
> 0)
707 memcpy(new->str
, aspath
->str
, buflen
);
714 static void *aspath_hash_alloc(void *arg
)
716 const struct aspath
*aspath
= arg
;
719 /* Malformed AS path value. */
722 /* New aspath structure is needed. */
723 new = XMALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
725 /* Reuse segments and string representation */
727 new->segments
= aspath
->segments
;
728 new->str
= aspath
->str
;
729 new->str_len
= aspath
->str_len
;
730 new->json
= aspath
->json
;
735 /* parse as-segment byte stream in struct assegment */
736 static int assegments_parse(struct stream
*s
, size_t length
,
737 struct assegment
**result
, int use32bit
)
739 struct assegment_header segh
;
740 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
743 /* empty aspath (ie iBGP or somesuch) */
747 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
749 "[AS4SEG] Parse aspath segment: got total byte length %lu",
750 (unsigned long)length
);
752 if ((STREAM_READABLE(s
) < length
)
753 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
754 || (length
% AS16_VALUE_SIZE
))
757 while (bytes
< length
) {
761 if ((length
- bytes
) <= AS_HEADER_SIZE
) {
763 assegment_free_all(head
);
767 /* softly softly, get the header first on its own */
768 segh
.type
= stream_getc(s
);
769 segh
.length
= stream_getc(s
);
771 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
773 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
775 "[AS4SEG] Parse aspath segment: got type %d, length %d",
776 segh
.type
, segh
.length
);
779 if (((bytes
+ seg_size
) > length
)
780 /* 1771bis 4.3b: seg length contains one or more */
781 || (segh
.length
== 0)
782 /* Paranoia in case someone changes type of segment length.
783 * Shift both values by 0x10 to make the comparison operate
784 * on more, than 8 bits (otherwise it's a warning, bug
787 || ((sizeof(segh
.length
) > 1)
788 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
))) {
790 assegment_free_all(head
);
797 case AS_CONFED_SEQUENCE
:
802 assegment_free_all(head
);
806 /* now its safe to trust lengths */
807 seg
= assegment_new(segh
.type
, segh
.length
);
811 else /* it's the first segment */
814 for (i
= 0; i
< segh
.length
; i
++)
816 (use32bit
) ? stream_getl(s
) : stream_getw(s
);
820 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
822 "[AS4SEG] Parse aspath segment: Bytes now: %lu",
823 (unsigned long)bytes
);
828 *result
= assegment_normalise(head
);
832 /* AS path parse function. pnt is a pointer to byte stream and length
833 is length of byte stream. If there is same AS path in the the AS
834 path hash then return it else make new AS path structure.
836 On error NULL is returned.
838 struct aspath
*aspath_parse(struct stream
*s
, size_t length
, int use32bit
)
843 /* If length is odd it's malformed AS path. */
844 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
845 * otherwise its malformed when length is larger than 2 and (length-2)
846 * is not dividable by 4.
847 * But... this time we're lazy
849 if (length
% AS16_VALUE_SIZE
)
852 memset(&as
, 0, sizeof(struct aspath
));
853 if (assegments_parse(s
, length
, &as
.segments
, use32bit
) < 0)
856 /* If already same aspath exist then return it. */
857 find
= hash_get(ashash
, &as
, aspath_hash_alloc
);
859 /* bug! should not happen, let the daemon crash below */
862 /* if the aspath was already hashed free temporary memory. */
864 assegment_free_all(as
.segments
);
865 /* aspath_key_make() always updates the string */
866 XFREE(MTYPE_AS_STR
, as
.str
);
868 json_object_free(as
.json
);
878 static void assegment_data_put(struct stream
*s
, as_t
*as
, int num
,
882 assert(num
<= AS_SEGMENT_MAX
);
884 for (i
= 0; i
< num
; i
++)
886 stream_putl(s
, as
[i
]);
888 if (as
[i
] <= BGP_AS_MAX
)
889 stream_putw(s
, as
[i
]);
891 stream_putw(s
, BGP_AS_TRANS
);
895 static size_t assegment_header_put(struct stream
*s
, uint8_t type
, int length
)
898 assert(length
<= AS_SEGMENT_MAX
);
899 stream_putc(s
, type
);
900 lenp
= stream_get_endp(s
);
901 stream_putc(s
, length
);
905 /* write aspath data to stream */
906 size_t aspath_put(struct stream
*s
, struct aspath
*as
, int use32bit
)
908 struct assegment
*seg
= as
->segments
;
911 if (!seg
|| seg
->length
== 0)
915 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
916 * At the moment, we would write out a partial aspath, and our
918 * will complain and drop the session :-/
920 * The general assumption here is that many things tested will
921 * never happen. And, in real live, up to now, they have not.
923 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
) <= STREAM_WRITEABLE(s
))) {
924 struct assegment
*next
= seg
->next
;
929 /* Overlength segments have to be split up */
930 while ((seg
->length
- written
) > AS_SEGMENT_MAX
) {
931 assegment_header_put(s
, seg
->type
, AS_SEGMENT_MAX
);
932 assegment_data_put(s
, (seg
->as
+ written
),
933 AS_SEGMENT_MAX
, use32bit
);
934 written
+= AS_SEGMENT_MAX
;
935 bytes
+= ASSEGMENT_SIZE(AS_SEGMENT_MAX
, use32bit
);
938 /* write the final segment, probably is also the first
940 lenp
= assegment_header_put(s
, seg
->type
,
941 seg
->length
- written
);
942 assegment_data_put(s
, (seg
->as
+ written
),
943 seg
->length
- written
, use32bit
);
945 /* Sequence-type segments can be 'packed' together
946 * Case of a segment which was overlength and split up
947 * will be missed here, but that doesn't matter.
949 while (next
&& ASSEGMENTS_PACKABLE(seg
, next
)) {
950 /* NB: We should never normally get here given
952 * normalise aspath data when parse them.
954 * safe than sorry. We potentially could call
955 * assegment_normalise here instead, but it's
957 * easier to do it on the fly here rather than
959 * the segment list twice every time we write
964 /* Next segment's data can fit in this one */
965 assegment_data_put(s
, next
->as
, next
->length
, use32bit
);
967 /* update the length of the segment header */
968 stream_putc_at(s
, lenp
,
969 seg
->length
- written
+ next
->length
);
970 asns_packed
+= next
->length
;
975 bytes
+= ASSEGMENT_SIZE(seg
->length
- written
+ asns_packed
,
982 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
983 * We have no way to manage the storage, so we use a static stream
984 * wrapper around aspath_put.
986 uint8_t *aspath_snmp_pathseg(struct aspath
*as
, size_t *varlen
)
988 #define SNMP_PATHSEG_MAX 1024
991 snmp_stream
= stream_new(SNMP_PATHSEG_MAX
);
993 stream_reset(snmp_stream
);
999 aspath_put(snmp_stream
, as
, 0); /* use 16 bit for now here */
1001 *varlen
= stream_get_endp(snmp_stream
);
1002 return stream_pnt(snmp_stream
);
1005 #define min(A,B) ((A) < (B) ? (A) : (B))
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 /* When all of AS path is private AS return 1. */
1191 bool aspath_private_as_check(struct aspath
*aspath
)
1193 struct assegment
*seg
;
1195 if (!(aspath
&& aspath
->segments
))
1198 seg
= aspath
->segments
;
1203 for (i
= 0; i
< seg
->length
; i
++) {
1204 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1212 /* Return True if the entire ASPATH consist of the specified ASN */
1213 bool aspath_single_asn_check(struct aspath
*aspath
, as_t asn
)
1215 struct assegment
*seg
;
1217 if (!(aspath
&& aspath
->segments
))
1220 seg
= aspath
->segments
;
1225 for (i
= 0; i
< seg
->length
; i
++) {
1226 if (seg
->as
[i
] != asn
)
1234 /* Replace all instances of the target ASN with our own ASN */
1235 struct aspath
*aspath_replace_specific_asn(struct aspath
*aspath
,
1236 as_t target_asn
, as_t our_asn
)
1239 struct assegment
*seg
;
1241 new = aspath_dup(aspath
);
1242 seg
= new->segments
;
1247 for (i
= 0; i
< seg
->length
; i
++) {
1248 if (seg
->as
[i
] == target_asn
)
1249 seg
->as
[i
] = our_asn
;
1254 aspath_str_update(new, false);
1258 /* Replace all private ASNs with our own ASN */
1259 struct aspath
*aspath_replace_private_asns(struct aspath
*aspath
, as_t asn
,
1263 struct assegment
*seg
;
1265 new = aspath_dup(aspath
);
1266 seg
= new->segments
;
1271 for (i
= 0; i
< seg
->length
; i
++) {
1272 /* Don't replace if public ASN or peer's ASN */
1273 if (BGP_AS_IS_PRIVATE(seg
->as
[i
])
1274 && (seg
->as
[i
] != peer_asn
))
1280 aspath_str_update(new, false);
1284 /* Remove all private ASNs */
1285 struct aspath
*aspath_remove_private_asns(struct aspath
*aspath
, as_t peer_asn
)
1288 struct assegment
*seg
;
1289 struct assegment
*new_seg
;
1290 struct assegment
*last_new_seg
;
1295 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
1299 last_new_seg
= NULL
;
1300 seg
= aspath
->segments
;
1304 for (i
= 0; i
< seg
->length
; i
++) {
1306 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1312 // The entire segment is public so copy it
1313 if (public == seg
->length
)
1314 new_seg
= assegment_dup(seg
);
1316 // The segment is a mix of public and private ASNs. Copy as many
1318 // there are public ASNs then come back and fill in only the
1321 new_seg
= assegment_new(seg
->type
, public);
1323 for (i
= 0; i
< seg
->length
; i
++) {
1324 // keep ASN if public or matches peer's ASN
1325 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])
1326 || (seg
->as
[i
] == peer_asn
)) {
1327 new_seg
->as
[j
] = seg
->as
[i
];
1333 // This is the first segment so set the aspath segments pointer
1336 new->segments
= new_seg
;
1338 last_new_seg
->next
= new_seg
;
1340 last_new_seg
= new_seg
;
1344 aspath_str_update(new, false);
1348 /* AS path confed check. If aspath contains confed set or sequence then return
1350 bool aspath_confed_check(struct aspath
*aspath
)
1352 struct assegment
*seg
;
1354 if (!(aspath
&& aspath
->segments
))
1357 seg
= aspath
->segments
;
1360 if (seg
->type
== AS_CONFED_SET
1361 || seg
->type
== AS_CONFED_SEQUENCE
)
1368 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1369 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1370 bool aspath_left_confed_check(struct aspath
*aspath
)
1373 if (!(aspath
&& aspath
->segments
))
1376 if ((aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1377 || (aspath
->segments
->type
== AS_CONFED_SET
))
1383 /* Merge as1 to as2. as2 should be uninterned aspath. */
1384 static struct aspath
*aspath_merge(struct aspath
*as1
, struct aspath
*as2
)
1386 struct assegment
*last
, *new;
1391 last
= new = assegment_dup_all(as1
->segments
);
1393 /* find the last valid segment */
1394 while (last
&& last
->next
)
1398 last
->next
= as2
->segments
;
1399 as2
->segments
= new;
1400 aspath_str_update(as2
, false);
1404 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1405 struct aspath
*aspath_prepend(struct aspath
*as1
, struct aspath
*as2
)
1407 struct assegment
*as1segtail
;
1408 struct assegment
*as2segtail
;
1409 struct assegment
*as2seghead
;
1414 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1415 if (as2
->segments
== NULL
) {
1416 as2
->segments
= assegment_dup_all(as1
->segments
);
1417 aspath_str_update(as2
, false);
1421 /* If as1 is empty AS, no prepending to do. */
1422 if (as1
->segments
== NULL
)
1425 /* find the tail as1's segment chain. */
1426 as1segtail
= as1
->segments
;
1427 while (as1segtail
&& as1segtail
->next
)
1428 as1segtail
= as1segtail
->next
;
1430 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1431 if (as1segtail
->type
== AS_SEQUENCE
1432 && as2
->segments
->type
== AS_CONFED_SEQUENCE
)
1433 as2
= aspath_delete_confed_seq(as2
);
1435 if (!as2
->segments
) {
1436 as2
->segments
= assegment_dup_all(as1
->segments
);
1437 aspath_str_update(as2
, false);
1441 /* Compare last segment type of as1 and first segment type of as2. */
1442 if (as1segtail
->type
!= as2
->segments
->type
)
1443 return aspath_merge(as1
, as2
);
1445 if (as1segtail
->type
== AS_SEQUENCE
) {
1446 /* We have two chains of segments, as1->segments and seg2,
1447 * and we have to attach them together, merging the attaching
1448 * segments together into one.
1450 * 1. dupe as1->segments onto head of as2
1451 * 2. merge seg2's asns onto last segment of this new chain
1452 * 3. attach chain after seg2
1456 as2seghead
= as2
->segments
;
1458 /* dupe as1 onto as2's head */
1459 as2segtail
= as2
->segments
= assegment_dup_all(as1
->segments
);
1461 /* refind the tail of as2 */
1462 while (as2segtail
&& as2segtail
->next
)
1463 as2segtail
= as2segtail
->next
;
1465 /* merge the old head, seg2, into tail, seg1 */
1466 assegment_append_asns(as2segtail
, as2seghead
->as
,
1467 as2seghead
->length
);
1470 * bypass the merged seg2, and attach any chain after it
1471 * to chain descending from as2's head
1474 as2segtail
->next
= as2seghead
->next
;
1476 /* as2->segments is now referenceless and useless */
1477 assegment_free(as2seghead
);
1479 /* we've now prepended as1's segment chain to as2, merging
1480 * the inbetween AS_SEQUENCE of seg2 in the process
1482 aspath_str_update(as2
, false);
1485 /* AS_SET merge code is needed at here. */
1486 return aspath_merge(as1
, as2
);
1488 /* XXX: Ermmm, what if as1 has multiple segments?? */
1493 /* Iterate over AS_PATH segments and wipe all occurrences of the
1494 * listed AS numbers. Hence some segments may lose some or even
1495 * all data on the way, the operation is implemented as a smarter
1496 * version of aspath_dup(), which allocates memory to hold the new
1497 * data, not the original. The new AS path is returned.
1499 struct aspath
*aspath_filter_exclude(struct aspath
*source
,
1500 struct aspath
*exclude_list
)
1502 struct assegment
*srcseg
, *exclseg
, *lastseg
;
1503 struct aspath
*newpath
;
1505 newpath
= aspath_new();
1508 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
) {
1509 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1510 struct assegment
*newseg
;
1512 /* Find out, how much ASns are we going to pick from this
1514 * We can't perform filtering right inline, because the size of
1515 * the new segment isn't known at the moment yet.
1517 for (i
= 0; i
< srcseg
->length
; i
++) {
1519 for (exclseg
= exclude_list
->segments
;
1520 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1521 for (y
= 0; y
< exclseg
->length
; y
++)
1522 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1524 // There's no sense in testing
1525 // the rest of exclusion list,
1532 /* newlen is now the number of ASns to copy */
1536 /* Actual copying. Allocate memory and iterate once more,
1537 * performing filtering. */
1538 newseg
= assegment_new(srcseg
->type
, newlen
);
1539 for (i
= 0; i
< srcseg
->length
; i
++) {
1541 for (exclseg
= exclude_list
->segments
;
1542 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1543 for (y
= 0; y
< exclseg
->length
; y
++)
1544 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1550 newseg
->as
[done
++] = srcseg
->as
[i
];
1552 /* At his point newlen must be equal to done, and both must be
1554 * the filtered segment to the gross result. */
1556 newpath
->segments
= newseg
;
1558 lastseg
->next
= newseg
;
1561 aspath_str_update(newpath
, false);
1562 /* We are happy returning even an empty AS_PATH, because the
1564 * might expect this very behaviour. There's a mean to avoid this, if
1566 * by having a match rule against certain AS_PATH regexps in the
1569 aspath_free(source
);
1573 /* Add specified AS to the leftmost of aspath. */
1574 static struct aspath
*aspath_add_asns(struct aspath
*aspath
, as_t asno
,
1575 uint8_t type
, unsigned num
)
1577 struct assegment
*assegment
= aspath
->segments
;
1580 if (assegment
&& assegment
->type
== type
) {
1581 /* extend existing segment */
1583 assegment_prepend_asns(aspath
->segments
, asno
, num
);
1585 /* prepend with new segment */
1586 struct assegment
*newsegment
= assegment_new(type
, num
);
1587 for (i
= 0; i
< num
; i
++)
1588 newsegment
->as
[i
] = asno
;
1590 /* insert potentially replacing empty segment */
1591 if (assegment
&& assegment
->length
== 0) {
1592 newsegment
->next
= assegment
->next
;
1593 assegment_free(assegment
);
1595 newsegment
->next
= assegment
;
1596 aspath
->segments
= newsegment
;
1599 aspath_str_update(aspath
, false);
1603 /* Add specified AS to the leftmost of aspath num times. */
1604 struct aspath
*aspath_add_seq_n(struct aspath
*aspath
, as_t asno
, unsigned num
)
1606 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, num
);
1609 /* Add specified AS to the leftmost of aspath. */
1610 struct aspath
*aspath_add_seq(struct aspath
*aspath
, as_t asno
)
1612 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, 1);
1615 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1616 as2's leftmost AS is same return 1. */
1617 bool aspath_cmp_left(const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1619 const struct assegment
*seg1
;
1620 const struct assegment
*seg2
;
1622 if (!(aspath1
&& aspath2
))
1625 seg1
= aspath1
->segments
;
1626 seg2
= aspath2
->segments
;
1628 /* If both paths are originated in this AS then we do want to compare
1633 /* find first non-confed segments for each */
1634 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1635 || (seg1
->type
== AS_CONFED_SET
)))
1638 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1639 || (seg2
->type
== AS_CONFED_SET
)))
1643 if (!(seg1
&& seg2
&& (seg1
->type
== AS_SEQUENCE
)
1644 && (seg2
->type
== AS_SEQUENCE
)))
1647 if (seg1
->as
[0] == seg2
->as
[0])
1653 /* Truncate an aspath after a number of hops, and put the hops remaining
1654 * at the front of another aspath. Needed for AS4 compat.
1656 * Returned aspath is a /new/ aspath, which should either by free'd or
1657 * interned by the caller, as desired.
1659 struct aspath
*aspath_reconcile_as4(struct aspath
*aspath
,
1660 struct aspath
*as4path
)
1662 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1663 struct aspath
*newpath
= NULL
, *mergedpath
;
1664 int hops
, cpasns
= 0;
1666 if (!aspath
|| !as4path
)
1669 seg
= aspath
->segments
;
1671 /* CONFEDs should get reconciled too.. */
1672 hops
= (aspath_count_hops(aspath
) + aspath_count_confeds(aspath
))
1673 - aspath_count_hops(as4path
);
1676 if (BGP_DEBUG(as4
, AS4
))
1678 EC_BGP_ASPATH_FEWER_HOPS
,
1679 "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1680 /* Something's gone wrong. The RFC says we should now ignore
1682 * which is daft behaviour - it contains vital loop-detection
1683 * information which must have been removed from AS_PATH.
1685 hops
= aspath_count_hops(aspath
);
1689 newpath
= aspath_dup(as4path
);
1690 aspath_str_update(newpath
, false);
1694 if (BGP_DEBUG(as4
, AS4
))
1696 "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1697 aspath
->str
, as4path
->str
);
1699 while (seg
&& hops
> 0) {
1700 switch (seg
->type
) {
1704 cpasns
= seg
->length
;
1706 case AS_CONFED_SEQUENCE
:
1707 /* Should never split a confed-sequence, if hop-count
1708 * suggests we must then something's gone wrong
1711 * Most important goal is to preserve AS_PATHs prime
1713 * as loop-detector, so we fudge the numbers so that the
1715 * confed-sequence is merged in.
1717 if (hops
< seg
->length
) {
1718 if (BGP_DEBUG(as4
, AS4
))
1720 "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls across 2/4 ASN boundary somewhere, broken..");
1725 cpasns
= MIN(seg
->length
, hops
);
1726 hops
-= seg
->length
;
1729 assert(cpasns
<= seg
->length
);
1731 newseg
= assegment_new(seg
->type
, 0);
1732 newseg
= assegment_append_asns(newseg
, seg
->as
, cpasns
);
1735 newpath
= aspath_new();
1736 newpath
->segments
= newseg
;
1738 prevseg
->next
= newseg
;
1744 /* We may be able to join some segments here, and we must
1745 * do this because... we want normalised aspaths in out hash
1746 * and we do not want to stumble in aspath_put.
1748 mergedpath
= aspath_merge(newpath
, aspath_dup(as4path
));
1749 aspath_free(newpath
);
1750 mergedpath
->segments
= assegment_normalise(mergedpath
->segments
);
1751 aspath_str_update(mergedpath
, false);
1753 if (BGP_DEBUG(as4
, AS4
))
1754 zlog_debug("[AS4] result of synthesizing is %s",
1760 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1761 as2's leftmost AS is same return 1. (confederation as-path
1763 bool aspath_cmp_left_confed(const struct aspath
*aspath1
,
1764 const struct aspath
*aspath2
)
1766 if (!(aspath1
&& aspath2
))
1769 if (!(aspath1
->segments
&& aspath2
->segments
))
1772 if ((aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1773 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
))
1776 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1782 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1783 * RFC 5065 section 4.1.c.1
1785 * 1) if any path segments of the AS_PATH are of the type
1786 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1787 * removed from the AS_PATH attribute, leaving the sanitized
1788 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1790 struct aspath
*aspath_delete_confed_seq(struct aspath
*aspath
)
1792 struct assegment
*seg
, *prev
, *next
;
1793 char removed_confed_segment
;
1795 if (!(aspath
&& aspath
->segments
))
1798 seg
= aspath
->segments
;
1799 removed_confed_segment
= 0;
1806 if (seg
->type
== AS_CONFED_SEQUENCE
1807 || seg
->type
== AS_CONFED_SET
) {
1808 /* This is the first segment in the aspath */
1809 if (aspath
->segments
== seg
)
1810 aspath
->segments
= seg
->next
;
1812 prev
->next
= seg
->next
;
1814 assegment_free(seg
);
1815 removed_confed_segment
= 1;
1822 if (removed_confed_segment
)
1823 aspath_str_update(aspath
, false);
1828 /* Add new AS number to the leftmost part of the aspath as
1829 AS_CONFED_SEQUENCE. */
1830 struct aspath
*aspath_add_confed_seq(struct aspath
*aspath
, as_t asno
)
1832 return aspath_add_asns(aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1835 /* Add new as value to as path structure. */
1836 static void aspath_as_add(struct aspath
*as
, as_t asno
)
1838 struct assegment
*seg
= as
->segments
;
1843 /* Last segment search procedure. */
1847 assegment_append_asns(seg
, &asno
, 1);
1850 /* Add new as segment to the as path. */
1851 static void aspath_segment_add(struct aspath
*as
, int type
)
1853 struct assegment
*seg
= as
->segments
;
1854 struct assegment
*new = assegment_new(type
, 0);
1864 struct aspath
*aspath_empty(void)
1866 return aspath_parse(NULL
, 0, 1); /* 32Bit ;-) */
1869 struct aspath
*aspath_empty_get(void)
1871 struct aspath
*aspath
;
1873 aspath
= aspath_new();
1874 aspath_make_str_count(aspath
, false);
1878 unsigned long aspath_count(void)
1880 return ashash
->count
;
1884 Theoretically, one as path can have:
1886 One BGP packet size should be less than 4096.
1887 One BGP attribute size should be less than 4096 - BGP header size.
1888 One BGP aspath size should be less than 4096 - BGP header size -
1889 BGP mandantry attribute size.
1892 /* AS path string lexical token enum. */
1897 as_token_confed_seq_start
,
1898 as_token_confed_seq_end
,
1899 as_token_confed_set_start
,
1900 as_token_confed_set_end
,
1904 /* Return next token and point for string parse. */
1905 static const char *aspath_gettoken(const char *buf
, enum as_token
*token
,
1906 unsigned long *asno
)
1908 const char *p
= buf
;
1910 /* Skip seperators (space for sequences, ',' for sets). */
1911 while (isspace((unsigned char)*p
) || *p
== ',')
1914 /* Check the end of the string and type specify characters
1920 *token
= as_token_set_start
;
1924 *token
= as_token_set_end
;
1928 *token
= as_token_confed_seq_start
;
1932 *token
= as_token_confed_seq_end
;
1936 *token
= as_token_confed_set_start
;
1940 *token
= as_token_confed_set_end
;
1945 /* Check actual AS value. */
1946 if (isdigit((unsigned char)*p
)) {
1949 *token
= as_token_asval
;
1953 while (isdigit((unsigned char)*p
)) {
1955 asval
+= (*p
- '0');
1962 /* There is no match then return unknown token. */
1963 *token
= as_token_unknown
;
1968 struct aspath
*aspath_str2aspath(const char *str
)
1970 enum as_token token
= as_token_unknown
;
1971 unsigned short as_type
;
1972 unsigned long asno
= 0;
1973 struct aspath
*aspath
;
1976 aspath
= aspath_new();
1978 /* We start default type as AS_SEQUENCE. */
1979 as_type
= AS_SEQUENCE
;
1982 while ((str
= aspath_gettoken(str
, &token
, &asno
)) != NULL
) {
1984 case as_token_asval
:
1986 aspath_segment_add(aspath
, as_type
);
1989 aspath_as_add(aspath
, asno
);
1991 case as_token_set_start
:
1993 aspath_segment_add(aspath
, as_type
);
1996 case as_token_set_end
:
1997 as_type
= AS_SEQUENCE
;
2000 case as_token_confed_seq_start
:
2001 as_type
= AS_CONFED_SEQUENCE
;
2002 aspath_segment_add(aspath
, as_type
);
2005 case as_token_confed_seq_end
:
2006 as_type
= AS_SEQUENCE
;
2009 case as_token_confed_set_start
:
2010 as_type
= AS_CONFED_SET
;
2011 aspath_segment_add(aspath
, as_type
);
2014 case as_token_confed_set_end
:
2015 as_type
= AS_SEQUENCE
;
2018 case as_token_unknown
:
2020 aspath_free(aspath
);
2025 aspath_make_str_count(aspath
, false);
2030 /* Make hash value by raw aspath data. */
2031 unsigned int aspath_key_make(const void *p
)
2033 const struct aspath
*aspath
= p
;
2034 unsigned int key
= 0;
2037 aspath_str_update((struct aspath
*)aspath
, false);
2039 key
= jhash(aspath
->str
, aspath
->str_len
, 2334325);
2044 /* If two aspath have same value then return 1 else return 0 */
2045 bool aspath_cmp(const void *arg1
, const void *arg2
)
2047 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2048 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2050 while (seg1
|| seg2
) {
2052 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2054 if (seg1
->type
!= seg2
->type
)
2056 if (seg1
->length
!= seg2
->length
)
2058 for (i
= 0; i
< seg1
->length
; i
++)
2059 if (seg1
->as
[i
] != seg2
->as
[i
])
2067 /* AS path hash initialize. */
2068 void aspath_init(void)
2070 ashash
= hash_create_size(32768, aspath_key_make
, aspath_cmp
,
2074 void aspath_finish(void)
2076 hash_clean(ashash
, (void (*)(void *))aspath_free
);
2081 stream_free(snmp_stream
);
2084 /* return and as path value */
2085 const char *aspath_print(struct aspath
*as
)
2087 return (as
? as
->str
: NULL
);
2090 /* Printing functions */
2091 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
2092 * AS_PATH wasn't empty.
2094 void aspath_print_vty(struct vty
*vty
, const char *format
, struct aspath
*as
,
2098 vty_out(vty
, format
, as
->str
);
2099 if (as
->str_len
&& strlen(suffix
))
2100 vty_out(vty
, "%s", suffix
);
2103 static void aspath_show_all_iterator(struct hash_bucket
*bucket
,
2108 as
= (struct aspath
*)bucket
->data
;
2110 vty_out(vty
, "[%p:%u] (%ld) ", (void *)bucket
, bucket
->key
, as
->refcnt
);
2111 vty_out(vty
, "%s\n", as
->str
);
2114 /* Print all aspath and hash information. This function is used from
2115 `show [ip] bgp paths' command. */
2116 void aspath_print_all_vty(struct vty
*vty
)
2118 hash_iterate(ashash
, (void (*)(struct hash_bucket
*,
2119 void *))aspath_show_all_iterator
,
2123 static struct aspath
*bgp_aggr_aspath_lookup(struct bgp_aggregate
*aggregate
,
2124 struct aspath
*aspath
)
2126 return hash_lookup(aggregate
->aspath_hash
, aspath
);
2129 static void *bgp_aggr_aspath_hash_alloc(void *p
)
2131 struct aspath
*ref
= (struct aspath
*)p
;
2132 struct aspath
*aspath
= NULL
;
2134 aspath
= aspath_dup(ref
);
2138 static void bgp_aggr_aspath_prepare(struct hash_bucket
*hb
, void *arg
)
2140 struct aspath
*hb_aspath
= hb
->data
;
2141 struct aspath
**aggr_aspath
= arg
;
2144 *aggr_aspath
= aspath_aggregate(*aggr_aspath
, hb_aspath
);
2146 *aggr_aspath
= aspath_dup(hb_aspath
);
2149 void bgp_aggr_aspath_remove(void *arg
)
2151 struct aspath
*aspath
= arg
;
2153 aspath_free(aspath
);
2156 void bgp_compute_aggregate_aspath(struct bgp_aggregate
*aggregate
,
2157 struct aspath
*aspath
)
2159 bgp_compute_aggregate_aspath_hash(aggregate
, aspath
);
2161 bgp_compute_aggregate_aspath_val(aggregate
);
2165 void bgp_compute_aggregate_aspath_hash(struct bgp_aggregate
*aggregate
,
2166 struct aspath
*aspath
)
2168 struct aspath
*aggr_aspath
= NULL
;
2170 if ((aggregate
== NULL
) || (aspath
== NULL
))
2173 /* Create hash if not already created.
2175 if (aggregate
->aspath_hash
== NULL
)
2176 aggregate
->aspath_hash
= hash_create(
2177 aspath_key_make
, aspath_cmp
,
2178 "BGP Aggregator as-path hash");
2180 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2181 if (aggr_aspath
== NULL
) {
2182 /* Insert as-path into hash.
2184 aggr_aspath
= hash_get(aggregate
->aspath_hash
, aspath
,
2185 bgp_aggr_aspath_hash_alloc
);
2188 /* Increment reference counter.
2190 aggr_aspath
->refcnt
++;
2193 void bgp_compute_aggregate_aspath_val(struct bgp_aggregate
*aggregate
)
2195 if (aggregate
== NULL
)
2197 /* Re-compute aggregate's as-path.
2199 if (aggregate
->aspath
) {
2200 aspath_free(aggregate
->aspath
);
2201 aggregate
->aspath
= NULL
;
2203 if (aggregate
->aspath_hash
2204 && aggregate
->aspath_hash
->count
) {
2205 hash_iterate(aggregate
->aspath_hash
,
2206 bgp_aggr_aspath_prepare
,
2207 &aggregate
->aspath
);
2211 void bgp_remove_aspath_from_aggregate(struct bgp_aggregate
*aggregate
,
2212 struct aspath
*aspath
)
2214 struct aspath
*aggr_aspath
= NULL
;
2215 struct aspath
*ret_aspath
= NULL
;
2218 || (!aggregate
->aspath_hash
)
2222 /* Look-up the aspath in the hash.
2224 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2226 aggr_aspath
->refcnt
--;
2228 if (aggr_aspath
->refcnt
== 0) {
2229 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2231 aspath_free(ret_aspath
);
2234 /* Remove aggregate's old as-path.
2236 aspath_free(aggregate
->aspath
);
2237 aggregate
->aspath
= NULL
;
2239 bgp_compute_aggregate_aspath_val(aggregate
);
2244 void bgp_remove_aspath_from_aggregate_hash(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
);