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 *aspath_segment_type_str
[] = {"as-invalid", "as-set", "as-sequence",
106 "as-confed-sequence", "as-confed-set"};
108 /* Get a new segment. Note that 0 is an allowed length,
109 * and will result in a segment with no allocated data segment.
110 * the caller should immediately assign data to the segment, as the segment
111 * otherwise is not generally valid
113 static struct assegment
*assegment_new(uint8_t type
, unsigned short length
)
115 struct assegment
*new;
117 new = XCALLOC(MTYPE_AS_SEG
, sizeof(struct assegment
));
120 new->as
= assegment_data_new(length
);
122 new->length
= length
;
128 static void assegment_free(struct assegment
*seg
)
134 assegment_data_free(seg
->as
);
135 memset(seg
, 0xfe, sizeof(struct assegment
));
136 XFREE(MTYPE_AS_SEG
, seg
);
141 /* free entire chain of segments */
142 static void assegment_free_all(struct assegment
*seg
)
144 struct assegment
*prev
;
149 assegment_free(prev
);
153 /* Duplicate just the given assegment and its data */
154 static struct assegment
*assegment_dup(struct assegment
*seg
)
156 struct assegment
*new;
158 new = assegment_new(seg
->type
, seg
->length
);
159 memcpy(new->as
, seg
->as
, ASSEGMENT_DATA_SIZE(new->length
, 1));
164 /* Duplicate entire chain of assegments, return the head */
165 static struct assegment
*assegment_dup_all(struct assegment
*seg
)
167 struct assegment
*new = NULL
;
168 struct assegment
*head
= NULL
;
172 new->next
= assegment_dup(seg
);
175 head
= new = assegment_dup(seg
);
182 /* prepend the as number to given segment, given num of times */
183 static struct assegment
*assegment_prepend_asns(struct assegment
*seg
,
192 if (num
>= AS_SEGMENT_MAX
)
193 return seg
; /* we don't do huge prepends */
195 if ((newas
= assegment_data_new(seg
->length
+ num
)) == NULL
)
198 for (i
= 0; i
< num
; i
++)
201 memcpy(newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE(seg
->length
, 1));
202 assegment_data_free(seg
->as
);
209 /* append given array of as numbers to the segment */
210 static struct assegment
*assegment_append_asns(struct assegment
*seg
,
211 as_t
*asnos
, int num
)
215 newas
= XREALLOC(MTYPE_AS_SEG_DATA
, seg
->as
,
216 ASSEGMENT_DATA_SIZE(seg
->length
+ num
, 1));
219 memcpy(seg
->as
+ seg
->length
, asnos
,
220 ASSEGMENT_DATA_SIZE(num
, 1));
225 static int int_cmp(const void *p1
, const void *p2
)
227 const as_t
*as1
= p1
;
228 const as_t
*as2
= p2
;
230 return (*as1
== *as2
) ? 0 : ((*as1
> *as2
) ? 1 : -1);
233 /* normalise the segment.
234 * In particular, merge runs of AS_SEQUENCEs into one segment
235 * Internally, we do not care about the wire segment length limit, and
236 * we want each distinct AS_PATHs to have the exact same internal
237 * representation - eg, so that our hashing actually works..
239 static struct assegment
*assegment_normalise(struct assegment
*head
)
241 struct assegment
*seg
= head
, *pin
;
242 struct assegment
*tmp
;
250 /* Sort values SET segments, for determinism in paths to aid
251 * creation of hash values / path comparisons
252 * and because it helps other lesser implementations ;)
254 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
) {
258 qsort(seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
261 for (i
= 1; i
< seg
->length
; i
++) {
262 if (seg
->as
[tail
] == seg
->as
[i
])
267 seg
->as
[tail
] = seg
->as
[i
];
269 /* seg->length can be 0.. */
271 seg
->length
= tail
+ 1;
274 /* read ahead from the current, pinned segment while the
276 * are packable/mergeable. Append all following packable
278 * to the segment we have pinned and remove these appended
281 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
)) {
285 /* append the next sequence to the pinned sequence */
286 pin
= assegment_append_asns(pin
, seg
->as
, seg
->length
);
288 /* bypass the next sequence */
289 pin
->next
= seg
->next
;
291 /* get rid of the now referenceless segment */
300 static struct aspath
*aspath_new(void)
302 return XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
305 /* Free AS path structure. */
306 void aspath_free(struct aspath
*aspath
)
310 if (aspath
->segments
)
311 assegment_free_all(aspath
->segments
);
313 XFREE(MTYPE_AS_STR
, aspath
->str
);
316 json_object_free(aspath
->json
);
320 XFREE(MTYPE_AS_PATH
, aspath
);
323 /* Unintern aspath from AS path bucket. */
324 void aspath_unintern(struct aspath
**aspath
)
327 struct aspath
*asp
= *aspath
;
332 if (asp
->refcnt
== 0) {
333 /* This aspath must exist in aspath hash table. */
334 ret
= hash_release(ashash
, asp
);
341 /* Return the start or end delimiters for a particular Segment type */
342 #define AS_SEG_START 0
344 static char aspath_delimiter_char(uint8_t type
, uint8_t which
)
351 } aspath_delim_char
[] = {{AS_SET
, '{', '}'},
352 {AS_CONFED_SET
, '[', ']'},
353 {AS_CONFED_SEQUENCE
, '(', ')'},
356 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++) {
357 if (aspath_delim_char
[i
].type
== type
) {
358 if (which
== AS_SEG_START
)
359 return aspath_delim_char
[i
].start
;
360 else if (which
== AS_SEG_END
)
361 return aspath_delim_char
[i
].end
;
367 /* countup asns from this segment and index onward */
368 static int assegment_count_asns(struct assegment
*seg
, int from
)
373 count
+= seg
->length
;
375 count
+= (seg
->length
- from
);
383 unsigned int aspath_count_confeds(struct aspath
*aspath
)
386 struct assegment
*seg
= aspath
->segments
;
389 if (seg
->type
== AS_CONFED_SEQUENCE
)
390 count
+= seg
->length
;
391 else if (seg
->type
== AS_CONFED_SET
)
399 unsigned int aspath_count_hops(const struct aspath
*aspath
)
402 struct assegment
*seg
= aspath
->segments
;
405 if (seg
->type
== AS_SEQUENCE
)
406 count
+= seg
->length
;
407 else if (seg
->type
== AS_SET
)
415 /* Estimate size aspath /might/ take if encoded into an
418 * This is a quick estimate, not definitive! aspath_put()
419 * may return a different number!!
421 unsigned int aspath_size(struct aspath
*aspath
)
424 struct assegment
*seg
= aspath
->segments
;
427 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
433 /* Return highest public ASN in path */
434 as_t
aspath_highest(struct aspath
*aspath
)
436 struct assegment
*seg
= aspath
->segments
;
441 for (i
= 0; i
< seg
->length
; i
++)
442 if (seg
->as
[i
] > highest
443 && !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
444 highest
= seg
->as
[i
];
450 /* Return the left-most ASN in path */
451 as_t
aspath_leftmost(struct aspath
*aspath
)
453 struct assegment
*seg
= aspath
->segments
;
456 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
457 leftmost
= seg
->as
[0];
462 /* Return 1 if there are any 4-byte ASes in the path */
463 unsigned int aspath_has_as4(struct aspath
*aspath
)
465 struct assegment
*seg
= aspath
->segments
;
469 for (i
= 0; i
< seg
->length
; i
++)
470 if (seg
->as
[i
] > BGP_AS_MAX
)
477 /* Convert aspath structure to string expression. */
478 static void aspath_make_str_count(struct aspath
*as
, bool make_json
)
480 struct assegment
*seg
;
484 json_object
*jaspath_segments
= NULL
;
485 json_object
*jseg
= NULL
;
486 json_object
*jseg_list
= NULL
;
489 as
->json
= json_object_new_object();
490 jaspath_segments
= json_object_new_array();
496 json_object_string_add(as
->json
, "string", "Local");
497 json_object_object_add(as
->json
, "segments",
499 json_object_int_add(as
->json
, "length", 0);
501 as
->str
= XMALLOC(MTYPE_AS_STR
, 1);
509 /* ASN takes 5 to 10 chars plus seperator, see below.
510 * If there is one differing segment type, we need an additional
511 * 2 chars for segment delimiters, and the final '\0'.
512 * Hopefully this is large enough to avoid hitting the realloc
513 * code below for most common sequences.
515 * This was changed to 10 after the well-known BGP assertion, which
516 * had hit some parts of the Internet in May of 2009.
518 #define ASN_STR_LEN (10 + 1)
519 str_size
= MAX(assegment_count_asns(seg
, 0) * ASN_STR_LEN
+ 2 + 1,
520 ASPATH_STR_DEFAULT_LEN
);
521 str_buf
= XMALLOC(MTYPE_AS_STR
, str_size
);
527 /* Check AS type validity. Set seperator for segment */
534 case AS_CONFED_SEQUENCE
:
538 XFREE(MTYPE_AS_STR
, str_buf
);
541 json_object_free(as
->json
);
547 /* We might need to increase str_buf, particularly if path has
548 * differing segments types, our initial guesstimate above will
549 * have been wrong. Need 10 chars for ASN, a seperator each and
550 * potentially two segment delimiters, plus a space between each
551 * segment and trailing zero.
553 * This definitely didn't work with the value of 5 bytes and
556 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
557 if ((len
+ SEGMENT_STR_LEN(seg
)) > str_size
) {
558 str_size
= len
+ SEGMENT_STR_LEN(seg
);
559 str_buf
= XREALLOC(MTYPE_AS_STR
, str_buf
, str_size
);
562 #undef SEGMENT_STR_LEN
564 if (seg
->type
!= AS_SEQUENCE
)
566 str_buf
+ len
, str_size
- len
, "%c",
567 aspath_delimiter_char(seg
->type
, AS_SEG_START
));
570 jseg_list
= json_object_new_array();
572 /* write out the ASNs, with their seperators, bar the last one*/
573 for (i
= 0; i
< seg
->length
; i
++) {
575 json_object_array_add(
577 json_object_new_int(seg
->as
[i
]));
579 len
+= snprintf(str_buf
+ len
, str_size
- len
, "%u",
582 if (i
< (seg
->length
- 1))
583 len
+= snprintf(str_buf
+ len
, str_size
- len
,
588 jseg
= json_object_new_object();
589 json_object_string_add(
591 aspath_segment_type_str
[seg
->type
]);
592 json_object_object_add(jseg
, "list", jseg_list
);
593 json_object_array_add(jaspath_segments
, jseg
);
596 if (seg
->type
!= AS_SEQUENCE
)
598 str_buf
+ len
, str_size
- len
, "%c",
599 aspath_delimiter_char(seg
->type
, AS_SEG_END
));
601 len
+= snprintf(str_buf
+ len
, str_size
- len
, " ");
606 assert(len
< str_size
);
613 json_object_string_add(as
->json
, "string", str_buf
);
614 json_object_object_add(as
->json
, "segments", jaspath_segments
);
615 json_object_int_add(as
->json
, "length", aspath_count_hops(as
));
621 void aspath_str_update(struct aspath
*as
, bool make_json
)
624 XFREE(MTYPE_AS_STR
, as
->str
);
627 json_object_free(as
->json
);
631 aspath_make_str_count(as
, make_json
);
634 /* Intern allocated AS path. */
635 struct aspath
*aspath_intern(struct aspath
*aspath
)
639 /* Assert this AS path structure is not interned and has the string
640 representation built. */
641 assert(aspath
->refcnt
== 0);
644 /* Check AS path hash. */
645 find
= hash_get(ashash
, aspath
, hash_alloc_intern
);
654 /* Duplicate aspath structure. Created same aspath structure but
655 reference count and AS path string is cleared. */
656 struct aspath
*aspath_dup(struct aspath
*aspath
)
658 unsigned short buflen
= aspath
->str_len
+ 1;
661 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
664 if (aspath
->segments
)
665 new->segments
= assegment_dup_all(aspath
->segments
);
670 new->str
= XMALLOC(MTYPE_AS_STR
, buflen
);
671 new->str_len
= aspath
->str_len
;
673 /* copy the string data */
674 if (aspath
->str_len
> 0)
675 memcpy(new->str
, aspath
->str
, buflen
);
682 static void *aspath_hash_alloc(void *arg
)
684 const struct aspath
*aspath
= arg
;
687 /* Malformed AS path value. */
690 /* New aspath structure is needed. */
691 new = XMALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
693 /* Reuse segments and string representation */
695 new->segments
= aspath
->segments
;
696 new->str
= aspath
->str
;
697 new->str_len
= aspath
->str_len
;
698 new->json
= aspath
->json
;
703 /* parse as-segment byte stream in struct assegment */
704 static int assegments_parse(struct stream
*s
, size_t length
,
705 struct assegment
**result
, int use32bit
)
707 struct assegment_header segh
;
708 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
711 /* empty aspath (ie iBGP or somesuch) */
715 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
717 "[AS4SEG] Parse aspath segment: got total byte length %lu",
718 (unsigned long)length
);
720 if ((STREAM_READABLE(s
) < length
)
721 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
722 || (length
% AS16_VALUE_SIZE
))
725 while (bytes
< length
) {
729 if ((length
- bytes
) <= AS_HEADER_SIZE
) {
731 assegment_free_all(head
);
735 /* softly softly, get the header first on its own */
736 segh
.type
= stream_getc(s
);
737 segh
.length
= stream_getc(s
);
739 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
741 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
743 "[AS4SEG] Parse aspath segment: got type %d, length %d",
744 segh
.type
, segh
.length
);
747 if (((bytes
+ seg_size
) > length
)
748 /* 1771bis 4.3b: seg length contains one or more */
749 || (segh
.length
== 0)
750 /* Paranoia in case someone changes type of segment length.
751 * Shift both values by 0x10 to make the comparison operate
752 * on more, than 8 bits (otherwise it's a warning, bug
755 || ((sizeof segh
.length
> 1)
756 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
))) {
758 assegment_free_all(head
);
765 case AS_CONFED_SEQUENCE
:
770 assegment_free_all(head
);
774 /* now its safe to trust lengths */
775 seg
= assegment_new(segh
.type
, segh
.length
);
779 else /* it's the first segment */
782 for (i
= 0; i
< segh
.length
; i
++)
784 (use32bit
) ? stream_getl(s
) : stream_getw(s
);
788 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
790 "[AS4SEG] Parse aspath segment: Bytes now: %lu",
791 (unsigned long)bytes
);
796 *result
= assegment_normalise(head
);
800 /* AS path parse function. pnt is a pointer to byte stream and length
801 is length of byte stream. If there is same AS path in the the AS
802 path hash then return it else make new AS path structure.
804 On error NULL is returned.
806 struct aspath
*aspath_parse(struct stream
*s
, size_t length
, int use32bit
)
811 /* If length is odd it's malformed AS path. */
812 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
813 * otherwise its malformed when length is larger than 2 and (length-2)
814 * is not dividable by 4.
815 * But... this time we're lazy
817 if (length
% AS16_VALUE_SIZE
)
820 memset(&as
, 0, sizeof(struct aspath
));
821 if (assegments_parse(s
, length
, &as
.segments
, use32bit
) < 0)
824 /* If already same aspath exist then return it. */
825 find
= hash_get(ashash
, &as
, aspath_hash_alloc
);
827 /* bug! should not happen, let the daemon crash below */
830 /* if the aspath was already hashed free temporary memory. */
832 assegment_free_all(as
.segments
);
833 /* aspath_key_make() always updates the string */
834 XFREE(MTYPE_AS_STR
, as
.str
);
836 json_object_free(as
.json
);
846 static void assegment_data_put(struct stream
*s
, as_t
*as
, int num
,
850 assert(num
<= AS_SEGMENT_MAX
);
852 for (i
= 0; i
< num
; i
++)
854 stream_putl(s
, as
[i
]);
856 if (as
[i
] <= BGP_AS_MAX
)
857 stream_putw(s
, as
[i
]);
859 stream_putw(s
, BGP_AS_TRANS
);
863 static size_t assegment_header_put(struct stream
*s
, uint8_t type
, int length
)
866 assert(length
<= AS_SEGMENT_MAX
);
867 stream_putc(s
, type
);
868 lenp
= stream_get_endp(s
);
869 stream_putc(s
, length
);
873 /* write aspath data to stream */
874 size_t aspath_put(struct stream
*s
, struct aspath
*as
, int use32bit
)
876 struct assegment
*seg
= as
->segments
;
879 if (!seg
|| seg
->length
== 0)
884 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
885 * At the moment, we would write out a partial aspath, and our
887 * will complain and drop the session :-/
889 * The general assumption here is that many things tested will
890 * never happen. And, in real live, up to now, they have not.
892 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
)
893 <= STREAM_WRITEABLE(s
))) {
894 struct assegment
*next
= seg
->next
;
899 /* Overlength segments have to be split up */
900 while ((seg
->length
- written
) > AS_SEGMENT_MAX
) {
901 assegment_header_put(s
, seg
->type
,
903 assegment_data_put(s
, (seg
->as
+ written
), AS_SEGMENT_MAX
,
905 written
+= AS_SEGMENT_MAX
;
906 bytes
+= ASSEGMENT_SIZE(AS_SEGMENT_MAX
,
910 /* write the final segment, probably is also the first
912 lenp
= assegment_header_put(s
, seg
->type
,
913 seg
->length
- written
);
914 assegment_data_put(s
, (seg
->as
+ written
),
915 seg
->length
- written
, use32bit
);
917 /* Sequence-type segments can be 'packed' together
918 * Case of a segment which was overlength and split up
919 * will be missed here, but that doesn't matter.
921 while (next
&& ASSEGMENTS_PACKABLE(seg
, next
)) {
922 /* NB: We should never normally get here given
924 * normalise aspath data when parse them.
926 * safe than sorry. We potentially could call
927 * assegment_normalise here instead, but it's
929 * easier to do it on the fly here rather than
931 * the segment list twice every time we write
936 /* Next segment's data can fit in this one */
937 assegment_data_put(s
, next
->as
, next
->length
,
940 /* update the length of the segment header */
941 stream_putc_at(s
, lenp
,
942 seg
->length
- written
944 asns_packed
+= next
->length
;
949 bytes
+= ASSEGMENT_SIZE(
950 seg
->length
- written
+ asns_packed
, use32bit
);
957 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
958 * We have no way to manage the storage, so we use a static stream
959 * wrapper around aspath_put.
961 uint8_t *aspath_snmp_pathseg(struct aspath
*as
, size_t *varlen
)
963 #define SNMP_PATHSEG_MAX 1024
966 snmp_stream
= stream_new(SNMP_PATHSEG_MAX
);
968 stream_reset(snmp_stream
);
974 aspath_put(snmp_stream
, as
, 0); /* use 16 bit for now here */
976 *varlen
= stream_get_endp(snmp_stream
);
977 return stream_pnt(snmp_stream
);
980 #define min(A,B) ((A) < (B) ? (A) : (B))
982 static struct assegment
*aspath_aggregate_as_set_add(struct aspath
*aspath
,
983 struct assegment
*asset
,
988 /* If this is first AS set member, create new as-set segment. */
990 asset
= assegment_new(AS_SET
, 1);
991 if (!aspath
->segments
)
992 aspath
->segments
= asset
;
994 struct assegment
*seg
= aspath
->segments
;
999 asset
->type
= AS_SET
;
1003 /* Check this AS value already exists or not. */
1004 for (i
= 0; i
< asset
->length
; i
++)
1005 if (asset
->as
[i
] == as
)
1009 asset
->as
= XREALLOC(MTYPE_AS_SEG_DATA
, asset
->as
,
1010 asset
->length
* AS_VALUE_SIZE
);
1011 asset
->as
[asset
->length
- 1] = as
;
1018 /* Modify as1 using as2 for aggregation. */
1019 struct aspath
*aspath_aggregate(struct aspath
*as1
, struct aspath
*as2
)
1025 struct assegment
*seg1
= as1
->segments
;
1026 struct assegment
*seg2
= as2
->segments
;
1027 struct aspath
*aspath
= NULL
;
1028 struct assegment
*asset
= NULL
;
1029 struct assegment
*prevseg
= NULL
;
1031 /* First of all check common leading sequence. */
1032 while (seg1
&& seg2
) {
1033 /* Check segment type. */
1034 if (seg1
->type
!= seg2
->type
)
1037 /* Minimum segment length. */
1038 minlen
= min(seg1
->length
, seg2
->length
);
1040 for (match
= 0; match
< minlen
; match
++)
1041 if (seg1
->as
[match
] != seg2
->as
[match
])
1045 struct assegment
*seg
= assegment_new(seg1
->type
, 0);
1047 seg
= assegment_append_asns(seg
, seg1
->as
, match
);
1050 aspath
= aspath_new();
1051 aspath
->segments
= seg
;
1053 prevseg
->next
= seg
;
1058 if (match
!= minlen
|| match
!= seg1
->length
1059 || seg1
->length
!= seg2
->length
)
1061 /* We are moving on to the next segment to reset match */
1070 aspath
= aspath_new();
1072 /* Make as-set using rest of all information. */
1075 for (i
= from
; i
< seg1
->length
; i
++)
1076 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1085 for (i
= from
; i
< seg2
->length
; i
++)
1086 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1093 assegment_normalise(aspath
->segments
);
1094 aspath_str_update(aspath
, false);
1098 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1099 attribute, check the leftmost AS number in the AS_PATH attribute is
1100 or not the peer's AS number. */
1101 int aspath_firstas_check(struct aspath
*aspath
, as_t asno
)
1103 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1106 if (aspath
->segments
&& (aspath
->segments
->type
== AS_SEQUENCE
)
1107 && (aspath
->segments
->as
[0] == asno
))
1113 unsigned int aspath_get_first_as(struct aspath
*aspath
)
1115 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1118 return aspath
->segments
->as
[0];
1121 unsigned int aspath_get_last_as(struct aspath
*aspath
)
1124 unsigned int last_as
= 0;
1125 const struct assegment
*seg
;
1127 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1130 seg
= aspath
->segments
;
1133 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1134 for (i
= 0; i
< seg
->length
; i
++)
1135 last_as
= seg
->as
[i
];
1142 /* AS path loop check. If aspath contains asno then return >= 1. */
1143 int aspath_loop_check(struct aspath
*aspath
, as_t asno
)
1145 struct assegment
*seg
;
1148 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1151 seg
= aspath
->segments
;
1156 for (i
= 0; i
< seg
->length
; i
++)
1157 if (seg
->as
[i
] == asno
)
1165 /* When all of AS path is private AS return 1. */
1166 int aspath_private_as_check(struct aspath
*aspath
)
1168 struct assegment
*seg
;
1170 if (!(aspath
&& aspath
->segments
))
1173 seg
= aspath
->segments
;
1178 for (i
= 0; i
< seg
->length
; i
++) {
1179 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1187 /* Return True if the entire ASPATH consist of the specified ASN */
1188 int aspath_single_asn_check(struct aspath
*aspath
, as_t asn
)
1190 struct assegment
*seg
;
1192 if (!(aspath
&& aspath
->segments
))
1195 seg
= aspath
->segments
;
1200 for (i
= 0; i
< seg
->length
; i
++) {
1201 if (seg
->as
[i
] != asn
)
1209 /* Replace all instances of the target ASN with our own ASN */
1210 struct aspath
*aspath_replace_specific_asn(struct aspath
*aspath
,
1211 as_t target_asn
, as_t our_asn
)
1214 struct assegment
*seg
;
1216 new = aspath_dup(aspath
);
1217 seg
= new->segments
;
1222 for (i
= 0; i
< seg
->length
; i
++) {
1223 if (seg
->as
[i
] == target_asn
)
1224 seg
->as
[i
] = our_asn
;
1229 aspath_str_update(new, false);
1233 /* Replace all private ASNs with our own ASN */
1234 struct aspath
*aspath_replace_private_asns(struct aspath
*aspath
, as_t asn
)
1237 struct assegment
*seg
;
1239 new = aspath_dup(aspath
);
1240 seg
= new->segments
;
1245 for (i
= 0; i
< seg
->length
; i
++) {
1246 if (BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1252 aspath_str_update(new, false);
1256 /* Remove all private ASNs */
1257 struct aspath
*aspath_remove_private_asns(struct aspath
*aspath
)
1260 struct assegment
*seg
;
1261 struct assegment
*new_seg
;
1262 struct assegment
*last_new_seg
;
1267 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
1271 last_new_seg
= NULL
;
1272 seg
= aspath
->segments
;
1276 for (i
= 0; i
< seg
->length
; i
++) {
1278 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1284 // The entire segment is private so skip it
1290 // The entire segment is public so copy it
1291 else if (public == seg
->length
) {
1292 new_seg
= assegment_dup(seg
);
1295 // The segment is a mix of public and private ASNs. Copy as many
1297 // there are public ASNs then come back and fill in only the
1300 new_seg
= assegment_new(seg
->type
, public);
1302 for (i
= 0; i
< seg
->length
; i
++) {
1304 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1305 new_seg
->as
[j
] = seg
->as
[i
];
1311 // This is the first segment so set the aspath segments pointer
1314 new->segments
= new_seg
;
1316 last_new_seg
->next
= new_seg
;
1318 last_new_seg
= new_seg
;
1322 aspath_str_update(new, false);
1326 /* AS path confed check. If aspath contains confed set or sequence then return
1328 int aspath_confed_check(struct aspath
*aspath
)
1330 struct assegment
*seg
;
1332 if (!(aspath
&& aspath
->segments
))
1335 seg
= aspath
->segments
;
1338 if (seg
->type
== AS_CONFED_SET
1339 || seg
->type
== AS_CONFED_SEQUENCE
)
1346 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1347 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1348 int aspath_left_confed_check(struct aspath
*aspath
)
1351 if (!(aspath
&& aspath
->segments
))
1354 if ((aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1355 || (aspath
->segments
->type
== AS_CONFED_SET
))
1361 /* Merge as1 to as2. as2 should be uninterned aspath. */
1362 static struct aspath
*aspath_merge(struct aspath
*as1
, struct aspath
*as2
)
1364 struct assegment
*last
, *new;
1369 last
= new = assegment_dup_all(as1
->segments
);
1371 /* find the last valid segment */
1372 while (last
&& last
->next
)
1375 last
->next
= as2
->segments
;
1376 as2
->segments
= new;
1377 aspath_str_update(as2
, false);
1381 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1382 struct aspath
*aspath_prepend(struct aspath
*as1
, struct aspath
*as2
)
1384 struct assegment
*seg1
;
1385 struct assegment
*seg2
;
1390 seg1
= as1
->segments
;
1391 seg2
= as2
->segments
;
1393 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1395 as2
->segments
= assegment_dup_all(as1
->segments
);
1396 aspath_str_update(as2
, false);
1400 /* If as1 is empty AS, no prepending to do. */
1404 /* find the tail as1's segment chain. */
1405 while (seg1
&& seg1
->next
)
1408 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1409 if (seg1
->type
== AS_SEQUENCE
&& seg2
->type
== AS_CONFED_SEQUENCE
)
1410 as2
= aspath_delete_confed_seq(as2
);
1412 /* Compare last segment type of as1 and first segment type of as2. */
1413 if (seg1
->type
!= seg2
->type
)
1414 return aspath_merge(as1
, as2
);
1416 if (seg1
->type
== AS_SEQUENCE
) {
1417 /* We have two chains of segments, as1->segments and seg2,
1418 * and we have to attach them together, merging the attaching
1419 * segments together into one.
1421 * 1. dupe as1->segments onto head of as2
1422 * 2. merge seg2's asns onto last segment of this new chain
1423 * 3. attach chain after seg2
1426 /* dupe as1 onto as2's head */
1427 seg1
= as2
->segments
= assegment_dup_all(as1
->segments
);
1429 /* refind the tail of as2, reusing seg1 */
1430 while (seg1
&& seg1
->next
)
1433 /* merge the old head, seg2, into tail, seg1 */
1434 seg1
= assegment_append_asns(seg1
, seg2
->as
, seg2
->length
);
1436 /* bypass the merged seg2, and attach any chain after it to
1437 * chain descending from as2's head
1439 seg1
->next
= seg2
->next
;
1441 /* seg2 is now referenceless and useless*/
1442 assegment_free(seg2
);
1444 /* we've now prepended as1's segment chain to as2, merging
1445 * the inbetween AS_SEQUENCE of seg2 in the process
1447 aspath_str_update(as2
, false);
1450 /* AS_SET merge code is needed at here. */
1451 return aspath_merge(as1
, as2
);
1453 /* XXX: Ermmm, what if as1 has multiple segments?? */
1458 /* Iterate over AS_PATH segments and wipe all occurences of the
1459 * listed AS numbers. Hence some segments may lose some or even
1460 * all data on the way, the operation is implemented as a smarter
1461 * version of aspath_dup(), which allocates memory to hold the new
1462 * data, not the original. The new AS path is returned.
1464 struct aspath
*aspath_filter_exclude(struct aspath
*source
,
1465 struct aspath
*exclude_list
)
1467 struct assegment
*srcseg
, *exclseg
, *lastseg
;
1468 struct aspath
*newpath
;
1470 newpath
= aspath_new();
1473 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
) {
1474 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1475 struct assegment
*newseg
;
1477 /* Find out, how much ASns are we going to pick from this
1479 * We can't perform filtering right inline, because the size of
1480 * the new segment isn't known at the moment yet.
1482 for (i
= 0; i
< srcseg
->length
; i
++) {
1484 for (exclseg
= exclude_list
->segments
;
1485 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1486 for (y
= 0; y
< exclseg
->length
; y
++)
1487 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1489 // There's no sense in testing
1490 // the rest of exclusion list,
1497 /* newlen is now the number of ASns to copy */
1501 /* Actual copying. Allocate memory and iterate once more,
1502 * performing filtering. */
1503 newseg
= assegment_new(srcseg
->type
, newlen
);
1504 for (i
= 0; i
< srcseg
->length
; i
++) {
1506 for (exclseg
= exclude_list
->segments
;
1507 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1508 for (y
= 0; y
< exclseg
->length
; y
++)
1509 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1515 newseg
->as
[done
++] = srcseg
->as
[i
];
1517 /* At his point newlen must be equal to done, and both must be
1519 * the filtered segment to the gross result. */
1521 newpath
->segments
= newseg
;
1523 lastseg
->next
= newseg
;
1526 aspath_str_update(newpath
, false);
1527 /* We are happy returning even an empty AS_PATH, because the
1529 * might expect this very behaviour. There's a mean to avoid this, if
1531 * by having a match rule against certain AS_PATH regexps in the
1534 aspath_free(source
);
1538 /* Add specified AS to the leftmost of aspath. */
1539 static struct aspath
*aspath_add_asns(struct aspath
*aspath
, as_t asno
,
1540 uint8_t type
, unsigned num
)
1542 struct assegment
*assegment
= aspath
->segments
;
1545 if (assegment
&& assegment
->type
== type
) {
1546 /* extend existing segment */
1548 assegment_prepend_asns(aspath
->segments
, asno
, num
);
1550 /* prepend with new segment */
1551 struct assegment
*newsegment
= assegment_new(type
, num
);
1552 for (i
= 0; i
< num
; i
++)
1553 newsegment
->as
[i
] = asno
;
1555 /* insert potentially replacing empty segment */
1556 if (assegment
&& assegment
->length
== 0) {
1557 newsegment
->next
= assegment
->next
;
1558 assegment_free(assegment
);
1560 newsegment
->next
= assegment
;
1561 aspath
->segments
= newsegment
;
1564 aspath_str_update(aspath
, false);
1568 /* Add specified AS to the leftmost of aspath num times. */
1569 struct aspath
*aspath_add_seq_n(struct aspath
*aspath
, as_t asno
, unsigned num
)
1571 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, num
);
1574 /* Add specified AS to the leftmost of aspath. */
1575 struct aspath
*aspath_add_seq(struct aspath
*aspath
, as_t asno
)
1577 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, 1);
1580 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1581 as2's leftmost AS is same return 1. */
1582 int aspath_cmp_left(const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1584 const struct assegment
*seg1
;
1585 const struct assegment
*seg2
;
1587 if (!(aspath1
&& aspath2
))
1590 seg1
= aspath1
->segments
;
1591 seg2
= aspath2
->segments
;
1593 /* If both paths are originated in this AS then we do want to compare
1598 /* find first non-confed segments for each */
1599 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1600 || (seg1
->type
== AS_CONFED_SET
)))
1603 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1604 || (seg2
->type
== AS_CONFED_SET
)))
1608 if (!(seg1
&& seg2
&& (seg1
->type
== AS_SEQUENCE
)
1609 && (seg2
->type
== AS_SEQUENCE
)))
1612 if (seg1
->as
[0] == seg2
->as
[0])
1618 /* Truncate an aspath after a number of hops, and put the hops remaining
1619 * at the front of another aspath. Needed for AS4 compat.
1621 * Returned aspath is a /new/ aspath, which should either by free'd or
1622 * interned by the caller, as desired.
1624 struct aspath
*aspath_reconcile_as4(struct aspath
*aspath
,
1625 struct aspath
*as4path
)
1627 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1628 struct aspath
*newpath
= NULL
, *mergedpath
;
1629 int hops
, cpasns
= 0;
1631 if (!aspath
|| !as4path
)
1634 seg
= aspath
->segments
;
1636 /* CONFEDs should get reconciled too.. */
1637 hops
= (aspath_count_hops(aspath
) + aspath_count_confeds(aspath
))
1638 - aspath_count_hops(as4path
);
1641 if (BGP_DEBUG(as4
, AS4
))
1643 EC_BGP_ASPATH_FEWER_HOPS
,
1644 "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1645 /* Something's gone wrong. The RFC says we should now ignore
1647 * which is daft behaviour - it contains vital loop-detection
1648 * information which must have been removed from AS_PATH.
1650 hops
= aspath_count_hops(aspath
);
1654 newpath
= aspath_dup(as4path
);
1655 aspath_str_update(newpath
, false);
1659 if (BGP_DEBUG(as4
, AS4
))
1661 "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1662 aspath
->str
, as4path
->str
);
1664 while (seg
&& hops
> 0) {
1665 switch (seg
->type
) {
1669 cpasns
= seg
->length
;
1671 case AS_CONFED_SEQUENCE
:
1672 /* Should never split a confed-sequence, if hop-count
1673 * suggests we must then something's gone wrong
1676 * Most important goal is to preserve AS_PATHs prime
1678 * as loop-detector, so we fudge the numbers so that the
1680 * confed-sequence is merged in.
1682 if (hops
< seg
->length
) {
1683 if (BGP_DEBUG(as4
, AS4
))
1685 "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1686 " across 2/4 ASN boundary somewhere, broken..");
1691 cpasns
= MIN(seg
->length
, hops
);
1692 hops
-= seg
->length
;
1695 assert(cpasns
<= seg
->length
);
1697 newseg
= assegment_new(seg
->type
, 0);
1698 newseg
= assegment_append_asns(newseg
, seg
->as
, cpasns
);
1701 newpath
= aspath_new();
1702 newpath
->segments
= newseg
;
1704 prevseg
->next
= newseg
;
1710 /* We may be able to join some segments here, and we must
1711 * do this because... we want normalised aspaths in out hash
1712 * and we do not want to stumble in aspath_put.
1714 mergedpath
= aspath_merge(newpath
, aspath_dup(as4path
));
1715 aspath_free(newpath
);
1716 mergedpath
->segments
= assegment_normalise(mergedpath
->segments
);
1717 aspath_str_update(mergedpath
, false);
1719 if (BGP_DEBUG(as4
, AS4
))
1720 zlog_debug("[AS4] result of synthesizing is %s",
1726 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1727 as2's leftmost AS is same return 1. (confederation as-path
1729 bool aspath_cmp_left_confed(const struct aspath
*aspath1
,
1730 const struct aspath
*aspath2
)
1732 if (!(aspath1
&& aspath2
))
1735 if (!(aspath1
->segments
&& aspath2
->segments
))
1738 if ((aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1739 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
))
1742 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1748 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1749 * RFC 5065 section 4.1.c.1
1751 * 1) if any path segments of the AS_PATH are of the type
1752 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1753 * removed from the AS_PATH attribute, leaving the sanitized
1754 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1756 struct aspath
*aspath_delete_confed_seq(struct aspath
*aspath
)
1758 struct assegment
*seg
, *prev
, *next
;
1759 char removed_confed_segment
;
1761 if (!(aspath
&& aspath
->segments
))
1764 seg
= aspath
->segments
;
1765 removed_confed_segment
= 0;
1772 if (seg
->type
== AS_CONFED_SEQUENCE
1773 || seg
->type
== AS_CONFED_SET
) {
1774 /* This is the first segment in the aspath */
1775 if (aspath
->segments
== seg
)
1776 aspath
->segments
= seg
->next
;
1778 prev
->next
= seg
->next
;
1780 assegment_free(seg
);
1781 removed_confed_segment
= 1;
1788 if (removed_confed_segment
)
1789 aspath_str_update(aspath
, false);
1794 /* Add new AS number to the leftmost part of the aspath as
1795 AS_CONFED_SEQUENCE. */
1796 struct aspath
*aspath_add_confed_seq(struct aspath
*aspath
, as_t asno
)
1798 return aspath_add_asns(aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1801 /* Add new as value to as path structure. */
1802 static void aspath_as_add(struct aspath
*as
, as_t asno
)
1804 struct assegment
*seg
= as
->segments
;
1809 /* Last segment search procedure. */
1813 assegment_append_asns(seg
, &asno
, 1);
1816 /* Add new as segment to the as path. */
1817 static void aspath_segment_add(struct aspath
*as
, int type
)
1819 struct assegment
*seg
= as
->segments
;
1820 struct assegment
*new = assegment_new(type
, 0);
1830 struct aspath
*aspath_empty(void)
1832 return aspath_parse(NULL
, 0, 1); /* 32Bit ;-) */
1835 struct aspath
*aspath_empty_get(void)
1837 struct aspath
*aspath
;
1839 aspath
= aspath_new();
1840 aspath_make_str_count(aspath
, false);
1844 unsigned long aspath_count(void)
1846 return ashash
->count
;
1850 Theoretically, one as path can have:
1852 One BGP packet size should be less than 4096.
1853 One BGP attribute size should be less than 4096 - BGP header size.
1854 One BGP aspath size should be less than 4096 - BGP header size -
1855 BGP mandantry attribute size.
1858 /* AS path string lexical token enum. */
1863 as_token_confed_seq_start
,
1864 as_token_confed_seq_end
,
1865 as_token_confed_set_start
,
1866 as_token_confed_set_end
,
1870 /* Return next token and point for string parse. */
1871 static const char *aspath_gettoken(const char *buf
, enum as_token
*token
,
1872 unsigned long *asno
)
1874 const char *p
= buf
;
1876 /* Skip seperators (space for sequences, ',' for sets). */
1877 while (isspace((int)*p
) || *p
== ',')
1880 /* Check the end of the string and type specify characters
1886 *token
= as_token_set_start
;
1890 *token
= as_token_set_end
;
1894 *token
= as_token_confed_seq_start
;
1898 *token
= as_token_confed_seq_end
;
1902 *token
= as_token_confed_set_start
;
1906 *token
= as_token_confed_set_end
;
1911 /* Check actual AS value. */
1912 if (isdigit((int)*p
)) {
1915 *token
= as_token_asval
;
1919 while (isdigit((int)*p
)) {
1921 asval
+= (*p
- '0');
1928 /* There is no match then return unknown token. */
1929 *token
= as_token_unknown
;
1934 struct aspath
*aspath_str2aspath(const char *str
)
1936 enum as_token token
= as_token_unknown
;
1937 unsigned short as_type
;
1938 unsigned long asno
= 0;
1939 struct aspath
*aspath
;
1942 aspath
= aspath_new();
1944 /* We start default type as AS_SEQUENCE. */
1945 as_type
= AS_SEQUENCE
;
1948 while ((str
= aspath_gettoken(str
, &token
, &asno
)) != NULL
) {
1950 case as_token_asval
:
1952 aspath_segment_add(aspath
, as_type
);
1955 aspath_as_add(aspath
, asno
);
1957 case as_token_set_start
:
1959 aspath_segment_add(aspath
, as_type
);
1962 case as_token_set_end
:
1963 as_type
= AS_SEQUENCE
;
1966 case as_token_confed_seq_start
:
1967 as_type
= AS_CONFED_SEQUENCE
;
1968 aspath_segment_add(aspath
, as_type
);
1971 case as_token_confed_seq_end
:
1972 as_type
= AS_SEQUENCE
;
1975 case as_token_confed_set_start
:
1976 as_type
= AS_CONFED_SET
;
1977 aspath_segment_add(aspath
, as_type
);
1980 case as_token_confed_set_end
:
1981 as_type
= AS_SEQUENCE
;
1984 case as_token_unknown
:
1986 aspath_free(aspath
);
1991 aspath_make_str_count(aspath
, false);
1996 /* Make hash value by raw aspath data. */
1997 unsigned int aspath_key_make(void *p
)
1999 struct aspath
*aspath
= (struct aspath
*)p
;
2000 unsigned int key
= 0;
2003 aspath_str_update(aspath
, false);
2005 key
= jhash(aspath
->str
, aspath
->str_len
, 2334325);
2010 /* If two aspath have same value then return 1 else return 0 */
2011 bool aspath_cmp(const void *arg1
, const void *arg2
)
2013 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2014 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2016 while (seg1
|| seg2
) {
2018 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2020 if (seg1
->type
!= seg2
->type
)
2022 if (seg1
->length
!= seg2
->length
)
2024 for (i
= 0; i
< seg1
->length
; i
++)
2025 if (seg1
->as
[i
] != seg2
->as
[i
])
2033 /* AS path hash initialize. */
2034 void aspath_init(void)
2036 ashash
= hash_create_size(32768, aspath_key_make
, aspath_cmp
,
2040 void aspath_finish(void)
2042 hash_clean(ashash
, (void (*)(void *))aspath_free
);
2047 stream_free(snmp_stream
);
2050 /* return and as path value */
2051 const char *aspath_print(struct aspath
*as
)
2053 return (as
? as
->str
: NULL
);
2056 /* Printing functions */
2057 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
2058 * AS_PATH wasn't empty.
2060 void aspath_print_vty(struct vty
*vty
, const char *format
, struct aspath
*as
,
2064 vty_out(vty
, format
, as
->str
);
2065 if (as
->str_len
&& strlen(suffix
))
2066 vty_out(vty
, "%s", suffix
);
2069 static void aspath_show_all_iterator(struct hash_backet
*backet
,
2074 as
= (struct aspath
*)backet
->data
;
2076 vty_out(vty
, "[%p:%u] (%ld) ", (void *)backet
, backet
->key
, as
->refcnt
);
2077 vty_out(vty
, "%s\n", as
->str
);
2080 /* Print all aspath and hash information. This function is used from
2081 `show [ip] bgp paths' command. */
2082 void aspath_print_all_vty(struct vty
*vty
)
2084 hash_iterate(ashash
, (void (*)(struct hash_backet
*,
2085 void *))aspath_show_all_iterator
,