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
)
136 assegment_data_free(seg
->as
);
137 memset(seg
, 0xfe, sizeof(struct assegment
));
138 XFREE(MTYPE_AS_SEG
, seg
);
143 /* free entire chain of segments */
144 static void assegment_free_all(struct assegment
*seg
)
146 struct assegment
*prev
;
151 assegment_free(prev
);
155 /* Duplicate just the given assegment and its data */
156 static struct assegment
*assegment_dup(struct assegment
*seg
)
158 struct assegment
*new;
160 new = assegment_new(seg
->type
, seg
->length
);
161 memcpy(new->as
, seg
->as
, ASSEGMENT_DATA_SIZE(new->length
, 1));
166 /* Duplicate entire chain of assegments, return the head */
167 static struct assegment
*assegment_dup_all(struct assegment
*seg
)
169 struct assegment
*new = NULL
;
170 struct assegment
*head
= NULL
;
174 new->next
= assegment_dup(seg
);
177 head
= new = assegment_dup(seg
);
184 /* prepend the as number to given segment, given num of times */
185 static struct assegment
*assegment_prepend_asns(struct assegment
*seg
,
194 if (num
>= AS_SEGMENT_MAX
)
195 return seg
; /* we don't do huge prepends */
197 if ((newas
= assegment_data_new(seg
->length
+ num
)) == NULL
)
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 unsigned int 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)
916 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
917 * At the moment, we would write out a partial aspath, and our
919 * will complain and drop the session :-/
921 * The general assumption here is that many things tested will
922 * never happen. And, in real live, up to now, they have not.
924 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
)
925 <= 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
,
935 assegment_data_put(s
, (seg
->as
+ written
), AS_SEGMENT_MAX
,
937 written
+= AS_SEGMENT_MAX
;
938 bytes
+= ASSEGMENT_SIZE(AS_SEGMENT_MAX
,
942 /* write the final segment, probably is also the first
944 lenp
= assegment_header_put(s
, seg
->type
,
945 seg
->length
- written
);
946 assegment_data_put(s
, (seg
->as
+ written
),
947 seg
->length
- written
, use32bit
);
949 /* Sequence-type segments can be 'packed' together
950 * Case of a segment which was overlength and split up
951 * will be missed here, but that doesn't matter.
953 while (next
&& ASSEGMENTS_PACKABLE(seg
, next
)) {
954 /* NB: We should never normally get here given
956 * normalise aspath data when parse them.
958 * safe than sorry. We potentially could call
959 * assegment_normalise here instead, but it's
961 * easier to do it on the fly here rather than
963 * the segment list twice every time we write
968 /* Next segment's data can fit in this one */
969 assegment_data_put(s
, next
->as
, next
->length
,
972 /* update the length of the segment header */
973 stream_putc_at(s
, lenp
,
974 seg
->length
- written
976 asns_packed
+= next
->length
;
981 bytes
+= ASSEGMENT_SIZE(
982 seg
->length
- written
+ asns_packed
, use32bit
);
989 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
990 * We have no way to manage the storage, so we use a static stream
991 * wrapper around aspath_put.
993 uint8_t *aspath_snmp_pathseg(struct aspath
*as
, size_t *varlen
)
995 #define SNMP_PATHSEG_MAX 1024
998 snmp_stream
= stream_new(SNMP_PATHSEG_MAX
);
1000 stream_reset(snmp_stream
);
1006 aspath_put(snmp_stream
, as
, 0); /* use 16 bit for now here */
1008 *varlen
= stream_get_endp(snmp_stream
);
1009 return stream_pnt(snmp_stream
);
1012 #define min(A,B) ((A) < (B) ? (A) : (B))
1014 static struct assegment
*aspath_aggregate_as_set_add(struct aspath
*aspath
,
1015 struct assegment
*asset
,
1020 /* If this is first AS set member, create new as-set segment. */
1021 if (asset
== NULL
) {
1022 asset
= assegment_new(AS_SET
, 1);
1023 if (!aspath
->segments
)
1024 aspath
->segments
= asset
;
1026 struct assegment
*seg
= aspath
->segments
;
1031 asset
->type
= AS_SET
;
1035 /* Check this AS value already exists or not. */
1036 for (i
= 0; i
< asset
->length
; i
++)
1037 if (asset
->as
[i
] == as
)
1041 asset
->as
= XREALLOC(MTYPE_AS_SEG_DATA
, asset
->as
,
1042 asset
->length
* AS_VALUE_SIZE
);
1043 asset
->as
[asset
->length
- 1] = as
;
1050 /* Modify as1 using as2 for aggregation. */
1051 struct aspath
*aspath_aggregate(struct aspath
*as1
, struct aspath
*as2
)
1057 struct assegment
*seg1
= as1
->segments
;
1058 struct assegment
*seg2
= as2
->segments
;
1059 struct aspath
*aspath
= NULL
;
1060 struct assegment
*asset
= NULL
;
1061 struct assegment
*prevseg
= NULL
;
1063 /* First of all check common leading sequence. */
1064 while (seg1
&& seg2
) {
1065 /* Check segment type. */
1066 if (seg1
->type
!= seg2
->type
)
1069 /* Minimum segment length. */
1070 minlen
= min(seg1
->length
, seg2
->length
);
1072 for (match
= 0; match
< minlen
; match
++)
1073 if (seg1
->as
[match
] != seg2
->as
[match
])
1077 struct assegment
*seg
= assegment_new(seg1
->type
, 0);
1079 seg
= assegment_append_asns(seg
, seg1
->as
, match
);
1082 aspath
= aspath_new();
1083 aspath
->segments
= seg
;
1085 prevseg
->next
= seg
;
1090 if (match
!= minlen
|| match
!= seg1
->length
1091 || seg1
->length
!= seg2
->length
)
1093 /* We are moving on to the next segment to reset match */
1102 aspath
= aspath_new();
1104 /* Make as-set using rest of all information. */
1107 for (i
= from
; i
< seg1
->length
; i
++)
1108 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1117 for (i
= from
; i
< seg2
->length
; i
++)
1118 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1125 assegment_normalise(aspath
->segments
);
1126 aspath_str_update(aspath
, false);
1130 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1131 attribute, check the leftmost AS number in the AS_PATH attribute is
1132 or not the peer's AS number. */
1133 int aspath_firstas_check(struct aspath
*aspath
, as_t asno
)
1135 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1138 if (aspath
->segments
&& (aspath
->segments
->type
== AS_SEQUENCE
)
1139 && (aspath
->segments
->as
[0] == asno
))
1145 unsigned int aspath_get_first_as(struct aspath
*aspath
)
1147 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1150 return aspath
->segments
->as
[0];
1153 unsigned int aspath_get_last_as(struct aspath
*aspath
)
1156 unsigned int last_as
= 0;
1157 const struct assegment
*seg
;
1159 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1162 seg
= aspath
->segments
;
1165 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1166 for (i
= 0; i
< seg
->length
; i
++)
1167 last_as
= seg
->as
[i
];
1174 /* AS path loop check. If aspath contains asno then return >= 1. */
1175 int aspath_loop_check(struct aspath
*aspath
, as_t asno
)
1177 struct assegment
*seg
;
1180 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1183 seg
= aspath
->segments
;
1188 for (i
= 0; i
< seg
->length
; i
++)
1189 if (seg
->as
[i
] == asno
)
1197 /* When all of AS path is private AS return 1. */
1198 int aspath_private_as_check(struct aspath
*aspath
)
1200 struct assegment
*seg
;
1202 if (!(aspath
&& aspath
->segments
))
1205 seg
= aspath
->segments
;
1210 for (i
= 0; i
< seg
->length
; i
++) {
1211 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1219 /* Return True if the entire ASPATH consist of the specified ASN */
1220 int aspath_single_asn_check(struct aspath
*aspath
, as_t asn
)
1222 struct assegment
*seg
;
1224 if (!(aspath
&& aspath
->segments
))
1227 seg
= aspath
->segments
;
1232 for (i
= 0; i
< seg
->length
; i
++) {
1233 if (seg
->as
[i
] != asn
)
1241 /* Replace all instances of the target ASN with our own ASN */
1242 struct aspath
*aspath_replace_specific_asn(struct aspath
*aspath
,
1243 as_t target_asn
, as_t our_asn
)
1246 struct assegment
*seg
;
1248 new = aspath_dup(aspath
);
1249 seg
= new->segments
;
1254 for (i
= 0; i
< seg
->length
; i
++) {
1255 if (seg
->as
[i
] == target_asn
)
1256 seg
->as
[i
] = our_asn
;
1261 aspath_str_update(new, false);
1265 /* Replace all private ASNs with our own ASN */
1266 struct aspath
*aspath_replace_private_asns(struct aspath
*aspath
, as_t asn
,
1270 struct assegment
*seg
;
1272 new = aspath_dup(aspath
);
1273 seg
= new->segments
;
1278 for (i
= 0; i
< seg
->length
; i
++) {
1279 /* Don't replace if public ASN or peer's ASN */
1280 if (BGP_AS_IS_PRIVATE(seg
->as
[i
])
1281 && (seg
->as
[i
] != peer_asn
))
1287 aspath_str_update(new, false);
1291 /* Remove all private ASNs */
1292 struct aspath
*aspath_remove_private_asns(struct aspath
*aspath
, as_t peer_asn
)
1295 struct assegment
*seg
;
1296 struct assegment
*new_seg
;
1297 struct assegment
*last_new_seg
;
1302 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
1306 last_new_seg
= NULL
;
1307 seg
= aspath
->segments
;
1311 for (i
= 0; i
< seg
->length
; i
++) {
1313 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1319 // The entire segment is public so copy it
1320 if (public == seg
->length
)
1321 new_seg
= assegment_dup(seg
);
1323 // The segment is a mix of public and private ASNs. Copy as many
1325 // there are public ASNs then come back and fill in only the
1328 new_seg
= assegment_new(seg
->type
, public);
1330 for (i
= 0; i
< seg
->length
; i
++) {
1331 // keep ASN if public or matches peer's ASN
1332 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])
1333 || (seg
->as
[i
] == peer_asn
)) {
1334 new_seg
->as
[j
] = seg
->as
[i
];
1340 // This is the first segment so set the aspath segments pointer
1343 new->segments
= new_seg
;
1345 last_new_seg
->next
= new_seg
;
1347 last_new_seg
= new_seg
;
1351 aspath_str_update(new, false);
1355 /* AS path confed check. If aspath contains confed set or sequence then return
1357 int aspath_confed_check(struct aspath
*aspath
)
1359 struct assegment
*seg
;
1361 if (!(aspath
&& aspath
->segments
))
1364 seg
= aspath
->segments
;
1367 if (seg
->type
== AS_CONFED_SET
1368 || seg
->type
== AS_CONFED_SEQUENCE
)
1375 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1376 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1377 int aspath_left_confed_check(struct aspath
*aspath
)
1380 if (!(aspath
&& aspath
->segments
))
1383 if ((aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1384 || (aspath
->segments
->type
== AS_CONFED_SET
))
1390 /* Merge as1 to as2. as2 should be uninterned aspath. */
1391 static struct aspath
*aspath_merge(struct aspath
*as1
, struct aspath
*as2
)
1393 struct assegment
*last
, *new;
1398 last
= new = assegment_dup_all(as1
->segments
);
1400 /* find the last valid segment */
1401 while (last
&& last
->next
)
1405 last
->next
= as2
->segments
;
1406 as2
->segments
= new;
1407 aspath_str_update(as2
, false);
1411 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1412 struct aspath
*aspath_prepend(struct aspath
*as1
, struct aspath
*as2
)
1414 struct assegment
*as1segtail
;
1415 struct assegment
*as2segtail
;
1416 struct assegment
*as2seghead
;
1421 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1422 if (as2
->segments
== NULL
) {
1423 as2
->segments
= assegment_dup_all(as1
->segments
);
1424 aspath_str_update(as2
, false);
1428 /* If as1 is empty AS, no prepending to do. */
1429 if (as1
->segments
== NULL
)
1432 /* find the tail as1's segment chain. */
1433 as1segtail
= as1
->segments
;
1434 while (as1segtail
&& as1segtail
->next
)
1435 as1segtail
= as1segtail
->next
;
1437 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1438 if (as1segtail
->type
== AS_SEQUENCE
1439 && as2
->segments
->type
== AS_CONFED_SEQUENCE
)
1440 as2
= aspath_delete_confed_seq(as2
);
1442 if (!as2
->segments
) {
1443 as2
->segments
= assegment_dup_all(as1
->segments
);
1444 aspath_str_update(as2
, false);
1448 /* Compare last segment type of as1 and first segment type of as2. */
1449 if (as1segtail
->type
!= as2
->segments
->type
)
1450 return aspath_merge(as1
, as2
);
1452 if (as1segtail
->type
== AS_SEQUENCE
) {
1453 /* We have two chains of segments, as1->segments and seg2,
1454 * and we have to attach them together, merging the attaching
1455 * segments together into one.
1457 * 1. dupe as1->segments onto head of as2
1458 * 2. merge seg2's asns onto last segment of this new chain
1459 * 3. attach chain after seg2
1463 as2seghead
= as2
->segments
;
1465 /* dupe as1 onto as2's head */
1466 as2segtail
= as2
->segments
= assegment_dup_all(as1
->segments
);
1468 /* refind the tail of as2 */
1469 while (as2segtail
&& as2segtail
->next
)
1470 as2segtail
= as2segtail
->next
;
1472 /* merge the old head, seg2, into tail, seg1 */
1473 assegment_append_asns(as2segtail
, as2seghead
->as
,
1474 as2seghead
->length
);
1477 * bypass the merged seg2, and attach any chain after it
1478 * to chain descending from as2's head
1481 as2segtail
->next
= as2seghead
->next
;
1483 /* as2->segments is now referenceless and useless */
1484 assegment_free(as2seghead
);
1486 /* we've now prepended as1's segment chain to as2, merging
1487 * the inbetween AS_SEQUENCE of seg2 in the process
1489 aspath_str_update(as2
, false);
1492 /* AS_SET merge code is needed at here. */
1493 return aspath_merge(as1
, as2
);
1495 /* XXX: Ermmm, what if as1 has multiple segments?? */
1500 /* Iterate over AS_PATH segments and wipe all occurrences of the
1501 * listed AS numbers. Hence some segments may lose some or even
1502 * all data on the way, the operation is implemented as a smarter
1503 * version of aspath_dup(), which allocates memory to hold the new
1504 * data, not the original. The new AS path is returned.
1506 struct aspath
*aspath_filter_exclude(struct aspath
*source
,
1507 struct aspath
*exclude_list
)
1509 struct assegment
*srcseg
, *exclseg
, *lastseg
;
1510 struct aspath
*newpath
;
1512 newpath
= aspath_new();
1515 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
) {
1516 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1517 struct assegment
*newseg
;
1519 /* Find out, how much ASns are we going to pick from this
1521 * We can't perform filtering right inline, because the size of
1522 * the new segment isn't known at the moment yet.
1524 for (i
= 0; i
< srcseg
->length
; i
++) {
1526 for (exclseg
= exclude_list
->segments
;
1527 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1528 for (y
= 0; y
< exclseg
->length
; y
++)
1529 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1531 // There's no sense in testing
1532 // the rest of exclusion list,
1539 /* newlen is now the number of ASns to copy */
1543 /* Actual copying. Allocate memory and iterate once more,
1544 * performing filtering. */
1545 newseg
= assegment_new(srcseg
->type
, newlen
);
1546 for (i
= 0; i
< srcseg
->length
; i
++) {
1548 for (exclseg
= exclude_list
->segments
;
1549 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1550 for (y
= 0; y
< exclseg
->length
; y
++)
1551 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1557 newseg
->as
[done
++] = srcseg
->as
[i
];
1559 /* At his point newlen must be equal to done, and both must be
1561 * the filtered segment to the gross result. */
1563 newpath
->segments
= newseg
;
1565 lastseg
->next
= newseg
;
1568 aspath_str_update(newpath
, false);
1569 /* We are happy returning even an empty AS_PATH, because the
1571 * might expect this very behaviour. There's a mean to avoid this, if
1573 * by having a match rule against certain AS_PATH regexps in the
1576 aspath_free(source
);
1580 /* Add specified AS to the leftmost of aspath. */
1581 static struct aspath
*aspath_add_asns(struct aspath
*aspath
, as_t asno
,
1582 uint8_t type
, unsigned num
)
1584 struct assegment
*assegment
= aspath
->segments
;
1587 if (assegment
&& assegment
->type
== type
) {
1588 /* extend existing segment */
1590 assegment_prepend_asns(aspath
->segments
, asno
, num
);
1592 /* prepend with new segment */
1593 struct assegment
*newsegment
= assegment_new(type
, num
);
1594 for (i
= 0; i
< num
; i
++)
1595 newsegment
->as
[i
] = asno
;
1597 /* insert potentially replacing empty segment */
1598 if (assegment
&& assegment
->length
== 0) {
1599 newsegment
->next
= assegment
->next
;
1600 assegment_free(assegment
);
1602 newsegment
->next
= assegment
;
1603 aspath
->segments
= newsegment
;
1606 aspath_str_update(aspath
, false);
1610 /* Add specified AS to the leftmost of aspath num times. */
1611 struct aspath
*aspath_add_seq_n(struct aspath
*aspath
, as_t asno
, unsigned num
)
1613 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, num
);
1616 /* Add specified AS to the leftmost of aspath. */
1617 struct aspath
*aspath_add_seq(struct aspath
*aspath
, as_t asno
)
1619 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, 1);
1622 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1623 as2's leftmost AS is same return 1. */
1624 int aspath_cmp_left(const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1626 const struct assegment
*seg1
;
1627 const struct assegment
*seg2
;
1629 if (!(aspath1
&& aspath2
))
1632 seg1
= aspath1
->segments
;
1633 seg2
= aspath2
->segments
;
1635 /* If both paths are originated in this AS then we do want to compare
1640 /* find first non-confed segments for each */
1641 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1642 || (seg1
->type
== AS_CONFED_SET
)))
1645 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1646 || (seg2
->type
== AS_CONFED_SET
)))
1650 if (!(seg1
&& seg2
&& (seg1
->type
== AS_SEQUENCE
)
1651 && (seg2
->type
== AS_SEQUENCE
)))
1654 if (seg1
->as
[0] == seg2
->as
[0])
1660 /* Truncate an aspath after a number of hops, and put the hops remaining
1661 * at the front of another aspath. Needed for AS4 compat.
1663 * Returned aspath is a /new/ aspath, which should either by free'd or
1664 * interned by the caller, as desired.
1666 struct aspath
*aspath_reconcile_as4(struct aspath
*aspath
,
1667 struct aspath
*as4path
)
1669 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1670 struct aspath
*newpath
= NULL
, *mergedpath
;
1671 int hops
, cpasns
= 0;
1673 if (!aspath
|| !as4path
)
1676 seg
= aspath
->segments
;
1678 /* CONFEDs should get reconciled too.. */
1679 hops
= (aspath_count_hops(aspath
) + aspath_count_confeds(aspath
))
1680 - aspath_count_hops(as4path
);
1683 if (BGP_DEBUG(as4
, AS4
))
1685 EC_BGP_ASPATH_FEWER_HOPS
,
1686 "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1687 /* Something's gone wrong. The RFC says we should now ignore
1689 * which is daft behaviour - it contains vital loop-detection
1690 * information which must have been removed from AS_PATH.
1692 hops
= aspath_count_hops(aspath
);
1696 newpath
= aspath_dup(as4path
);
1697 aspath_str_update(newpath
, false);
1701 if (BGP_DEBUG(as4
, AS4
))
1703 "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1704 aspath
->str
, as4path
->str
);
1706 while (seg
&& hops
> 0) {
1707 switch (seg
->type
) {
1711 cpasns
= seg
->length
;
1713 case AS_CONFED_SEQUENCE
:
1714 /* Should never split a confed-sequence, if hop-count
1715 * suggests we must then something's gone wrong
1718 * Most important goal is to preserve AS_PATHs prime
1720 * as loop-detector, so we fudge the numbers so that the
1722 * confed-sequence is merged in.
1724 if (hops
< seg
->length
) {
1725 if (BGP_DEBUG(as4
, AS4
))
1727 "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1728 " across 2/4 ASN boundary somewhere, broken..");
1733 cpasns
= MIN(seg
->length
, hops
);
1734 hops
-= seg
->length
;
1737 assert(cpasns
<= seg
->length
);
1739 newseg
= assegment_new(seg
->type
, 0);
1740 newseg
= assegment_append_asns(newseg
, seg
->as
, cpasns
);
1743 newpath
= aspath_new();
1744 newpath
->segments
= newseg
;
1746 prevseg
->next
= newseg
;
1752 /* We may be able to join some segments here, and we must
1753 * do this because... we want normalised aspaths in out hash
1754 * and we do not want to stumble in aspath_put.
1756 mergedpath
= aspath_merge(newpath
, aspath_dup(as4path
));
1757 aspath_free(newpath
);
1758 mergedpath
->segments
= assegment_normalise(mergedpath
->segments
);
1759 aspath_str_update(mergedpath
, false);
1761 if (BGP_DEBUG(as4
, AS4
))
1762 zlog_debug("[AS4] result of synthesizing is %s",
1768 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1769 as2's leftmost AS is same return 1. (confederation as-path
1771 bool aspath_cmp_left_confed(const struct aspath
*aspath1
,
1772 const struct aspath
*aspath2
)
1774 if (!(aspath1
&& aspath2
))
1777 if (!(aspath1
->segments
&& aspath2
->segments
))
1780 if ((aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1781 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
))
1784 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1790 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1791 * RFC 5065 section 4.1.c.1
1793 * 1) if any path segments of the AS_PATH are of the type
1794 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1795 * removed from the AS_PATH attribute, leaving the sanitized
1796 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1798 struct aspath
*aspath_delete_confed_seq(struct aspath
*aspath
)
1800 struct assegment
*seg
, *prev
, *next
;
1801 char removed_confed_segment
;
1803 if (!(aspath
&& aspath
->segments
))
1806 seg
= aspath
->segments
;
1807 removed_confed_segment
= 0;
1814 if (seg
->type
== AS_CONFED_SEQUENCE
1815 || seg
->type
== AS_CONFED_SET
) {
1816 /* This is the first segment in the aspath */
1817 if (aspath
->segments
== seg
)
1818 aspath
->segments
= seg
->next
;
1820 prev
->next
= seg
->next
;
1822 assegment_free(seg
);
1823 removed_confed_segment
= 1;
1830 if (removed_confed_segment
)
1831 aspath_str_update(aspath
, false);
1836 /* Add new AS number to the leftmost part of the aspath as
1837 AS_CONFED_SEQUENCE. */
1838 struct aspath
*aspath_add_confed_seq(struct aspath
*aspath
, as_t asno
)
1840 return aspath_add_asns(aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1843 /* Add new as value to as path structure. */
1844 static void aspath_as_add(struct aspath
*as
, as_t asno
)
1846 struct assegment
*seg
= as
->segments
;
1851 /* Last segment search procedure. */
1855 assegment_append_asns(seg
, &asno
, 1);
1858 /* Add new as segment to the as path. */
1859 static void aspath_segment_add(struct aspath
*as
, int type
)
1861 struct assegment
*seg
= as
->segments
;
1862 struct assegment
*new = assegment_new(type
, 0);
1872 struct aspath
*aspath_empty(void)
1874 return aspath_parse(NULL
, 0, 1); /* 32Bit ;-) */
1877 struct aspath
*aspath_empty_get(void)
1879 struct aspath
*aspath
;
1881 aspath
= aspath_new();
1882 aspath_make_str_count(aspath
, false);
1886 unsigned long aspath_count(void)
1888 return ashash
->count
;
1892 Theoretically, one as path can have:
1894 One BGP packet size should be less than 4096.
1895 One BGP attribute size should be less than 4096 - BGP header size.
1896 One BGP aspath size should be less than 4096 - BGP header size -
1897 BGP mandantry attribute size.
1900 /* AS path string lexical token enum. */
1905 as_token_confed_seq_start
,
1906 as_token_confed_seq_end
,
1907 as_token_confed_set_start
,
1908 as_token_confed_set_end
,
1912 /* Return next token and point for string parse. */
1913 static const char *aspath_gettoken(const char *buf
, enum as_token
*token
,
1914 unsigned long *asno
)
1916 const char *p
= buf
;
1918 /* Skip seperators (space for sequences, ',' for sets). */
1919 while (isspace((unsigned char)*p
) || *p
== ',')
1922 /* Check the end of the string and type specify characters
1928 *token
= as_token_set_start
;
1932 *token
= as_token_set_end
;
1936 *token
= as_token_confed_seq_start
;
1940 *token
= as_token_confed_seq_end
;
1944 *token
= as_token_confed_set_start
;
1948 *token
= as_token_confed_set_end
;
1953 /* Check actual AS value. */
1954 if (isdigit((unsigned char)*p
)) {
1957 *token
= as_token_asval
;
1961 while (isdigit((unsigned char)*p
)) {
1963 asval
+= (*p
- '0');
1970 /* There is no match then return unknown token. */
1971 *token
= as_token_unknown
;
1976 struct aspath
*aspath_str2aspath(const char *str
)
1978 enum as_token token
= as_token_unknown
;
1979 unsigned short as_type
;
1980 unsigned long asno
= 0;
1981 struct aspath
*aspath
;
1984 aspath
= aspath_new();
1986 /* We start default type as AS_SEQUENCE. */
1987 as_type
= AS_SEQUENCE
;
1990 while ((str
= aspath_gettoken(str
, &token
, &asno
)) != NULL
) {
1992 case as_token_asval
:
1994 aspath_segment_add(aspath
, as_type
);
1997 aspath_as_add(aspath
, asno
);
1999 case as_token_set_start
:
2001 aspath_segment_add(aspath
, as_type
);
2004 case as_token_set_end
:
2005 as_type
= AS_SEQUENCE
;
2008 case as_token_confed_seq_start
:
2009 as_type
= AS_CONFED_SEQUENCE
;
2010 aspath_segment_add(aspath
, as_type
);
2013 case as_token_confed_seq_end
:
2014 as_type
= AS_SEQUENCE
;
2017 case as_token_confed_set_start
:
2018 as_type
= AS_CONFED_SET
;
2019 aspath_segment_add(aspath
, as_type
);
2022 case as_token_confed_set_end
:
2023 as_type
= AS_SEQUENCE
;
2026 case as_token_unknown
:
2028 aspath_free(aspath
);
2033 aspath_make_str_count(aspath
, false);
2038 /* Make hash value by raw aspath data. */
2039 unsigned int aspath_key_make(const void *p
)
2041 const struct aspath
*aspath
= p
;
2042 unsigned int key
= 0;
2045 aspath_str_update((struct aspath
*)aspath
, false);
2047 key
= jhash(aspath
->str
, aspath
->str_len
, 2334325);
2052 /* If two aspath have same value then return 1 else return 0 */
2053 bool aspath_cmp(const void *arg1
, const void *arg2
)
2055 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2056 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2058 while (seg1
|| seg2
) {
2060 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2062 if (seg1
->type
!= seg2
->type
)
2064 if (seg1
->length
!= seg2
->length
)
2066 for (i
= 0; i
< seg1
->length
; i
++)
2067 if (seg1
->as
[i
] != seg2
->as
[i
])
2075 /* AS path hash initialize. */
2076 void aspath_init(void)
2078 ashash
= hash_create_size(32768, aspath_key_make
, aspath_cmp
,
2082 void aspath_finish(void)
2084 hash_clean(ashash
, (void (*)(void *))aspath_free
);
2089 stream_free(snmp_stream
);
2092 /* return and as path value */
2093 const char *aspath_print(struct aspath
*as
)
2095 return (as
? as
->str
: NULL
);
2098 /* Printing functions */
2099 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
2100 * AS_PATH wasn't empty.
2102 void aspath_print_vty(struct vty
*vty
, const char *format
, struct aspath
*as
,
2106 vty_out(vty
, format
, as
->str
);
2107 if (as
->str_len
&& strlen(suffix
))
2108 vty_out(vty
, "%s", suffix
);
2111 static void aspath_show_all_iterator(struct hash_bucket
*bucket
,
2116 as
= (struct aspath
*)bucket
->data
;
2118 vty_out(vty
, "[%p:%u] (%ld) ", (void *)bucket
, bucket
->key
, as
->refcnt
);
2119 vty_out(vty
, "%s\n", as
->str
);
2122 /* Print all aspath and hash information. This function is used from
2123 `show [ip] bgp paths' command. */
2124 void aspath_print_all_vty(struct vty
*vty
)
2126 hash_iterate(ashash
, (void (*)(struct hash_bucket
*,
2127 void *))aspath_show_all_iterator
,
2131 static struct aspath
*bgp_aggr_aspath_lookup(struct bgp_aggregate
*aggregate
,
2132 struct aspath
*aspath
)
2134 return hash_lookup(aggregate
->aspath_hash
, aspath
);
2137 static void *bgp_aggr_aspath_hash_alloc(void *p
)
2139 struct aspath
*ref
= (struct aspath
*)p
;
2140 struct aspath
*aspath
= NULL
;
2142 aspath
= aspath_dup(ref
);
2146 static void bgp_aggr_aspath_prepare(struct hash_bucket
*hb
, void *arg
)
2148 struct aspath
*hb_aspath
= hb
->data
;
2149 struct aspath
**aggr_aspath
= arg
;
2152 *aggr_aspath
= aspath_aggregate(*aggr_aspath
, hb_aspath
);
2154 *aggr_aspath
= aspath_dup(hb_aspath
);
2157 void bgp_aggr_aspath_remove(void *arg
)
2159 struct aspath
*aspath
= arg
;
2161 aspath_free(aspath
);
2164 void bgp_compute_aggregate_aspath(struct bgp_aggregate
*aggregate
,
2165 struct aspath
*aspath
)
2167 bgp_compute_aggregate_aspath_hash(aggregate
, aspath
);
2169 bgp_compute_aggregate_aspath_val(aggregate
);
2173 void bgp_compute_aggregate_aspath_hash(struct bgp_aggregate
*aggregate
,
2174 struct aspath
*aspath
)
2176 struct aspath
*aggr_aspath
= NULL
;
2178 if ((aggregate
== NULL
) || (aspath
== NULL
))
2181 /* Create hash if not already created.
2183 if (aggregate
->aspath_hash
== NULL
)
2184 aggregate
->aspath_hash
= hash_create(
2185 aspath_key_make
, aspath_cmp
,
2186 "BGP Aggregator as-path hash");
2188 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2189 if (aggr_aspath
== NULL
) {
2190 /* Insert as-path into hash.
2192 aggr_aspath
= hash_get(aggregate
->aspath_hash
, aspath
,
2193 bgp_aggr_aspath_hash_alloc
);
2196 /* Increment reference counter.
2198 aggr_aspath
->refcnt
++;
2201 void bgp_compute_aggregate_aspath_val(struct bgp_aggregate
*aggregate
)
2203 if (aggregate
== NULL
)
2205 /* Re-compute aggregate's as-path.
2207 if (aggregate
->aspath
) {
2208 aspath_free(aggregate
->aspath
);
2209 aggregate
->aspath
= NULL
;
2211 if (aggregate
->aspath_hash
2212 && aggregate
->aspath_hash
->count
) {
2213 hash_iterate(aggregate
->aspath_hash
,
2214 bgp_aggr_aspath_prepare
,
2215 &aggregate
->aspath
);
2219 void bgp_remove_aspath_from_aggregate(struct bgp_aggregate
*aggregate
,
2220 struct aspath
*aspath
)
2222 struct aspath
*aggr_aspath
= NULL
;
2223 struct aspath
*ret_aspath
= NULL
;
2226 || (!aggregate
->aspath_hash
)
2230 /* Look-up the aspath in the hash.
2232 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2234 aggr_aspath
->refcnt
--;
2236 if (aggr_aspath
->refcnt
== 0) {
2237 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2239 aspath_free(ret_aspath
);
2242 /* Remove aggregate's old as-path.
2244 aspath_free(aggregate
->aspath
);
2245 aggregate
->aspath
= NULL
;
2247 bgp_compute_aggregate_aspath_val(aggregate
);
2252 void bgp_remove_aspath_from_aggregate_hash(struct bgp_aggregate
*aggregate
,
2253 struct aspath
*aspath
)
2255 struct aspath
*aggr_aspath
= NULL
;
2256 struct aspath
*ret_aspath
= NULL
;
2259 || (!aggregate
->aspath_hash
)
2263 /* Look-up the aspath in the hash.
2265 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2267 aggr_aspath
->refcnt
--;
2269 if (aggr_aspath
->refcnt
== 0) {
2270 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2272 aspath_free(ret_aspath
);