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 if ((newas
= assegment_data_new(seg
->length
+ num
)) == NULL
)
199 for (i
= 0; i
< num
; i
++)
202 memcpy(newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE(seg
->length
, 1));
203 assegment_data_free(seg
->as
);
210 /* append given array of as numbers to the segment */
211 static struct assegment
*assegment_append_asns(struct assegment
*seg
,
212 as_t
*asnos
, int num
)
219 newas
= XREALLOC(MTYPE_AS_SEG_DATA
, seg
->as
,
220 ASSEGMENT_DATA_SIZE(seg
->length
+ num
, 1));
223 memcpy(seg
->as
+ seg
->length
, asnos
,
224 ASSEGMENT_DATA_SIZE(num
, 1));
229 static int int_cmp(const void *p1
, const void *p2
)
231 const as_t
*as1
= p1
;
232 const as_t
*as2
= p2
;
234 return (*as1
== *as2
) ? 0 : ((*as1
> *as2
) ? 1 : -1);
237 /* normalise the segment.
238 * In particular, merge runs of AS_SEQUENCEs into one segment
239 * Internally, we do not care about the wire segment length limit, and
240 * we want each distinct AS_PATHs to have the exact same internal
241 * representation - eg, so that our hashing actually works..
243 static struct assegment
*assegment_normalise(struct assegment
*head
)
245 struct assegment
*seg
= head
, *pin
;
246 struct assegment
*tmp
;
254 /* Sort values SET segments, for determinism in paths to aid
255 * creation of hash values / path comparisons
256 * and because it helps other lesser implementations ;)
258 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
) {
262 qsort(seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
265 for (i
= 1; i
< seg
->length
; i
++) {
266 if (seg
->as
[tail
] == seg
->as
[i
])
271 seg
->as
[tail
] = seg
->as
[i
];
273 /* seg->length can be 0.. */
275 seg
->length
= tail
+ 1;
278 /* read ahead from the current, pinned segment while the
280 * are packable/mergeable. Append all following packable
282 * to the segment we have pinned and remove these appended
285 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
)) {
289 /* append the next sequence to the pinned sequence */
290 pin
= assegment_append_asns(pin
, seg
->as
, seg
->length
);
292 /* bypass the next sequence */
293 pin
->next
= seg
->next
;
295 /* get rid of the now referenceless segment */
304 static struct aspath
*aspath_new(void)
306 return XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
309 /* Free AS path structure. */
310 void aspath_free(struct aspath
*aspath
)
314 if (aspath
->segments
)
315 assegment_free_all(aspath
->segments
);
316 XFREE(MTYPE_AS_STR
, aspath
->str
);
319 json_object_free(aspath
->json
);
323 XFREE(MTYPE_AS_PATH
, aspath
);
326 /* Unintern aspath from AS path bucket. */
327 void aspath_unintern(struct aspath
**aspath
)
330 struct aspath
*asp
= *aspath
;
335 if (asp
->refcnt
== 0) {
336 /* This aspath must exist in aspath hash table. */
337 ret
= hash_release(ashash
, asp
);
344 /* Return the start or end delimiters for a particular Segment type */
345 #define AS_SEG_START 0
347 static char aspath_delimiter_char(uint8_t type
, uint8_t which
)
354 } aspath_delim_char
[] = {{AS_SET
, '{', '}'},
355 {AS_CONFED_SET
, '[', ']'},
356 {AS_CONFED_SEQUENCE
, '(', ')'},
359 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++) {
360 if (aspath_delim_char
[i
].type
== type
) {
361 if (which
== AS_SEG_START
)
362 return aspath_delim_char
[i
].start
;
363 else if (which
== AS_SEG_END
)
364 return aspath_delim_char
[i
].end
;
370 /* countup asns from this segment and index onward */
371 static int assegment_count_asns(struct assegment
*seg
, int from
)
376 count
+= seg
->length
;
378 count
+= (seg
->length
- from
);
386 unsigned int aspath_count_confeds(struct aspath
*aspath
)
389 struct assegment
*seg
= aspath
->segments
;
392 if (seg
->type
== AS_CONFED_SEQUENCE
)
393 count
+= seg
->length
;
394 else if (seg
->type
== AS_CONFED_SET
)
402 unsigned int aspath_count_hops(const struct aspath
*aspath
)
405 struct assegment
*seg
= aspath
->segments
;
408 if (seg
->type
== AS_SEQUENCE
)
409 count
+= seg
->length
;
410 else if (seg
->type
== AS_SET
)
418 /* Check if aspath has AS_SET or AS_CONFED_SET */
419 bool aspath_check_as_sets(struct aspath
*aspath
)
421 struct assegment
*seg
= aspath
->segments
;
424 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
)
431 /* Check if aspath has BGP_AS_ZERO */
432 bool aspath_check_as_zero(struct aspath
*aspath
)
434 struct assegment
*seg
= aspath
->segments
;
438 for (i
= 0; i
< seg
->length
; i
++)
439 if (seg
->as
[i
] == BGP_AS_ZERO
)
447 /* Estimate size aspath /might/ take if encoded into an
450 * This is a quick estimate, not definitive! aspath_put()
451 * may return a different number!!
453 unsigned int aspath_size(struct aspath
*aspath
)
456 struct assegment
*seg
= aspath
->segments
;
459 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
465 /* Return highest public ASN in path */
466 as_t
aspath_highest(struct aspath
*aspath
)
468 struct assegment
*seg
= aspath
->segments
;
473 for (i
= 0; i
< seg
->length
; i
++)
474 if (seg
->as
[i
] > highest
475 && !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
476 highest
= seg
->as
[i
];
482 /* Return the left-most ASN in path */
483 as_t
aspath_leftmost(struct aspath
*aspath
)
485 struct assegment
*seg
= aspath
->segments
;
488 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
489 leftmost
= seg
->as
[0];
494 /* Return 1 if there are any 4-byte ASes in the path */
495 bool aspath_has_as4(struct aspath
*aspath
)
497 struct assegment
*seg
= aspath
->segments
;
501 for (i
= 0; i
< seg
->length
; i
++)
502 if (seg
->as
[i
] > BGP_AS_MAX
)
509 /* Convert aspath structure to string expression. */
510 static void aspath_make_str_count(struct aspath
*as
, bool make_json
)
512 struct assegment
*seg
;
516 json_object
*jaspath_segments
= NULL
;
517 json_object
*jseg
= NULL
;
518 json_object
*jseg_list
= NULL
;
521 as
->json
= json_object_new_object();
522 jaspath_segments
= json_object_new_array();
528 json_object_string_add(as
->json
, "string", "Local");
529 json_object_object_add(as
->json
, "segments",
531 json_object_int_add(as
->json
, "length", 0);
533 as
->str
= XMALLOC(MTYPE_AS_STR
, 1);
541 /* ASN takes 5 to 10 chars plus seperator, see below.
542 * If there is one differing segment type, we need an additional
543 * 2 chars for segment delimiters, and the final '\0'.
544 * Hopefully this is large enough to avoid hitting the realloc
545 * code below for most common sequences.
547 * This was changed to 10 after the well-known BGP assertion, which
548 * had hit some parts of the Internet in May of 2009.
550 #define ASN_STR_LEN (10 + 1)
551 str_size
= MAX(assegment_count_asns(seg
, 0) * ASN_STR_LEN
+ 2 + 1,
552 ASPATH_STR_DEFAULT_LEN
);
553 str_buf
= XMALLOC(MTYPE_AS_STR
, str_size
);
559 /* Check AS type validity. Set seperator for segment */
566 case AS_CONFED_SEQUENCE
:
570 XFREE(MTYPE_AS_STR
, str_buf
);
573 json_object_free(as
->json
);
579 /* We might need to increase str_buf, particularly if path has
580 * differing segments types, our initial guesstimate above will
581 * have been wrong. Need 10 chars for ASN, a seperator each and
582 * potentially two segment delimiters, plus a space between each
583 * segment and trailing zero.
585 * This definitely didn't work with the value of 5 bytes and
588 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
589 if ((len
+ SEGMENT_STR_LEN(seg
)) > str_size
) {
590 str_size
= len
+ SEGMENT_STR_LEN(seg
);
591 str_buf
= XREALLOC(MTYPE_AS_STR
, str_buf
, str_size
);
594 #undef SEGMENT_STR_LEN
596 if (seg
->type
!= AS_SEQUENCE
)
598 str_buf
+ len
, str_size
- len
, "%c",
599 aspath_delimiter_char(seg
->type
, AS_SEG_START
));
602 jseg_list
= json_object_new_array();
604 /* write out the ASNs, with their seperators, bar the last one*/
605 for (i
= 0; i
< seg
->length
; i
++) {
607 json_object_array_add(
609 json_object_new_int64(seg
->as
[i
]));
611 len
+= snprintf(str_buf
+ len
, str_size
- len
, "%u",
614 if (i
< (seg
->length
- 1))
615 len
+= snprintf(str_buf
+ len
, str_size
- len
,
620 jseg
= json_object_new_object();
621 json_object_string_add(
623 aspath_segment_type_str
[seg
->type
]);
624 json_object_object_add(jseg
, "list", jseg_list
);
625 json_object_array_add(jaspath_segments
, jseg
);
628 if (seg
->type
!= AS_SEQUENCE
)
630 str_buf
+ len
, str_size
- len
, "%c",
631 aspath_delimiter_char(seg
->type
, AS_SEG_END
));
633 len
+= snprintf(str_buf
+ len
, str_size
- len
, " ");
638 assert(len
< str_size
);
645 json_object_string_add(as
->json
, "string", str_buf
);
646 json_object_object_add(as
->json
, "segments", jaspath_segments
);
647 json_object_int_add(as
->json
, "length", aspath_count_hops(as
));
653 void aspath_str_update(struct aspath
*as
, bool make_json
)
655 XFREE(MTYPE_AS_STR
, as
->str
);
658 json_object_free(as
->json
);
662 aspath_make_str_count(as
, make_json
);
665 /* Intern allocated AS path. */
666 struct aspath
*aspath_intern(struct aspath
*aspath
)
670 /* Assert this AS path structure is not interned and has the string
671 representation built. */
672 assert(aspath
->refcnt
== 0);
675 /* Check AS path hash. */
676 find
= hash_get(ashash
, aspath
, hash_alloc_intern
);
685 /* Duplicate aspath structure. Created same aspath structure but
686 reference count and AS path string is cleared. */
687 struct aspath
*aspath_dup(struct aspath
*aspath
)
689 unsigned short buflen
= aspath
->str_len
+ 1;
692 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
695 if (aspath
->segments
)
696 new->segments
= assegment_dup_all(aspath
->segments
);
701 new->str
= XMALLOC(MTYPE_AS_STR
, buflen
);
702 new->str_len
= aspath
->str_len
;
704 /* copy the string data */
705 if (aspath
->str_len
> 0)
706 memcpy(new->str
, aspath
->str
, buflen
);
713 static void *aspath_hash_alloc(void *arg
)
715 const struct aspath
*aspath
= arg
;
718 /* Malformed AS path value. */
721 /* New aspath structure is needed. */
722 new = XMALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
724 /* Reuse segments and string representation */
726 new->segments
= aspath
->segments
;
727 new->str
= aspath
->str
;
728 new->str_len
= aspath
->str_len
;
729 new->json
= aspath
->json
;
734 /* parse as-segment byte stream in struct assegment */
735 static int assegments_parse(struct stream
*s
, size_t length
,
736 struct assegment
**result
, int use32bit
)
738 struct assegment_header segh
;
739 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
742 /* empty aspath (ie iBGP or somesuch) */
746 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
748 "[AS4SEG] Parse aspath segment: got total byte length %lu",
749 (unsigned long)length
);
751 if ((STREAM_READABLE(s
) < length
)
752 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
753 || (length
% AS16_VALUE_SIZE
))
756 while (bytes
< length
) {
760 if ((length
- bytes
) <= AS_HEADER_SIZE
) {
762 assegment_free_all(head
);
766 /* softly softly, get the header first on its own */
767 segh
.type
= stream_getc(s
);
768 segh
.length
= stream_getc(s
);
770 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
772 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
774 "[AS4SEG] Parse aspath segment: got type %d, length %d",
775 segh
.type
, segh
.length
);
778 if (((bytes
+ seg_size
) > length
)
779 /* 1771bis 4.3b: seg length contains one or more */
780 || (segh
.length
== 0)
781 /* Paranoia in case someone changes type of segment length.
782 * Shift both values by 0x10 to make the comparison operate
783 * on more, than 8 bits (otherwise it's a warning, bug
786 || ((sizeof(segh
.length
) > 1)
787 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
))) {
789 assegment_free_all(head
);
796 case AS_CONFED_SEQUENCE
:
801 assegment_free_all(head
);
805 /* now its safe to trust lengths */
806 seg
= assegment_new(segh
.type
, segh
.length
);
810 else /* it's the first segment */
813 for (i
= 0; i
< segh
.length
; i
++)
815 (use32bit
) ? stream_getl(s
) : stream_getw(s
);
819 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
821 "[AS4SEG] Parse aspath segment: Bytes now: %lu",
822 (unsigned long)bytes
);
827 *result
= assegment_normalise(head
);
831 /* AS path parse function. pnt is a pointer to byte stream and length
832 is length of byte stream. If there is same AS path in the the AS
833 path hash then return it else make new AS path structure.
835 On error NULL is returned.
837 struct aspath
*aspath_parse(struct stream
*s
, size_t length
, int use32bit
)
842 /* If length is odd it's malformed AS path. */
843 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
844 * otherwise its malformed when length is larger than 2 and (length-2)
845 * is not dividable by 4.
846 * But... this time we're lazy
848 if (length
% AS16_VALUE_SIZE
)
851 memset(&as
, 0, sizeof(struct aspath
));
852 if (assegments_parse(s
, length
, &as
.segments
, use32bit
) < 0)
855 /* If already same aspath exist then return it. */
856 find
= hash_get(ashash
, &as
, aspath_hash_alloc
);
858 /* bug! should not happen, let the daemon crash below */
861 /* if the aspath was already hashed free temporary memory. */
863 assegment_free_all(as
.segments
);
864 /* aspath_key_make() always updates the string */
865 XFREE(MTYPE_AS_STR
, as
.str
);
867 json_object_free(as
.json
);
877 static void assegment_data_put(struct stream
*s
, as_t
*as
, int num
,
881 assert(num
<= AS_SEGMENT_MAX
);
883 for (i
= 0; i
< num
; i
++)
885 stream_putl(s
, as
[i
]);
887 if (as
[i
] <= BGP_AS_MAX
)
888 stream_putw(s
, as
[i
]);
890 stream_putw(s
, BGP_AS_TRANS
);
894 static size_t assegment_header_put(struct stream
*s
, uint8_t type
, int length
)
897 assert(length
<= AS_SEGMENT_MAX
);
898 stream_putc(s
, type
);
899 lenp
= stream_get_endp(s
);
900 stream_putc(s
, length
);
904 /* write aspath data to stream */
905 size_t aspath_put(struct stream
*s
, struct aspath
*as
, int use32bit
)
907 struct assegment
*seg
= as
->segments
;
910 if (!seg
|| seg
->length
== 0)
914 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
915 * At the moment, we would write out a partial aspath, and our
917 * will complain and drop the session :-/
919 * The general assumption here is that many things tested will
920 * never happen. And, in real live, up to now, they have not.
922 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
) <= STREAM_WRITEABLE(s
))) {
923 struct assegment
*next
= seg
->next
;
928 /* Overlength segments have to be split up */
929 while ((seg
->length
- written
) > AS_SEGMENT_MAX
) {
930 assegment_header_put(s
, seg
->type
, AS_SEGMENT_MAX
);
931 assegment_data_put(s
, (seg
->as
+ written
),
932 AS_SEGMENT_MAX
, use32bit
);
933 written
+= AS_SEGMENT_MAX
;
934 bytes
+= ASSEGMENT_SIZE(AS_SEGMENT_MAX
, use32bit
);
937 /* write the final segment, probably is also the first
939 lenp
= assegment_header_put(s
, seg
->type
,
940 seg
->length
- written
);
941 assegment_data_put(s
, (seg
->as
+ written
),
942 seg
->length
- written
, use32bit
);
944 /* Sequence-type segments can be 'packed' together
945 * Case of a segment which was overlength and split up
946 * will be missed here, but that doesn't matter.
948 while (next
&& ASSEGMENTS_PACKABLE(seg
, next
)) {
949 /* NB: We should never normally get here given
951 * normalise aspath data when parse them.
953 * safe than sorry. We potentially could call
954 * assegment_normalise here instead, but it's
956 * easier to do it on the fly here rather than
958 * the segment list twice every time we write
963 /* Next segment's data can fit in this one */
964 assegment_data_put(s
, next
->as
, next
->length
, use32bit
);
966 /* update the length of the segment header */
967 stream_putc_at(s
, lenp
,
968 seg
->length
- written
+ next
->length
);
969 asns_packed
+= next
->length
;
974 bytes
+= ASSEGMENT_SIZE(seg
->length
- written
+ asns_packed
,
981 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
982 * We have no way to manage the storage, so we use a static stream
983 * wrapper around aspath_put.
985 uint8_t *aspath_snmp_pathseg(struct aspath
*as
, size_t *varlen
)
987 #define SNMP_PATHSEG_MAX 1024
990 snmp_stream
= stream_new(SNMP_PATHSEG_MAX
);
992 stream_reset(snmp_stream
);
998 aspath_put(snmp_stream
, as
, 0); /* use 16 bit for now here */
1000 *varlen
= stream_get_endp(snmp_stream
);
1001 return stream_pnt(snmp_stream
);
1004 #define min(A,B) ((A) < (B) ? (A) : (B))
1006 static struct assegment
*aspath_aggregate_as_set_add(struct aspath
*aspath
,
1007 struct assegment
*asset
,
1012 /* If this is first AS set member, create new as-set segment. */
1013 if (asset
== NULL
) {
1014 asset
= assegment_new(AS_SET
, 1);
1015 if (!aspath
->segments
)
1016 aspath
->segments
= asset
;
1018 struct assegment
*seg
= aspath
->segments
;
1023 asset
->type
= AS_SET
;
1027 /* Check this AS value already exists or not. */
1028 for (i
= 0; i
< asset
->length
; i
++)
1029 if (asset
->as
[i
] == as
)
1033 asset
->as
= XREALLOC(MTYPE_AS_SEG_DATA
, asset
->as
,
1034 asset
->length
* AS_VALUE_SIZE
);
1035 asset
->as
[asset
->length
- 1] = as
;
1042 /* Modify as1 using as2 for aggregation. */
1043 struct aspath
*aspath_aggregate(struct aspath
*as1
, struct aspath
*as2
)
1049 struct assegment
*seg1
= as1
->segments
;
1050 struct assegment
*seg2
= as2
->segments
;
1051 struct aspath
*aspath
= NULL
;
1052 struct assegment
*asset
= NULL
;
1053 struct assegment
*prevseg
= NULL
;
1055 /* First of all check common leading sequence. */
1056 while (seg1
&& seg2
) {
1057 /* Check segment type. */
1058 if (seg1
->type
!= seg2
->type
)
1061 /* Minimum segment length. */
1062 minlen
= min(seg1
->length
, seg2
->length
);
1064 for (match
= 0; match
< minlen
; match
++)
1065 if (seg1
->as
[match
] != seg2
->as
[match
])
1069 struct assegment
*seg
= assegment_new(seg1
->type
, 0);
1071 seg
= assegment_append_asns(seg
, seg1
->as
, match
);
1074 aspath
= aspath_new();
1075 aspath
->segments
= seg
;
1077 prevseg
->next
= seg
;
1082 if (match
!= minlen
|| match
!= seg1
->length
1083 || seg1
->length
!= seg2
->length
)
1085 /* We are moving on to the next segment to reset match */
1094 aspath
= aspath_new();
1096 /* Make as-set using rest of all information. */
1099 for (i
= from
; i
< seg1
->length
; i
++)
1100 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1109 for (i
= from
; i
< seg2
->length
; i
++)
1110 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1117 assegment_normalise(aspath
->segments
);
1118 aspath_str_update(aspath
, false);
1122 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1123 attribute, check the leftmost AS number in the AS_PATH attribute is
1124 or not the peer's AS number. */
1125 bool aspath_firstas_check(struct aspath
*aspath
, as_t asno
)
1127 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1130 if (aspath
->segments
&& (aspath
->segments
->type
== AS_SEQUENCE
)
1131 && (aspath
->segments
->as
[0] == asno
))
1137 unsigned int aspath_get_first_as(struct aspath
*aspath
)
1139 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1142 return aspath
->segments
->as
[0];
1145 unsigned int aspath_get_last_as(struct aspath
*aspath
)
1148 unsigned int last_as
= 0;
1149 const struct assegment
*seg
;
1151 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1154 seg
= aspath
->segments
;
1157 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1158 for (i
= 0; i
< seg
->length
; i
++)
1159 last_as
= seg
->as
[i
];
1166 /* AS path loop check. If aspath contains asno then return >= 1. */
1167 int aspath_loop_check(struct aspath
*aspath
, as_t asno
)
1169 struct assegment
*seg
;
1172 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1175 seg
= aspath
->segments
;
1180 for (i
= 0; i
< seg
->length
; i
++)
1181 if (seg
->as
[i
] == asno
)
1189 /* When all of AS path is private AS return 1. */
1190 bool aspath_private_as_check(struct aspath
*aspath
)
1192 struct assegment
*seg
;
1194 if (!(aspath
&& aspath
->segments
))
1197 seg
= aspath
->segments
;
1202 for (i
= 0; i
< seg
->length
; i
++) {
1203 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1211 /* Return True if the entire ASPATH consist of the specified ASN */
1212 bool aspath_single_asn_check(struct aspath
*aspath
, as_t asn
)
1214 struct assegment
*seg
;
1216 if (!(aspath
&& aspath
->segments
))
1219 seg
= aspath
->segments
;
1224 for (i
= 0; i
< seg
->length
; i
++) {
1225 if (seg
->as
[i
] != asn
)
1233 /* Replace all instances of the target ASN with our own ASN */
1234 struct aspath
*aspath_replace_specific_asn(struct aspath
*aspath
,
1235 as_t target_asn
, as_t our_asn
)
1238 struct assegment
*seg
;
1240 new = aspath_dup(aspath
);
1241 seg
= new->segments
;
1246 for (i
= 0; i
< seg
->length
; i
++) {
1247 if (seg
->as
[i
] == target_asn
)
1248 seg
->as
[i
] = our_asn
;
1253 aspath_str_update(new, false);
1257 /* Replace all private ASNs with our own ASN */
1258 struct aspath
*aspath_replace_private_asns(struct aspath
*aspath
, as_t asn
,
1262 struct assegment
*seg
;
1264 new = aspath_dup(aspath
);
1265 seg
= new->segments
;
1270 for (i
= 0; i
< seg
->length
; i
++) {
1271 /* Don't replace if public ASN or peer's ASN */
1272 if (BGP_AS_IS_PRIVATE(seg
->as
[i
])
1273 && (seg
->as
[i
] != peer_asn
))
1279 aspath_str_update(new, false);
1283 /* Remove all private ASNs */
1284 struct aspath
*aspath_remove_private_asns(struct aspath
*aspath
, as_t peer_asn
)
1287 struct assegment
*seg
;
1288 struct assegment
*new_seg
;
1289 struct assegment
*last_new_seg
;
1294 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
1298 last_new_seg
= NULL
;
1299 seg
= aspath
->segments
;
1303 for (i
= 0; i
< seg
->length
; i
++) {
1305 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1311 // The entire segment is public so copy it
1312 if (public == seg
->length
)
1313 new_seg
= assegment_dup(seg
);
1315 // The segment is a mix of public and private ASNs. Copy as many
1317 // there are public ASNs then come back and fill in only the
1320 new_seg
= assegment_new(seg
->type
, public);
1322 for (i
= 0; i
< seg
->length
; i
++) {
1323 // keep ASN if public or matches peer's ASN
1324 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])
1325 || (seg
->as
[i
] == peer_asn
)) {
1326 new_seg
->as
[j
] = seg
->as
[i
];
1332 // This is the first segment so set the aspath segments pointer
1335 new->segments
= new_seg
;
1337 last_new_seg
->next
= new_seg
;
1339 last_new_seg
= new_seg
;
1343 aspath_str_update(new, false);
1347 /* AS path confed check. If aspath contains confed set or sequence then return
1349 bool aspath_confed_check(struct aspath
*aspath
)
1351 struct assegment
*seg
;
1353 if (!(aspath
&& aspath
->segments
))
1356 seg
= aspath
->segments
;
1359 if (seg
->type
== AS_CONFED_SET
1360 || seg
->type
== AS_CONFED_SEQUENCE
)
1367 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1368 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1369 bool aspath_left_confed_check(struct aspath
*aspath
)
1372 if (!(aspath
&& aspath
->segments
))
1375 if ((aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1376 || (aspath
->segments
->type
== AS_CONFED_SET
))
1382 /* Merge as1 to as2. as2 should be uninterned aspath. */
1383 static struct aspath
*aspath_merge(struct aspath
*as1
, struct aspath
*as2
)
1385 struct assegment
*last
, *new;
1390 last
= new = assegment_dup_all(as1
->segments
);
1392 /* find the last valid segment */
1393 while (last
&& last
->next
)
1397 last
->next
= as2
->segments
;
1398 as2
->segments
= new;
1399 aspath_str_update(as2
, false);
1403 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1404 struct aspath
*aspath_prepend(struct aspath
*as1
, struct aspath
*as2
)
1406 struct assegment
*as1segtail
;
1407 struct assegment
*as2segtail
;
1408 struct assegment
*as2seghead
;
1413 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1414 if (as2
->segments
== NULL
) {
1415 as2
->segments
= assegment_dup_all(as1
->segments
);
1416 aspath_str_update(as2
, false);
1420 /* If as1 is empty AS, no prepending to do. */
1421 if (as1
->segments
== NULL
)
1424 /* find the tail as1's segment chain. */
1425 as1segtail
= as1
->segments
;
1426 while (as1segtail
&& as1segtail
->next
)
1427 as1segtail
= as1segtail
->next
;
1429 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1430 if (as1segtail
->type
== AS_SEQUENCE
1431 && as2
->segments
->type
== AS_CONFED_SEQUENCE
)
1432 as2
= aspath_delete_confed_seq(as2
);
1434 if (!as2
->segments
) {
1435 as2
->segments
= assegment_dup_all(as1
->segments
);
1436 aspath_str_update(as2
, false);
1440 /* Compare last segment type of as1 and first segment type of as2. */
1441 if (as1segtail
->type
!= as2
->segments
->type
)
1442 return aspath_merge(as1
, as2
);
1444 if (as1segtail
->type
== AS_SEQUENCE
) {
1445 /* We have two chains of segments, as1->segments and seg2,
1446 * and we have to attach them together, merging the attaching
1447 * segments together into one.
1449 * 1. dupe as1->segments onto head of as2
1450 * 2. merge seg2's asns onto last segment of this new chain
1451 * 3. attach chain after seg2
1455 as2seghead
= as2
->segments
;
1457 /* dupe as1 onto as2's head */
1458 as2segtail
= as2
->segments
= assegment_dup_all(as1
->segments
);
1460 /* refind the tail of as2 */
1461 while (as2segtail
&& as2segtail
->next
)
1462 as2segtail
= as2segtail
->next
;
1464 /* merge the old head, seg2, into tail, seg1 */
1465 assegment_append_asns(as2segtail
, as2seghead
->as
,
1466 as2seghead
->length
);
1469 * bypass the merged seg2, and attach any chain after it
1470 * to chain descending from as2's head
1473 as2segtail
->next
= as2seghead
->next
;
1475 /* as2->segments is now referenceless and useless */
1476 assegment_free(as2seghead
);
1478 /* we've now prepended as1's segment chain to as2, merging
1479 * the inbetween AS_SEQUENCE of seg2 in the process
1481 aspath_str_update(as2
, false);
1484 /* AS_SET merge code is needed at here. */
1485 return aspath_merge(as1
, as2
);
1487 /* XXX: Ermmm, what if as1 has multiple segments?? */
1492 /* Iterate over AS_PATH segments and wipe all occurrences of the
1493 * listed AS numbers. Hence some segments may lose some or even
1494 * all data on the way, the operation is implemented as a smarter
1495 * version of aspath_dup(), which allocates memory to hold the new
1496 * data, not the original. The new AS path is returned.
1498 struct aspath
*aspath_filter_exclude(struct aspath
*source
,
1499 struct aspath
*exclude_list
)
1501 struct assegment
*srcseg
, *exclseg
, *lastseg
;
1502 struct aspath
*newpath
;
1504 newpath
= aspath_new();
1507 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
) {
1508 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1509 struct assegment
*newseg
;
1511 /* Find out, how much ASns are we going to pick from this
1513 * We can't perform filtering right inline, because the size of
1514 * the new segment isn't known at the moment yet.
1516 for (i
= 0; i
< srcseg
->length
; i
++) {
1518 for (exclseg
= exclude_list
->segments
;
1519 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1520 for (y
= 0; y
< exclseg
->length
; y
++)
1521 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1523 // There's no sense in testing
1524 // the rest of exclusion list,
1531 /* newlen is now the number of ASns to copy */
1535 /* Actual copying. Allocate memory and iterate once more,
1536 * performing filtering. */
1537 newseg
= assegment_new(srcseg
->type
, newlen
);
1538 for (i
= 0; i
< srcseg
->length
; i
++) {
1540 for (exclseg
= exclude_list
->segments
;
1541 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1542 for (y
= 0; y
< exclseg
->length
; y
++)
1543 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1549 newseg
->as
[done
++] = srcseg
->as
[i
];
1551 /* At his point newlen must be equal to done, and both must be
1553 * the filtered segment to the gross result. */
1555 newpath
->segments
= newseg
;
1557 lastseg
->next
= newseg
;
1560 aspath_str_update(newpath
, false);
1561 /* We are happy returning even an empty AS_PATH, because the
1563 * might expect this very behaviour. There's a mean to avoid this, if
1565 * by having a match rule against certain AS_PATH regexps in the
1568 aspath_free(source
);
1572 /* Add specified AS to the leftmost of aspath. */
1573 static struct aspath
*aspath_add_asns(struct aspath
*aspath
, as_t asno
,
1574 uint8_t type
, unsigned num
)
1576 struct assegment
*assegment
= aspath
->segments
;
1579 if (assegment
&& assegment
->type
== type
) {
1580 /* extend existing segment */
1582 assegment_prepend_asns(aspath
->segments
, asno
, num
);
1584 /* prepend with new segment */
1585 struct assegment
*newsegment
= assegment_new(type
, num
);
1586 for (i
= 0; i
< num
; i
++)
1587 newsegment
->as
[i
] = asno
;
1589 /* insert potentially replacing empty segment */
1590 if (assegment
&& assegment
->length
== 0) {
1591 newsegment
->next
= assegment
->next
;
1592 assegment_free(assegment
);
1594 newsegment
->next
= assegment
;
1595 aspath
->segments
= newsegment
;
1598 aspath_str_update(aspath
, false);
1602 /* Add specified AS to the leftmost of aspath num times. */
1603 struct aspath
*aspath_add_seq_n(struct aspath
*aspath
, as_t asno
, unsigned num
)
1605 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, num
);
1608 /* Add specified AS to the leftmost of aspath. */
1609 struct aspath
*aspath_add_seq(struct aspath
*aspath
, as_t asno
)
1611 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, 1);
1614 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1615 as2's leftmost AS is same return 1. */
1616 bool aspath_cmp_left(const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1618 const struct assegment
*seg1
;
1619 const struct assegment
*seg2
;
1621 if (!(aspath1
&& aspath2
))
1624 seg1
= aspath1
->segments
;
1625 seg2
= aspath2
->segments
;
1627 /* If both paths are originated in this AS then we do want to compare
1632 /* find first non-confed segments for each */
1633 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1634 || (seg1
->type
== AS_CONFED_SET
)))
1637 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1638 || (seg2
->type
== AS_CONFED_SET
)))
1642 if (!(seg1
&& seg2
&& (seg1
->type
== AS_SEQUENCE
)
1643 && (seg2
->type
== AS_SEQUENCE
)))
1646 if (seg1
->as
[0] == seg2
->as
[0])
1652 /* Truncate an aspath after a number of hops, and put the hops remaining
1653 * at the front of another aspath. Needed for AS4 compat.
1655 * Returned aspath is a /new/ aspath, which should either by free'd or
1656 * interned by the caller, as desired.
1658 struct aspath
*aspath_reconcile_as4(struct aspath
*aspath
,
1659 struct aspath
*as4path
)
1661 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1662 struct aspath
*newpath
= NULL
, *mergedpath
;
1663 int hops
, cpasns
= 0;
1665 if (!aspath
|| !as4path
)
1668 seg
= aspath
->segments
;
1670 /* CONFEDs should get reconciled too.. */
1671 hops
= (aspath_count_hops(aspath
) + aspath_count_confeds(aspath
))
1672 - aspath_count_hops(as4path
);
1675 if (BGP_DEBUG(as4
, AS4
))
1677 EC_BGP_ASPATH_FEWER_HOPS
,
1678 "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1679 /* Something's gone wrong. The RFC says we should now ignore
1681 * which is daft behaviour - it contains vital loop-detection
1682 * information which must have been removed from AS_PATH.
1684 hops
= aspath_count_hops(aspath
);
1688 newpath
= aspath_dup(as4path
);
1689 aspath_str_update(newpath
, false);
1693 if (BGP_DEBUG(as4
, AS4
))
1695 "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1696 aspath
->str
, as4path
->str
);
1698 while (seg
&& hops
> 0) {
1699 switch (seg
->type
) {
1703 cpasns
= seg
->length
;
1705 case AS_CONFED_SEQUENCE
:
1706 /* Should never split a confed-sequence, if hop-count
1707 * suggests we must then something's gone wrong
1710 * Most important goal is to preserve AS_PATHs prime
1712 * as loop-detector, so we fudge the numbers so that the
1714 * confed-sequence is merged in.
1716 if (hops
< seg
->length
) {
1717 if (BGP_DEBUG(as4
, AS4
))
1719 "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls across 2/4 ASN boundary somewhere, broken..");
1724 cpasns
= MIN(seg
->length
, hops
);
1725 hops
-= seg
->length
;
1728 assert(cpasns
<= seg
->length
);
1730 newseg
= assegment_new(seg
->type
, 0);
1731 newseg
= assegment_append_asns(newseg
, seg
->as
, cpasns
);
1734 newpath
= aspath_new();
1735 newpath
->segments
= newseg
;
1737 prevseg
->next
= newseg
;
1743 /* We may be able to join some segments here, and we must
1744 * do this because... we want normalised aspaths in out hash
1745 * and we do not want to stumble in aspath_put.
1747 mergedpath
= aspath_merge(newpath
, aspath_dup(as4path
));
1748 aspath_free(newpath
);
1749 mergedpath
->segments
= assegment_normalise(mergedpath
->segments
);
1750 aspath_str_update(mergedpath
, false);
1752 if (BGP_DEBUG(as4
, AS4
))
1753 zlog_debug("[AS4] result of synthesizing is %s",
1759 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1760 as2's leftmost AS is same return 1. (confederation as-path
1762 bool aspath_cmp_left_confed(const struct aspath
*aspath1
,
1763 const struct aspath
*aspath2
)
1765 if (!(aspath1
&& aspath2
))
1768 if (!(aspath1
->segments
&& aspath2
->segments
))
1771 if ((aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1772 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
))
1775 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1781 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1782 * RFC 5065 section 4.1.c.1
1784 * 1) if any path segments of the AS_PATH are of the type
1785 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1786 * removed from the AS_PATH attribute, leaving the sanitized
1787 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1789 struct aspath
*aspath_delete_confed_seq(struct aspath
*aspath
)
1791 struct assegment
*seg
, *prev
, *next
;
1792 char removed_confed_segment
;
1794 if (!(aspath
&& aspath
->segments
))
1797 seg
= aspath
->segments
;
1798 removed_confed_segment
= 0;
1805 if (seg
->type
== AS_CONFED_SEQUENCE
1806 || seg
->type
== AS_CONFED_SET
) {
1807 /* This is the first segment in the aspath */
1808 if (aspath
->segments
== seg
)
1809 aspath
->segments
= seg
->next
;
1811 prev
->next
= seg
->next
;
1813 assegment_free(seg
);
1814 removed_confed_segment
= 1;
1821 if (removed_confed_segment
)
1822 aspath_str_update(aspath
, false);
1827 /* Add new AS number to the leftmost part of the aspath as
1828 AS_CONFED_SEQUENCE. */
1829 struct aspath
*aspath_add_confed_seq(struct aspath
*aspath
, as_t asno
)
1831 return aspath_add_asns(aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1834 /* Add new as value to as path structure. */
1835 static void aspath_as_add(struct aspath
*as
, as_t asno
)
1837 struct assegment
*seg
= as
->segments
;
1842 /* Last segment search procedure. */
1846 assegment_append_asns(seg
, &asno
, 1);
1849 /* Add new as segment to the as path. */
1850 static void aspath_segment_add(struct aspath
*as
, int type
)
1852 struct assegment
*seg
= as
->segments
;
1853 struct assegment
*new = assegment_new(type
, 0);
1863 struct aspath
*aspath_empty(void)
1865 return aspath_parse(NULL
, 0, 1); /* 32Bit ;-) */
1868 struct aspath
*aspath_empty_get(void)
1870 struct aspath
*aspath
;
1872 aspath
= aspath_new();
1873 aspath_make_str_count(aspath
, false);
1877 unsigned long aspath_count(void)
1879 return ashash
->count
;
1883 Theoretically, one as path can have:
1885 One BGP packet size should be less than 4096.
1886 One BGP attribute size should be less than 4096 - BGP header size.
1887 One BGP aspath size should be less than 4096 - BGP header size -
1888 BGP mandantry attribute size.
1891 /* AS path string lexical token enum. */
1896 as_token_confed_seq_start
,
1897 as_token_confed_seq_end
,
1898 as_token_confed_set_start
,
1899 as_token_confed_set_end
,
1903 /* Return next token and point for string parse. */
1904 static const char *aspath_gettoken(const char *buf
, enum as_token
*token
,
1905 unsigned long *asno
)
1907 const char *p
= buf
;
1909 /* Skip seperators (space for sequences, ',' for sets). */
1910 while (isspace((unsigned char)*p
) || *p
== ',')
1913 /* Check the end of the string and type specify characters
1919 *token
= as_token_set_start
;
1923 *token
= as_token_set_end
;
1927 *token
= as_token_confed_seq_start
;
1931 *token
= as_token_confed_seq_end
;
1935 *token
= as_token_confed_set_start
;
1939 *token
= as_token_confed_set_end
;
1944 /* Check actual AS value. */
1945 if (isdigit((unsigned char)*p
)) {
1948 *token
= as_token_asval
;
1952 while (isdigit((unsigned char)*p
)) {
1954 asval
+= (*p
- '0');
1961 /* There is no match then return unknown token. */
1962 *token
= as_token_unknown
;
1967 struct aspath
*aspath_str2aspath(const char *str
)
1969 enum as_token token
= as_token_unknown
;
1970 unsigned short as_type
;
1971 unsigned long asno
= 0;
1972 struct aspath
*aspath
;
1975 aspath
= aspath_new();
1977 /* We start default type as AS_SEQUENCE. */
1978 as_type
= AS_SEQUENCE
;
1981 while ((str
= aspath_gettoken(str
, &token
, &asno
)) != NULL
) {
1983 case as_token_asval
:
1985 aspath_segment_add(aspath
, as_type
);
1988 aspath_as_add(aspath
, asno
);
1990 case as_token_set_start
:
1992 aspath_segment_add(aspath
, as_type
);
1995 case as_token_set_end
:
1996 as_type
= AS_SEQUENCE
;
1999 case as_token_confed_seq_start
:
2000 as_type
= AS_CONFED_SEQUENCE
;
2001 aspath_segment_add(aspath
, as_type
);
2004 case as_token_confed_seq_end
:
2005 as_type
= AS_SEQUENCE
;
2008 case as_token_confed_set_start
:
2009 as_type
= AS_CONFED_SET
;
2010 aspath_segment_add(aspath
, as_type
);
2013 case as_token_confed_set_end
:
2014 as_type
= AS_SEQUENCE
;
2017 case as_token_unknown
:
2019 aspath_free(aspath
);
2024 aspath_make_str_count(aspath
, false);
2029 /* Make hash value by raw aspath data. */
2030 unsigned int aspath_key_make(const void *p
)
2032 const struct aspath
*aspath
= p
;
2033 unsigned int key
= 0;
2036 aspath_str_update((struct aspath
*)aspath
, false);
2038 key
= jhash(aspath
->str
, aspath
->str_len
, 2334325);
2043 /* If two aspath have same value then return 1 else return 0 */
2044 bool aspath_cmp(const void *arg1
, const void *arg2
)
2046 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2047 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2049 while (seg1
|| seg2
) {
2051 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2053 if (seg1
->type
!= seg2
->type
)
2055 if (seg1
->length
!= seg2
->length
)
2057 for (i
= 0; i
< seg1
->length
; i
++)
2058 if (seg1
->as
[i
] != seg2
->as
[i
])
2066 /* AS path hash initialize. */
2067 void aspath_init(void)
2069 ashash
= hash_create_size(32768, aspath_key_make
, aspath_cmp
,
2073 void aspath_finish(void)
2075 hash_clean(ashash
, (void (*)(void *))aspath_free
);
2080 stream_free(snmp_stream
);
2083 /* return and as path value */
2084 const char *aspath_print(struct aspath
*as
)
2086 return (as
? as
->str
: NULL
);
2089 /* Printing functions */
2090 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
2091 * AS_PATH wasn't empty.
2093 void aspath_print_vty(struct vty
*vty
, const char *format
, struct aspath
*as
,
2097 vty_out(vty
, format
, as
->str
);
2098 if (as
->str_len
&& strlen(suffix
))
2099 vty_out(vty
, "%s", suffix
);
2102 static void aspath_show_all_iterator(struct hash_bucket
*bucket
,
2107 as
= (struct aspath
*)bucket
->data
;
2109 vty_out(vty
, "[%p:%u] (%ld) ", (void *)bucket
, bucket
->key
, as
->refcnt
);
2110 vty_out(vty
, "%s\n", as
->str
);
2113 /* Print all aspath and hash information. This function is used from
2114 `show [ip] bgp paths' command. */
2115 void aspath_print_all_vty(struct vty
*vty
)
2117 hash_iterate(ashash
, (void (*)(struct hash_bucket
*,
2118 void *))aspath_show_all_iterator
,
2122 static struct aspath
*bgp_aggr_aspath_lookup(struct bgp_aggregate
*aggregate
,
2123 struct aspath
*aspath
)
2125 return hash_lookup(aggregate
->aspath_hash
, aspath
);
2128 static void *bgp_aggr_aspath_hash_alloc(void *p
)
2130 struct aspath
*ref
= (struct aspath
*)p
;
2131 struct aspath
*aspath
= NULL
;
2133 aspath
= aspath_dup(ref
);
2137 static void bgp_aggr_aspath_prepare(struct hash_bucket
*hb
, void *arg
)
2139 struct aspath
*hb_aspath
= hb
->data
;
2140 struct aspath
**aggr_aspath
= arg
;
2143 *aggr_aspath
= aspath_aggregate(*aggr_aspath
, hb_aspath
);
2145 *aggr_aspath
= aspath_dup(hb_aspath
);
2148 void bgp_aggr_aspath_remove(void *arg
)
2150 struct aspath
*aspath
= arg
;
2152 aspath_free(aspath
);
2155 void bgp_compute_aggregate_aspath(struct bgp_aggregate
*aggregate
,
2156 struct aspath
*aspath
)
2158 bgp_compute_aggregate_aspath_hash(aggregate
, aspath
);
2160 bgp_compute_aggregate_aspath_val(aggregate
);
2164 void bgp_compute_aggregate_aspath_hash(struct bgp_aggregate
*aggregate
,
2165 struct aspath
*aspath
)
2167 struct aspath
*aggr_aspath
= NULL
;
2169 if ((aggregate
== NULL
) || (aspath
== NULL
))
2172 /* Create hash if not already created.
2174 if (aggregate
->aspath_hash
== NULL
)
2175 aggregate
->aspath_hash
= hash_create(
2176 aspath_key_make
, aspath_cmp
,
2177 "BGP Aggregator as-path hash");
2179 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2180 if (aggr_aspath
== NULL
) {
2181 /* Insert as-path into hash.
2183 aggr_aspath
= hash_get(aggregate
->aspath_hash
, aspath
,
2184 bgp_aggr_aspath_hash_alloc
);
2187 /* Increment reference counter.
2189 aggr_aspath
->refcnt
++;
2192 void bgp_compute_aggregate_aspath_val(struct bgp_aggregate
*aggregate
)
2194 if (aggregate
== NULL
)
2196 /* Re-compute aggregate's as-path.
2198 if (aggregate
->aspath
) {
2199 aspath_free(aggregate
->aspath
);
2200 aggregate
->aspath
= NULL
;
2202 if (aggregate
->aspath_hash
2203 && aggregate
->aspath_hash
->count
) {
2204 hash_iterate(aggregate
->aspath_hash
,
2205 bgp_aggr_aspath_prepare
,
2206 &aggregate
->aspath
);
2210 void bgp_remove_aspath_from_aggregate(struct bgp_aggregate
*aggregate
,
2211 struct aspath
*aspath
)
2213 struct aspath
*aggr_aspath
= NULL
;
2214 struct aspath
*ret_aspath
= NULL
;
2217 || (!aggregate
->aspath_hash
)
2221 /* Look-up the aspath in the hash.
2223 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2225 aggr_aspath
->refcnt
--;
2227 if (aggr_aspath
->refcnt
== 0) {
2228 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2230 aspath_free(ret_aspath
);
2233 /* Remove aggregate's old as-path.
2235 aspath_free(aggregate
->aspath
);
2236 aggregate
->aspath
= NULL
;
2238 bgp_compute_aggregate_aspath_val(aggregate
);
2243 void bgp_remove_aspath_from_aggregate_hash(struct bgp_aggregate
*aggregate
,
2244 struct aspath
*aspath
)
2246 struct aspath
*aggr_aspath
= NULL
;
2247 struct aspath
*ret_aspath
= NULL
;
2250 || (!aggregate
->aspath_hash
)
2254 /* Look-up the aspath in the hash.
2256 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2258 aggr_aspath
->refcnt
--;
2260 if (aggr_aspath
->refcnt
== 0) {
2261 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2263 aspath_free(ret_aspath
);