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 /* Estimate size aspath /might/ take if encoded into an
435 * This is a quick estimate, not definitive! aspath_put()
436 * may return a different number!!
438 unsigned int aspath_size(struct aspath
*aspath
)
441 struct assegment
*seg
= aspath
->segments
;
444 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
450 /* Return highest public ASN in path */
451 as_t
aspath_highest(struct aspath
*aspath
)
453 struct assegment
*seg
= aspath
->segments
;
458 for (i
= 0; i
< seg
->length
; i
++)
459 if (seg
->as
[i
] > highest
460 && !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
461 highest
= seg
->as
[i
];
467 /* Return the left-most ASN in path */
468 as_t
aspath_leftmost(struct aspath
*aspath
)
470 struct assegment
*seg
= aspath
->segments
;
473 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
474 leftmost
= seg
->as
[0];
479 /* Return 1 if there are any 4-byte ASes in the path */
480 unsigned int aspath_has_as4(struct aspath
*aspath
)
482 struct assegment
*seg
= aspath
->segments
;
486 for (i
= 0; i
< seg
->length
; i
++)
487 if (seg
->as
[i
] > BGP_AS_MAX
)
494 /* Convert aspath structure to string expression. */
495 static void aspath_make_str_count(struct aspath
*as
, bool make_json
)
497 struct assegment
*seg
;
501 json_object
*jaspath_segments
= NULL
;
502 json_object
*jseg
= NULL
;
503 json_object
*jseg_list
= NULL
;
506 as
->json
= json_object_new_object();
507 jaspath_segments
= json_object_new_array();
513 json_object_string_add(as
->json
, "string", "Local");
514 json_object_object_add(as
->json
, "segments",
516 json_object_int_add(as
->json
, "length", 0);
518 as
->str
= XMALLOC(MTYPE_AS_STR
, 1);
526 /* ASN takes 5 to 10 chars plus seperator, see below.
527 * If there is one differing segment type, we need an additional
528 * 2 chars for segment delimiters, and the final '\0'.
529 * Hopefully this is large enough to avoid hitting the realloc
530 * code below for most common sequences.
532 * This was changed to 10 after the well-known BGP assertion, which
533 * had hit some parts of the Internet in May of 2009.
535 #define ASN_STR_LEN (10 + 1)
536 str_size
= MAX(assegment_count_asns(seg
, 0) * ASN_STR_LEN
+ 2 + 1,
537 ASPATH_STR_DEFAULT_LEN
);
538 str_buf
= XMALLOC(MTYPE_AS_STR
, str_size
);
544 /* Check AS type validity. Set seperator for segment */
551 case AS_CONFED_SEQUENCE
:
555 XFREE(MTYPE_AS_STR
, str_buf
);
558 json_object_free(as
->json
);
564 /* We might need to increase str_buf, particularly if path has
565 * differing segments types, our initial guesstimate above will
566 * have been wrong. Need 10 chars for ASN, a seperator each and
567 * potentially two segment delimiters, plus a space between each
568 * segment and trailing zero.
570 * This definitely didn't work with the value of 5 bytes and
573 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
574 if ((len
+ SEGMENT_STR_LEN(seg
)) > str_size
) {
575 str_size
= len
+ SEGMENT_STR_LEN(seg
);
576 str_buf
= XREALLOC(MTYPE_AS_STR
, str_buf
, str_size
);
579 #undef SEGMENT_STR_LEN
581 if (seg
->type
!= AS_SEQUENCE
)
583 str_buf
+ len
, str_size
- len
, "%c",
584 aspath_delimiter_char(seg
->type
, AS_SEG_START
));
587 jseg_list
= json_object_new_array();
589 /* write out the ASNs, with their seperators, bar the last one*/
590 for (i
= 0; i
< seg
->length
; i
++) {
592 json_object_array_add(
594 json_object_new_int64(seg
->as
[i
]));
596 len
+= snprintf(str_buf
+ len
, str_size
- len
, "%u",
599 if (i
< (seg
->length
- 1))
600 len
+= snprintf(str_buf
+ len
, str_size
- len
,
605 jseg
= json_object_new_object();
606 json_object_string_add(
608 aspath_segment_type_str
[seg
->type
]);
609 json_object_object_add(jseg
, "list", jseg_list
);
610 json_object_array_add(jaspath_segments
, jseg
);
613 if (seg
->type
!= AS_SEQUENCE
)
615 str_buf
+ len
, str_size
- len
, "%c",
616 aspath_delimiter_char(seg
->type
, AS_SEG_END
));
618 len
+= snprintf(str_buf
+ len
, str_size
- len
, " ");
623 assert(len
< str_size
);
630 json_object_string_add(as
->json
, "string", str_buf
);
631 json_object_object_add(as
->json
, "segments", jaspath_segments
);
632 json_object_int_add(as
->json
, "length", aspath_count_hops(as
));
638 void aspath_str_update(struct aspath
*as
, bool make_json
)
640 XFREE(MTYPE_AS_STR
, as
->str
);
643 json_object_free(as
->json
);
647 aspath_make_str_count(as
, make_json
);
650 /* Intern allocated AS path. */
651 struct aspath
*aspath_intern(struct aspath
*aspath
)
655 /* Assert this AS path structure is not interned and has the string
656 representation built. */
657 assert(aspath
->refcnt
== 0);
660 /* Check AS path hash. */
661 find
= hash_get(ashash
, aspath
, hash_alloc_intern
);
670 /* Duplicate aspath structure. Created same aspath structure but
671 reference count and AS path string is cleared. */
672 struct aspath
*aspath_dup(struct aspath
*aspath
)
674 unsigned short buflen
= aspath
->str_len
+ 1;
677 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
680 if (aspath
->segments
)
681 new->segments
= assegment_dup_all(aspath
->segments
);
686 new->str
= XMALLOC(MTYPE_AS_STR
, buflen
);
687 new->str_len
= aspath
->str_len
;
689 /* copy the string data */
690 if (aspath
->str_len
> 0)
691 memcpy(new->str
, aspath
->str
, buflen
);
698 static void *aspath_hash_alloc(void *arg
)
700 const struct aspath
*aspath
= arg
;
703 /* Malformed AS path value. */
706 /* New aspath structure is needed. */
707 new = XMALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
709 /* Reuse segments and string representation */
711 new->segments
= aspath
->segments
;
712 new->str
= aspath
->str
;
713 new->str_len
= aspath
->str_len
;
714 new->json
= aspath
->json
;
719 /* parse as-segment byte stream in struct assegment */
720 static int assegments_parse(struct stream
*s
, size_t length
,
721 struct assegment
**result
, int use32bit
)
723 struct assegment_header segh
;
724 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
727 /* empty aspath (ie iBGP or somesuch) */
731 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
733 "[AS4SEG] Parse aspath segment: got total byte length %lu",
734 (unsigned long)length
);
736 if ((STREAM_READABLE(s
) < length
)
737 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
738 || (length
% AS16_VALUE_SIZE
))
741 while (bytes
< length
) {
745 if ((length
- bytes
) <= AS_HEADER_SIZE
) {
747 assegment_free_all(head
);
751 /* softly softly, get the header first on its own */
752 segh
.type
= stream_getc(s
);
753 segh
.length
= stream_getc(s
);
755 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
757 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
759 "[AS4SEG] Parse aspath segment: got type %d, length %d",
760 segh
.type
, segh
.length
);
763 if (((bytes
+ seg_size
) > length
)
764 /* 1771bis 4.3b: seg length contains one or more */
765 || (segh
.length
== 0)
766 /* Paranoia in case someone changes type of segment length.
767 * Shift both values by 0x10 to make the comparison operate
768 * on more, than 8 bits (otherwise it's a warning, bug
771 || ((sizeof(segh
.length
) > 1)
772 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
))) {
774 assegment_free_all(head
);
781 case AS_CONFED_SEQUENCE
:
786 assegment_free_all(head
);
790 /* now its safe to trust lengths */
791 seg
= assegment_new(segh
.type
, segh
.length
);
795 else /* it's the first segment */
798 for (i
= 0; i
< segh
.length
; i
++)
800 (use32bit
) ? stream_getl(s
) : stream_getw(s
);
804 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
806 "[AS4SEG] Parse aspath segment: Bytes now: %lu",
807 (unsigned long)bytes
);
812 *result
= assegment_normalise(head
);
816 /* AS path parse function. pnt is a pointer to byte stream and length
817 is length of byte stream. If there is same AS path in the the AS
818 path hash then return it else make new AS path structure.
820 On error NULL is returned.
822 struct aspath
*aspath_parse(struct stream
*s
, size_t length
, int use32bit
)
827 /* If length is odd it's malformed AS path. */
828 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
829 * otherwise its malformed when length is larger than 2 and (length-2)
830 * is not dividable by 4.
831 * But... this time we're lazy
833 if (length
% AS16_VALUE_SIZE
)
836 memset(&as
, 0, sizeof(struct aspath
));
837 if (assegments_parse(s
, length
, &as
.segments
, use32bit
) < 0)
840 /* If already same aspath exist then return it. */
841 find
= hash_get(ashash
, &as
, aspath_hash_alloc
);
843 /* bug! should not happen, let the daemon crash below */
846 /* if the aspath was already hashed free temporary memory. */
848 assegment_free_all(as
.segments
);
849 /* aspath_key_make() always updates the string */
850 XFREE(MTYPE_AS_STR
, as
.str
);
852 json_object_free(as
.json
);
862 static void assegment_data_put(struct stream
*s
, as_t
*as
, int num
,
866 assert(num
<= AS_SEGMENT_MAX
);
868 for (i
= 0; i
< num
; i
++)
870 stream_putl(s
, as
[i
]);
872 if (as
[i
] <= BGP_AS_MAX
)
873 stream_putw(s
, as
[i
]);
875 stream_putw(s
, BGP_AS_TRANS
);
879 static size_t assegment_header_put(struct stream
*s
, uint8_t type
, int length
)
882 assert(length
<= AS_SEGMENT_MAX
);
883 stream_putc(s
, type
);
884 lenp
= stream_get_endp(s
);
885 stream_putc(s
, length
);
889 /* write aspath data to stream */
890 size_t aspath_put(struct stream
*s
, struct aspath
*as
, int use32bit
)
892 struct assegment
*seg
= as
->segments
;
895 if (!seg
|| seg
->length
== 0)
900 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
901 * At the moment, we would write out a partial aspath, and our
903 * will complain and drop the session :-/
905 * The general assumption here is that many things tested will
906 * never happen. And, in real live, up to now, they have not.
908 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
)
909 <= STREAM_WRITEABLE(s
))) {
910 struct assegment
*next
= seg
->next
;
915 /* Overlength segments have to be split up */
916 while ((seg
->length
- written
) > AS_SEGMENT_MAX
) {
917 assegment_header_put(s
, seg
->type
,
919 assegment_data_put(s
, (seg
->as
+ written
), AS_SEGMENT_MAX
,
921 written
+= AS_SEGMENT_MAX
;
922 bytes
+= ASSEGMENT_SIZE(AS_SEGMENT_MAX
,
926 /* write the final segment, probably is also the first
928 lenp
= assegment_header_put(s
, seg
->type
,
929 seg
->length
- written
);
930 assegment_data_put(s
, (seg
->as
+ written
),
931 seg
->length
- written
, use32bit
);
933 /* Sequence-type segments can be 'packed' together
934 * Case of a segment which was overlength and split up
935 * will be missed here, but that doesn't matter.
937 while (next
&& ASSEGMENTS_PACKABLE(seg
, next
)) {
938 /* NB: We should never normally get here given
940 * normalise aspath data when parse them.
942 * safe than sorry. We potentially could call
943 * assegment_normalise here instead, but it's
945 * easier to do it on the fly here rather than
947 * the segment list twice every time we write
952 /* Next segment's data can fit in this one */
953 assegment_data_put(s
, next
->as
, next
->length
,
956 /* update the length of the segment header */
957 stream_putc_at(s
, lenp
,
958 seg
->length
- written
960 asns_packed
+= next
->length
;
965 bytes
+= ASSEGMENT_SIZE(
966 seg
->length
- written
+ asns_packed
, use32bit
);
973 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
974 * We have no way to manage the storage, so we use a static stream
975 * wrapper around aspath_put.
977 uint8_t *aspath_snmp_pathseg(struct aspath
*as
, size_t *varlen
)
979 #define SNMP_PATHSEG_MAX 1024
982 snmp_stream
= stream_new(SNMP_PATHSEG_MAX
);
984 stream_reset(snmp_stream
);
990 aspath_put(snmp_stream
, as
, 0); /* use 16 bit for now here */
992 *varlen
= stream_get_endp(snmp_stream
);
993 return stream_pnt(snmp_stream
);
996 #define min(A,B) ((A) < (B) ? (A) : (B))
998 static struct assegment
*aspath_aggregate_as_set_add(struct aspath
*aspath
,
999 struct assegment
*asset
,
1004 /* If this is first AS set member, create new as-set segment. */
1005 if (asset
== NULL
) {
1006 asset
= assegment_new(AS_SET
, 1);
1007 if (!aspath
->segments
)
1008 aspath
->segments
= asset
;
1010 struct assegment
*seg
= aspath
->segments
;
1015 asset
->type
= AS_SET
;
1019 /* Check this AS value already exists or not. */
1020 for (i
= 0; i
< asset
->length
; i
++)
1021 if (asset
->as
[i
] == as
)
1025 asset
->as
= XREALLOC(MTYPE_AS_SEG_DATA
, asset
->as
,
1026 asset
->length
* AS_VALUE_SIZE
);
1027 asset
->as
[asset
->length
- 1] = as
;
1034 /* Modify as1 using as2 for aggregation. */
1035 struct aspath
*aspath_aggregate(struct aspath
*as1
, struct aspath
*as2
)
1041 struct assegment
*seg1
= as1
->segments
;
1042 struct assegment
*seg2
= as2
->segments
;
1043 struct aspath
*aspath
= NULL
;
1044 struct assegment
*asset
= NULL
;
1045 struct assegment
*prevseg
= NULL
;
1047 /* First of all check common leading sequence. */
1048 while (seg1
&& seg2
) {
1049 /* Check segment type. */
1050 if (seg1
->type
!= seg2
->type
)
1053 /* Minimum segment length. */
1054 minlen
= min(seg1
->length
, seg2
->length
);
1056 for (match
= 0; match
< minlen
; match
++)
1057 if (seg1
->as
[match
] != seg2
->as
[match
])
1061 struct assegment
*seg
= assegment_new(seg1
->type
, 0);
1063 seg
= assegment_append_asns(seg
, seg1
->as
, match
);
1066 aspath
= aspath_new();
1067 aspath
->segments
= seg
;
1069 prevseg
->next
= seg
;
1074 if (match
!= minlen
|| match
!= seg1
->length
1075 || seg1
->length
!= seg2
->length
)
1077 /* We are moving on to the next segment to reset match */
1086 aspath
= aspath_new();
1088 /* Make as-set using rest of all information. */
1091 for (i
= from
; i
< seg1
->length
; i
++)
1092 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1101 for (i
= from
; i
< seg2
->length
; i
++)
1102 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1109 assegment_normalise(aspath
->segments
);
1110 aspath_str_update(aspath
, false);
1114 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1115 attribute, check the leftmost AS number in the AS_PATH attribute is
1116 or not the peer's AS number. */
1117 int aspath_firstas_check(struct aspath
*aspath
, as_t asno
)
1119 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1122 if (aspath
->segments
&& (aspath
->segments
->type
== AS_SEQUENCE
)
1123 && (aspath
->segments
->as
[0] == asno
))
1129 unsigned int aspath_get_first_as(struct aspath
*aspath
)
1131 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1134 return aspath
->segments
->as
[0];
1137 unsigned int aspath_get_last_as(struct aspath
*aspath
)
1140 unsigned int last_as
= 0;
1141 const struct assegment
*seg
;
1143 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1146 seg
= aspath
->segments
;
1149 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1150 for (i
= 0; i
< seg
->length
; i
++)
1151 last_as
= seg
->as
[i
];
1158 /* AS path loop check. If aspath contains asno then return >= 1. */
1159 int aspath_loop_check(struct aspath
*aspath
, as_t asno
)
1161 struct assegment
*seg
;
1164 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1167 seg
= aspath
->segments
;
1172 for (i
= 0; i
< seg
->length
; i
++)
1173 if (seg
->as
[i
] == asno
)
1181 /* When all of AS path is private AS return 1. */
1182 int aspath_private_as_check(struct aspath
*aspath
)
1184 struct assegment
*seg
;
1186 if (!(aspath
&& aspath
->segments
))
1189 seg
= aspath
->segments
;
1194 for (i
= 0; i
< seg
->length
; i
++) {
1195 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1203 /* Return True if the entire ASPATH consist of the specified ASN */
1204 int aspath_single_asn_check(struct aspath
*aspath
, as_t asn
)
1206 struct assegment
*seg
;
1208 if (!(aspath
&& aspath
->segments
))
1211 seg
= aspath
->segments
;
1216 for (i
= 0; i
< seg
->length
; i
++) {
1217 if (seg
->as
[i
] != asn
)
1225 /* Replace all instances of the target ASN with our own ASN */
1226 struct aspath
*aspath_replace_specific_asn(struct aspath
*aspath
,
1227 as_t target_asn
, as_t our_asn
)
1230 struct assegment
*seg
;
1232 new = aspath_dup(aspath
);
1233 seg
= new->segments
;
1238 for (i
= 0; i
< seg
->length
; i
++) {
1239 if (seg
->as
[i
] == target_asn
)
1240 seg
->as
[i
] = our_asn
;
1245 aspath_str_update(new, false);
1249 /* Replace all private ASNs with our own ASN */
1250 struct aspath
*aspath_replace_private_asns(struct aspath
*aspath
, as_t asn
,
1254 struct assegment
*seg
;
1256 new = aspath_dup(aspath
);
1257 seg
= new->segments
;
1262 for (i
= 0; i
< seg
->length
; i
++) {
1263 /* Don't replace if public ASN or peer's ASN */
1264 if (BGP_AS_IS_PRIVATE(seg
->as
[i
])
1265 && (seg
->as
[i
] != peer_asn
))
1271 aspath_str_update(new, false);
1275 /* Remove all private ASNs */
1276 struct aspath
*aspath_remove_private_asns(struct aspath
*aspath
, as_t peer_asn
)
1279 struct assegment
*seg
;
1280 struct assegment
*new_seg
;
1281 struct assegment
*last_new_seg
;
1286 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
1290 last_new_seg
= NULL
;
1291 seg
= aspath
->segments
;
1295 for (i
= 0; i
< seg
->length
; i
++) {
1297 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1303 // The entire segment is public so copy it
1304 if (public == seg
->length
)
1305 new_seg
= assegment_dup(seg
);
1307 // The segment is a mix of public and private ASNs. Copy as many
1309 // there are public ASNs then come back and fill in only the
1312 new_seg
= assegment_new(seg
->type
, public);
1314 for (i
= 0; i
< seg
->length
; i
++) {
1315 // keep ASN if public or matches peer's ASN
1316 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])
1317 || (seg
->as
[i
] == peer_asn
)) {
1318 new_seg
->as
[j
] = seg
->as
[i
];
1324 // This is the first segment so set the aspath segments pointer
1327 new->segments
= new_seg
;
1329 last_new_seg
->next
= new_seg
;
1331 last_new_seg
= new_seg
;
1335 aspath_str_update(new, false);
1339 /* AS path confed check. If aspath contains confed set or sequence then return
1341 int aspath_confed_check(struct aspath
*aspath
)
1343 struct assegment
*seg
;
1345 if (!(aspath
&& aspath
->segments
))
1348 seg
= aspath
->segments
;
1351 if (seg
->type
== AS_CONFED_SET
1352 || seg
->type
== AS_CONFED_SEQUENCE
)
1359 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1360 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1361 int aspath_left_confed_check(struct aspath
*aspath
)
1364 if (!(aspath
&& aspath
->segments
))
1367 if ((aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1368 || (aspath
->segments
->type
== AS_CONFED_SET
))
1374 /* Merge as1 to as2. as2 should be uninterned aspath. */
1375 static struct aspath
*aspath_merge(struct aspath
*as1
, struct aspath
*as2
)
1377 struct assegment
*last
, *new;
1382 last
= new = assegment_dup_all(as1
->segments
);
1384 /* find the last valid segment */
1385 while (last
&& last
->next
)
1389 last
->next
= as2
->segments
;
1390 as2
->segments
= new;
1391 aspath_str_update(as2
, false);
1395 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1396 struct aspath
*aspath_prepend(struct aspath
*as1
, struct aspath
*as2
)
1398 struct assegment
*as1segtail
;
1399 struct assegment
*as2segtail
;
1400 struct assegment
*as2seghead
;
1405 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1406 if (as2
->segments
== NULL
) {
1407 as2
->segments
= assegment_dup_all(as1
->segments
);
1408 aspath_str_update(as2
, false);
1412 /* If as1 is empty AS, no prepending to do. */
1413 if (as1
->segments
== NULL
)
1416 /* find the tail as1's segment chain. */
1417 as1segtail
= as1
->segments
;
1418 while (as1segtail
&& as1segtail
->next
)
1419 as1segtail
= as1segtail
->next
;
1421 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1422 if (as1segtail
->type
== AS_SEQUENCE
1423 && as2
->segments
->type
== AS_CONFED_SEQUENCE
)
1424 as2
= aspath_delete_confed_seq(as2
);
1426 if (!as2
->segments
) {
1427 as2
->segments
= assegment_dup_all(as1
->segments
);
1428 aspath_str_update(as2
, false);
1432 /* Compare last segment type of as1 and first segment type of as2. */
1433 if (as1segtail
->type
!= as2
->segments
->type
)
1434 return aspath_merge(as1
, as2
);
1436 if (as1segtail
->type
== AS_SEQUENCE
) {
1437 /* We have two chains of segments, as1->segments and seg2,
1438 * and we have to attach them together, merging the attaching
1439 * segments together into one.
1441 * 1. dupe as1->segments onto head of as2
1442 * 2. merge seg2's asns onto last segment of this new chain
1443 * 3. attach chain after seg2
1447 as2seghead
= as2
->segments
;
1449 /* dupe as1 onto as2's head */
1450 as2segtail
= as2
->segments
= assegment_dup_all(as1
->segments
);
1452 /* refind the tail of as2 */
1453 while (as2segtail
&& as2segtail
->next
)
1454 as2segtail
= as2segtail
->next
;
1456 /* merge the old head, seg2, into tail, seg1 */
1457 assegment_append_asns(as2segtail
, as2seghead
->as
,
1458 as2seghead
->length
);
1461 * bypass the merged seg2, and attach any chain after it
1462 * to chain descending from as2's head
1465 as2segtail
->next
= as2seghead
->next
;
1467 /* as2->segments is now referenceless and useless */
1468 assegment_free(as2seghead
);
1470 /* we've now prepended as1's segment chain to as2, merging
1471 * the inbetween AS_SEQUENCE of seg2 in the process
1473 aspath_str_update(as2
, false);
1476 /* AS_SET merge code is needed at here. */
1477 return aspath_merge(as1
, as2
);
1479 /* XXX: Ermmm, what if as1 has multiple segments?? */
1484 /* Iterate over AS_PATH segments and wipe all occurrences of the
1485 * listed AS numbers. Hence some segments may lose some or even
1486 * all data on the way, the operation is implemented as a smarter
1487 * version of aspath_dup(), which allocates memory to hold the new
1488 * data, not the original. The new AS path is returned.
1490 struct aspath
*aspath_filter_exclude(struct aspath
*source
,
1491 struct aspath
*exclude_list
)
1493 struct assegment
*srcseg
, *exclseg
, *lastseg
;
1494 struct aspath
*newpath
;
1496 newpath
= aspath_new();
1499 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
) {
1500 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1501 struct assegment
*newseg
;
1503 /* Find out, how much ASns are we going to pick from this
1505 * We can't perform filtering right inline, because the size of
1506 * the new segment isn't known at the moment yet.
1508 for (i
= 0; i
< srcseg
->length
; i
++) {
1510 for (exclseg
= exclude_list
->segments
;
1511 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1512 for (y
= 0; y
< exclseg
->length
; y
++)
1513 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1515 // There's no sense in testing
1516 // the rest of exclusion list,
1523 /* newlen is now the number of ASns to copy */
1527 /* Actual copying. Allocate memory and iterate once more,
1528 * performing filtering. */
1529 newseg
= assegment_new(srcseg
->type
, newlen
);
1530 for (i
= 0; i
< srcseg
->length
; i
++) {
1532 for (exclseg
= exclude_list
->segments
;
1533 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1534 for (y
= 0; y
< exclseg
->length
; y
++)
1535 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1541 newseg
->as
[done
++] = srcseg
->as
[i
];
1543 /* At his point newlen must be equal to done, and both must be
1545 * the filtered segment to the gross result. */
1547 newpath
->segments
= newseg
;
1549 lastseg
->next
= newseg
;
1552 aspath_str_update(newpath
, false);
1553 /* We are happy returning even an empty AS_PATH, because the
1555 * might expect this very behaviour. There's a mean to avoid this, if
1557 * by having a match rule against certain AS_PATH regexps in the
1560 aspath_free(source
);
1564 /* Add specified AS to the leftmost of aspath. */
1565 static struct aspath
*aspath_add_asns(struct aspath
*aspath
, as_t asno
,
1566 uint8_t type
, unsigned num
)
1568 struct assegment
*assegment
= aspath
->segments
;
1571 if (assegment
&& assegment
->type
== type
) {
1572 /* extend existing segment */
1574 assegment_prepend_asns(aspath
->segments
, asno
, num
);
1576 /* prepend with new segment */
1577 struct assegment
*newsegment
= assegment_new(type
, num
);
1578 for (i
= 0; i
< num
; i
++)
1579 newsegment
->as
[i
] = asno
;
1581 /* insert potentially replacing empty segment */
1582 if (assegment
&& assegment
->length
== 0) {
1583 newsegment
->next
= assegment
->next
;
1584 assegment_free(assegment
);
1586 newsegment
->next
= assegment
;
1587 aspath
->segments
= newsegment
;
1590 aspath_str_update(aspath
, false);
1594 /* Add specified AS to the leftmost of aspath num times. */
1595 struct aspath
*aspath_add_seq_n(struct aspath
*aspath
, as_t asno
, unsigned num
)
1597 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, num
);
1600 /* Add specified AS to the leftmost of aspath. */
1601 struct aspath
*aspath_add_seq(struct aspath
*aspath
, as_t asno
)
1603 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, 1);
1606 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1607 as2's leftmost AS is same return 1. */
1608 int aspath_cmp_left(const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1610 const struct assegment
*seg1
;
1611 const struct assegment
*seg2
;
1613 if (!(aspath1
&& aspath2
))
1616 seg1
= aspath1
->segments
;
1617 seg2
= aspath2
->segments
;
1619 /* If both paths are originated in this AS then we do want to compare
1624 /* find first non-confed segments for each */
1625 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1626 || (seg1
->type
== AS_CONFED_SET
)))
1629 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1630 || (seg2
->type
== AS_CONFED_SET
)))
1634 if (!(seg1
&& seg2
&& (seg1
->type
== AS_SEQUENCE
)
1635 && (seg2
->type
== AS_SEQUENCE
)))
1638 if (seg1
->as
[0] == seg2
->as
[0])
1644 /* Truncate an aspath after a number of hops, and put the hops remaining
1645 * at the front of another aspath. Needed for AS4 compat.
1647 * Returned aspath is a /new/ aspath, which should either by free'd or
1648 * interned by the caller, as desired.
1650 struct aspath
*aspath_reconcile_as4(struct aspath
*aspath
,
1651 struct aspath
*as4path
)
1653 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1654 struct aspath
*newpath
= NULL
, *mergedpath
;
1655 int hops
, cpasns
= 0;
1657 if (!aspath
|| !as4path
)
1660 seg
= aspath
->segments
;
1662 /* CONFEDs should get reconciled too.. */
1663 hops
= (aspath_count_hops(aspath
) + aspath_count_confeds(aspath
))
1664 - aspath_count_hops(as4path
);
1667 if (BGP_DEBUG(as4
, AS4
))
1669 EC_BGP_ASPATH_FEWER_HOPS
,
1670 "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1671 /* Something's gone wrong. The RFC says we should now ignore
1673 * which is daft behaviour - it contains vital loop-detection
1674 * information which must have been removed from AS_PATH.
1676 hops
= aspath_count_hops(aspath
);
1680 newpath
= aspath_dup(as4path
);
1681 aspath_str_update(newpath
, false);
1685 if (BGP_DEBUG(as4
, AS4
))
1687 "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1688 aspath
->str
, as4path
->str
);
1690 while (seg
&& hops
> 0) {
1691 switch (seg
->type
) {
1695 cpasns
= seg
->length
;
1697 case AS_CONFED_SEQUENCE
:
1698 /* Should never split a confed-sequence, if hop-count
1699 * suggests we must then something's gone wrong
1702 * Most important goal is to preserve AS_PATHs prime
1704 * as loop-detector, so we fudge the numbers so that the
1706 * confed-sequence is merged in.
1708 if (hops
< seg
->length
) {
1709 if (BGP_DEBUG(as4
, AS4
))
1711 "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1712 " across 2/4 ASN boundary somewhere, broken..");
1717 cpasns
= MIN(seg
->length
, hops
);
1718 hops
-= seg
->length
;
1721 assert(cpasns
<= seg
->length
);
1723 newseg
= assegment_new(seg
->type
, 0);
1724 newseg
= assegment_append_asns(newseg
, seg
->as
, cpasns
);
1727 newpath
= aspath_new();
1728 newpath
->segments
= newseg
;
1730 prevseg
->next
= newseg
;
1736 /* We may be able to join some segments here, and we must
1737 * do this because... we want normalised aspaths in out hash
1738 * and we do not want to stumble in aspath_put.
1740 mergedpath
= aspath_merge(newpath
, aspath_dup(as4path
));
1741 aspath_free(newpath
);
1742 mergedpath
->segments
= assegment_normalise(mergedpath
->segments
);
1743 aspath_str_update(mergedpath
, false);
1745 if (BGP_DEBUG(as4
, AS4
))
1746 zlog_debug("[AS4] result of synthesizing is %s",
1752 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1753 as2's leftmost AS is same return 1. (confederation as-path
1755 bool aspath_cmp_left_confed(const struct aspath
*aspath1
,
1756 const struct aspath
*aspath2
)
1758 if (!(aspath1
&& aspath2
))
1761 if (!(aspath1
->segments
&& aspath2
->segments
))
1764 if ((aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1765 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
))
1768 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1774 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1775 * RFC 5065 section 4.1.c.1
1777 * 1) if any path segments of the AS_PATH are of the type
1778 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1779 * removed from the AS_PATH attribute, leaving the sanitized
1780 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1782 struct aspath
*aspath_delete_confed_seq(struct aspath
*aspath
)
1784 struct assegment
*seg
, *prev
, *next
;
1785 char removed_confed_segment
;
1787 if (!(aspath
&& aspath
->segments
))
1790 seg
= aspath
->segments
;
1791 removed_confed_segment
= 0;
1798 if (seg
->type
== AS_CONFED_SEQUENCE
1799 || seg
->type
== AS_CONFED_SET
) {
1800 /* This is the first segment in the aspath */
1801 if (aspath
->segments
== seg
)
1802 aspath
->segments
= seg
->next
;
1804 prev
->next
= seg
->next
;
1806 assegment_free(seg
);
1807 removed_confed_segment
= 1;
1814 if (removed_confed_segment
)
1815 aspath_str_update(aspath
, false);
1820 /* Add new AS number to the leftmost part of the aspath as
1821 AS_CONFED_SEQUENCE. */
1822 struct aspath
*aspath_add_confed_seq(struct aspath
*aspath
, as_t asno
)
1824 return aspath_add_asns(aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1827 /* Add new as value to as path structure. */
1828 static void aspath_as_add(struct aspath
*as
, as_t asno
)
1830 struct assegment
*seg
= as
->segments
;
1835 /* Last segment search procedure. */
1839 assegment_append_asns(seg
, &asno
, 1);
1842 /* Add new as segment to the as path. */
1843 static void aspath_segment_add(struct aspath
*as
, int type
)
1845 struct assegment
*seg
= as
->segments
;
1846 struct assegment
*new = assegment_new(type
, 0);
1856 struct aspath
*aspath_empty(void)
1858 return aspath_parse(NULL
, 0, 1); /* 32Bit ;-) */
1861 struct aspath
*aspath_empty_get(void)
1863 struct aspath
*aspath
;
1865 aspath
= aspath_new();
1866 aspath_make_str_count(aspath
, false);
1870 unsigned long aspath_count(void)
1872 return ashash
->count
;
1876 Theoretically, one as path can have:
1878 One BGP packet size should be less than 4096.
1879 One BGP attribute size should be less than 4096 - BGP header size.
1880 One BGP aspath size should be less than 4096 - BGP header size -
1881 BGP mandantry attribute size.
1884 /* AS path string lexical token enum. */
1889 as_token_confed_seq_start
,
1890 as_token_confed_seq_end
,
1891 as_token_confed_set_start
,
1892 as_token_confed_set_end
,
1896 /* Return next token and point for string parse. */
1897 static const char *aspath_gettoken(const char *buf
, enum as_token
*token
,
1898 unsigned long *asno
)
1900 const char *p
= buf
;
1902 /* Skip seperators (space for sequences, ',' for sets). */
1903 while (isspace((unsigned char)*p
) || *p
== ',')
1906 /* Check the end of the string and type specify characters
1912 *token
= as_token_set_start
;
1916 *token
= as_token_set_end
;
1920 *token
= as_token_confed_seq_start
;
1924 *token
= as_token_confed_seq_end
;
1928 *token
= as_token_confed_set_start
;
1932 *token
= as_token_confed_set_end
;
1937 /* Check actual AS value. */
1938 if (isdigit((unsigned char)*p
)) {
1941 *token
= as_token_asval
;
1945 while (isdigit((unsigned char)*p
)) {
1947 asval
+= (*p
- '0');
1954 /* There is no match then return unknown token. */
1955 *token
= as_token_unknown
;
1960 struct aspath
*aspath_str2aspath(const char *str
)
1962 enum as_token token
= as_token_unknown
;
1963 unsigned short as_type
;
1964 unsigned long asno
= 0;
1965 struct aspath
*aspath
;
1968 aspath
= aspath_new();
1970 /* We start default type as AS_SEQUENCE. */
1971 as_type
= AS_SEQUENCE
;
1974 while ((str
= aspath_gettoken(str
, &token
, &asno
)) != NULL
) {
1976 case as_token_asval
:
1978 aspath_segment_add(aspath
, as_type
);
1981 aspath_as_add(aspath
, asno
);
1983 case as_token_set_start
:
1985 aspath_segment_add(aspath
, as_type
);
1988 case as_token_set_end
:
1989 as_type
= AS_SEQUENCE
;
1992 case as_token_confed_seq_start
:
1993 as_type
= AS_CONFED_SEQUENCE
;
1994 aspath_segment_add(aspath
, as_type
);
1997 case as_token_confed_seq_end
:
1998 as_type
= AS_SEQUENCE
;
2001 case as_token_confed_set_start
:
2002 as_type
= AS_CONFED_SET
;
2003 aspath_segment_add(aspath
, as_type
);
2006 case as_token_confed_set_end
:
2007 as_type
= AS_SEQUENCE
;
2010 case as_token_unknown
:
2012 aspath_free(aspath
);
2017 aspath_make_str_count(aspath
, false);
2022 /* Make hash value by raw aspath data. */
2023 unsigned int aspath_key_make(const void *p
)
2025 const struct aspath
*aspath
= p
;
2026 unsigned int key
= 0;
2029 aspath_str_update((struct aspath
*)aspath
, false);
2031 key
= jhash(aspath
->str
, aspath
->str_len
, 2334325);
2036 /* If two aspath have same value then return 1 else return 0 */
2037 bool aspath_cmp(const void *arg1
, const void *arg2
)
2039 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2040 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2042 while (seg1
|| seg2
) {
2044 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2046 if (seg1
->type
!= seg2
->type
)
2048 if (seg1
->length
!= seg2
->length
)
2050 for (i
= 0; i
< seg1
->length
; i
++)
2051 if (seg1
->as
[i
] != seg2
->as
[i
])
2059 /* AS path hash initialize. */
2060 void aspath_init(void)
2062 ashash
= hash_create_size(32768, aspath_key_make
, aspath_cmp
,
2066 void aspath_finish(void)
2068 hash_clean(ashash
, (void (*)(void *))aspath_free
);
2073 stream_free(snmp_stream
);
2076 /* return and as path value */
2077 const char *aspath_print(struct aspath
*as
)
2079 return (as
? as
->str
: NULL
);
2082 /* Printing functions */
2083 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
2084 * AS_PATH wasn't empty.
2086 void aspath_print_vty(struct vty
*vty
, const char *format
, struct aspath
*as
,
2090 vty_out(vty
, format
, as
->str
);
2091 if (as
->str_len
&& strlen(suffix
))
2092 vty_out(vty
, "%s", suffix
);
2095 static void aspath_show_all_iterator(struct hash_bucket
*bucket
,
2100 as
= (struct aspath
*)bucket
->data
;
2102 vty_out(vty
, "[%p:%u] (%ld) ", (void *)bucket
, bucket
->key
, as
->refcnt
);
2103 vty_out(vty
, "%s\n", as
->str
);
2106 /* Print all aspath and hash information. This function is used from
2107 `show [ip] bgp paths' command. */
2108 void aspath_print_all_vty(struct vty
*vty
)
2110 hash_iterate(ashash
, (void (*)(struct hash_bucket
*,
2111 void *))aspath_show_all_iterator
,
2115 static struct aspath
*bgp_aggr_aspath_lookup(struct bgp_aggregate
*aggregate
,
2116 struct aspath
*aspath
)
2118 return hash_lookup(aggregate
->aspath_hash
, aspath
);
2121 static void *bgp_aggr_aspath_hash_alloc(void *p
)
2123 struct aspath
*ref
= (struct aspath
*)p
;
2124 struct aspath
*aspath
= NULL
;
2126 aspath
= aspath_dup(ref
);
2130 static void bgp_aggr_aspath_prepare(struct hash_bucket
*hb
, void *arg
)
2132 struct aspath
*hb_aspath
= hb
->data
;
2133 struct aspath
**aggr_aspath
= arg
;
2136 *aggr_aspath
= aspath_aggregate(*aggr_aspath
, hb_aspath
);
2138 *aggr_aspath
= aspath_dup(hb_aspath
);
2141 void bgp_aggr_aspath_remove(void *arg
)
2143 struct aspath
*aspath
= arg
;
2145 aspath_free(aspath
);
2148 void bgp_compute_aggregate_aspath(struct bgp_aggregate
*aggregate
,
2149 struct aspath
*aspath
)
2151 bgp_compute_aggregate_aspath_hash(aggregate
, aspath
);
2153 bgp_compute_aggregate_aspath_val(aggregate
);
2157 void bgp_compute_aggregate_aspath_hash(struct bgp_aggregate
*aggregate
,
2158 struct aspath
*aspath
)
2160 struct aspath
*aggr_aspath
= NULL
;
2162 if ((aggregate
== NULL
) || (aspath
== NULL
))
2165 /* Create hash if not already created.
2167 if (aggregate
->aspath_hash
== NULL
)
2168 aggregate
->aspath_hash
= hash_create(
2169 aspath_key_make
, aspath_cmp
,
2170 "BGP Aggregator as-path hash");
2172 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2173 if (aggr_aspath
== NULL
) {
2174 /* Insert as-path into hash.
2176 aggr_aspath
= hash_get(aggregate
->aspath_hash
, aspath
,
2177 bgp_aggr_aspath_hash_alloc
);
2180 /* Increment reference counter.
2182 aggr_aspath
->refcnt
++;
2185 void bgp_compute_aggregate_aspath_val(struct bgp_aggregate
*aggregate
)
2187 if (aggregate
== NULL
)
2189 /* Re-compute aggregate's as-path.
2191 if (aggregate
->aspath
) {
2192 aspath_free(aggregate
->aspath
);
2193 aggregate
->aspath
= NULL
;
2195 if (aggregate
->aspath_hash
2196 && aggregate
->aspath_hash
->count
) {
2197 hash_iterate(aggregate
->aspath_hash
,
2198 bgp_aggr_aspath_prepare
,
2199 &aggregate
->aspath
);
2203 void bgp_remove_aspath_from_aggregate(struct bgp_aggregate
*aggregate
,
2204 struct aspath
*aspath
)
2206 struct aspath
*aggr_aspath
= NULL
;
2207 struct aspath
*ret_aspath
= NULL
;
2210 || (!aggregate
->aspath_hash
)
2214 /* Look-up the aspath in the hash.
2216 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2218 aggr_aspath
->refcnt
--;
2220 if (aggr_aspath
->refcnt
== 0) {
2221 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2223 aspath_free(ret_aspath
);
2226 /* Remove aggregate's old as-path.
2228 aspath_free(aggregate
->aspath
);
2229 aggregate
->aspath
= NULL
;
2231 bgp_compute_aggregate_aspath_val(aggregate
);
2236 void bgp_remove_aspath_from_aggregate_hash(struct bgp_aggregate
*aggregate
,
2237 struct aspath
*aspath
)
2239 struct aspath
*aggr_aspath
= NULL
;
2240 struct aspath
*ret_aspath
= NULL
;
2243 || (!aggregate
->aspath_hash
)
2247 /* Look-up the aspath in the hash.
2249 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2251 aggr_aspath
->refcnt
--;
2253 if (aggr_aspath
->refcnt
== 0) {
2254 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2256 aspath_free(ret_aspath
);