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
18 along with GNU Zebra; see the file COPYING. If not, write to the Free
19 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
35 #include "bgpd/bgpd.h"
36 #include "bgpd/bgp_aspath.h"
37 #include "bgpd/bgp_debug.h"
38 #include "bgpd/bgp_attr.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) \
75 && ((X)->type == AS_SEQUENCE))
76 /* Types and length of X,Y suitable for packing? */
77 #define ASSEGMENTS_PACKABLE(X,Y) \
78 ( ASSEGMENT_TYPES_PACKABLE( (X), (Y)) \
79 && ( ((X)->length + (Y)->length) <= AS_SEGMENT_MAX ) )
81 /* As segment header - the on-wire representation
82 * NOT the internal representation!
84 struct assegment_header
90 /* Hash for aspath. This is the top level structure of AS path. */
91 static struct hash
*ashash
;
93 /* Stream for SNMP. See aspath_snmp_pathseg */
94 static struct stream
*snmp_stream
;
96 /* Callers are required to initialize the memory */
98 assegment_data_new (int num
)
100 return (XMALLOC (MTYPE_AS_SEG_DATA
, ASSEGMENT_DATA_SIZE (num
, 1)));
104 assegment_data_free (as_t
*asdata
)
106 XFREE (MTYPE_AS_SEG_DATA
, asdata
);
109 const char *aspath_segment_type_str
[] = {
113 "as-confed-sequence",
117 /* Get a new segment. Note that 0 is an allowed length,
118 * and will result in a segment with no allocated data segment.
119 * the caller should immediately assign data to the segment, as the segment
120 * otherwise is not generally valid
122 static struct assegment
*
123 assegment_new (u_char type
, u_short length
)
125 struct assegment
*new;
127 new = XCALLOC (MTYPE_AS_SEG
, sizeof (struct assegment
));
130 new->as
= assegment_data_new (length
);
132 new->length
= length
;
139 assegment_free (struct assegment
*seg
)
145 assegment_data_free (seg
->as
);
146 memset (seg
, 0xfe, sizeof(struct assegment
));
147 XFREE (MTYPE_AS_SEG
, seg
);
152 /* free entire chain of segments */
154 assegment_free_all (struct assegment
*seg
)
156 struct assegment
*prev
;
162 assegment_free (prev
);
166 /* Duplicate just the given assegment and its data */
167 static struct assegment
*
168 assegment_dup (struct assegment
*seg
)
170 struct assegment
*new;
172 new = assegment_new (seg
->type
, seg
->length
);
173 memcpy (new->as
, seg
->as
, ASSEGMENT_DATA_SIZE (new->length
, 1) );
178 /* Duplicate entire chain of assegments, return the head */
179 static struct assegment
*
180 assegment_dup_all (struct assegment
*seg
)
182 struct assegment
*new = NULL
;
183 struct assegment
*head
= NULL
;
189 new->next
= assegment_dup (seg
);
193 head
= new = assegment_dup (seg
);
200 /* prepend the as number to given segment, given num of times */
201 static struct assegment
*
202 assegment_prepend_asns (struct assegment
*seg
, as_t asnum
, int num
)
210 if (num
>= AS_SEGMENT_MAX
)
211 return seg
; /* we don't do huge prepends */
213 if ((newas
= assegment_data_new (seg
->length
+ num
)) == NULL
)
216 for (i
= 0; i
< num
; i
++)
219 memcpy (newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE (seg
->length
, 1));
220 assegment_data_free (seg
->as
);
227 /* append given array of as numbers to the segment */
228 static struct assegment
*
229 assegment_append_asns (struct assegment
*seg
, as_t
*asnos
, int num
)
233 newas
= XREALLOC (MTYPE_AS_SEG_DATA
, seg
->as
,
234 ASSEGMENT_DATA_SIZE (seg
->length
+ num
, 1));
239 memcpy (seg
->as
+ seg
->length
, asnos
, ASSEGMENT_DATA_SIZE(num
, 1));
244 assegment_free_all (seg
);
249 int_cmp (const void *p1
, const void *p2
)
251 const as_t
*as1
= p1
;
252 const as_t
*as2
= p2
;
254 return (*as1
== *as2
)
255 ? 0 : ( (*as1
> *as2
) ? 1 : -1);
258 /* normalise the segment.
259 * In particular, merge runs of AS_SEQUENCEs into one segment
260 * Internally, we do not care about the wire segment length limit, and
261 * we want each distinct AS_PATHs to have the exact same internal
262 * representation - eg, so that our hashing actually works..
264 static struct assegment
*
265 assegment_normalise (struct assegment
*head
)
267 struct assegment
*seg
= head
, *pin
;
268 struct assegment
*tmp
;
277 /* Sort values SET segments, for determinism in paths to aid
278 * creation of hash values / path comparisons
279 * and because it helps other lesser implementations ;)
281 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
)
286 qsort (seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
289 for (i
=1; i
< seg
->length
; i
++)
291 if (seg
->as
[tail
] == seg
->as
[i
])
296 seg
->as
[tail
] = seg
->as
[i
];
298 /* seg->length can be 0.. */
300 seg
->length
= tail
+ 1;
303 /* read ahead from the current, pinned segment while the segments
304 * are packable/mergeable. Append all following packable segments
305 * to the segment we have pinned and remove these appended
308 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
))
313 /* append the next sequence to the pinned sequence */
314 pin
= assegment_append_asns (pin
, seg
->as
, seg
->length
);
316 /* bypass the next sequence */
317 pin
->next
= seg
->next
;
319 /* get rid of the now referenceless segment */
320 assegment_free (tmp
);
329 static struct aspath
*
332 return XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
335 /* Free AS path structure. */
337 aspath_free (struct aspath
*aspath
)
341 if (aspath
->segments
)
342 assegment_free_all (aspath
->segments
);
344 XFREE (MTYPE_AS_STR
, aspath
->str
);
348 json_object_free(aspath
->json
);
352 XFREE (MTYPE_AS_PATH
, aspath
);
355 /* Unintern aspath from AS path bucket. */
357 aspath_unintern (struct aspath
**aspath
)
360 struct aspath
*asp
= *aspath
;
365 if (asp
->refcnt
== 0)
367 /* This aspath must exist in aspath hash table. */
368 ret
= hash_release (ashash
, asp
);
369 assert (ret
!= NULL
);
375 /* Return the start or end delimiters for a particular Segment type */
376 #define AS_SEG_START 0
379 aspath_delimiter_char (u_char type
, u_char which
)
387 } aspath_delim_char
[] =
389 { AS_SET
, '{', '}' },
390 { AS_CONFED_SET
, '[', ']' },
391 { AS_CONFED_SEQUENCE
, '(', ')' },
395 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++)
397 if (aspath_delim_char
[i
].type
== type
)
399 if (which
== AS_SEG_START
)
400 return aspath_delim_char
[i
].start
;
401 else if (which
== AS_SEG_END
)
402 return aspath_delim_char
[i
].end
;
408 /* countup asns from this segment and index onward */
410 assegment_count_asns (struct assegment
*seg
, int from
)
416 count
+= seg
->length
;
419 count
+= (seg
->length
- from
);
428 aspath_count_confeds (struct aspath
*aspath
)
431 struct assegment
*seg
= aspath
->segments
;
435 if (seg
->type
== AS_CONFED_SEQUENCE
)
436 count
+= seg
->length
;
437 else if (seg
->type
== AS_CONFED_SET
)
446 aspath_count_hops (const struct aspath
*aspath
)
449 struct assegment
*seg
= aspath
->segments
;
453 if (seg
->type
== AS_SEQUENCE
)
454 count
+= seg
->length
;
455 else if (seg
->type
== AS_SET
)
463 /* Estimate size aspath /might/ take if encoded into an
466 * This is a quick estimate, not definitive! aspath_put()
467 * may return a different number!!
470 aspath_size (struct aspath
*aspath
)
473 struct assegment
*seg
= aspath
->segments
;
477 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
483 /* Return highest public ASN in path */
485 aspath_highest (struct aspath
*aspath
)
487 struct assegment
*seg
= aspath
->segments
;
493 for (i
= 0; i
< seg
->length
; i
++)
494 if (seg
->as
[i
] > highest
&& !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
495 highest
= seg
->as
[i
];
501 /* Return the left-most ASN in path */
503 aspath_leftmost (struct aspath
*aspath
)
505 struct assegment
*seg
= aspath
->segments
;
508 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
509 leftmost
= seg
->as
[0];
514 /* Return 1 if there are any 4-byte ASes in the path */
516 aspath_has_as4 (struct aspath
*aspath
)
518 struct assegment
*seg
= aspath
->segments
;
523 for (i
= 0; i
< seg
->length
; i
++)
524 if (seg
->as
[i
] > BGP_AS_MAX
)
531 /* Convert aspath structure to string expression. */
533 aspath_make_str_count (struct aspath
*as
)
535 struct assegment
*seg
;
539 json_object
*jaspath_segments
= NULL
;
540 json_object
*jseg
= NULL
;
541 json_object
*jseg_list
= NULL
;
543 as
->json
= json_object_new_object();
544 jaspath_segments
= json_object_new_array();
549 json_object_string_add(as
->json
, "string", "Local");
550 json_object_object_add(as
->json
, "segments", jaspath_segments
);
551 json_object_int_add(as
->json
, "length", 0);
552 as
->str
= XMALLOC (MTYPE_AS_STR
, 1);
560 /* ASN takes 5 to 10 chars plus seperator, see below.
561 * If there is one differing segment type, we need an additional
562 * 2 chars for segment delimiters, and the final '\0'.
563 * Hopefully this is large enough to avoid hitting the realloc
564 * code below for most common sequences.
566 * This was changed to 10 after the well-known BGP assertion, which
567 * had hit some parts of the Internet in May of 2009.
569 #define ASN_STR_LEN (10 + 1)
570 str_size
= MAX (assegment_count_asns (seg
, 0) * ASN_STR_LEN
+ 2 + 1,
571 ASPATH_STR_DEFAULT_LEN
);
572 str_buf
= XMALLOC (MTYPE_AS_STR
, str_size
);
579 /* Check AS type validity. Set seperator for segment */
587 case AS_CONFED_SEQUENCE
:
591 XFREE (MTYPE_AS_STR
, str_buf
);
594 json_object_free(as
->json
);
599 /* We might need to increase str_buf, particularly if path has
600 * differing segments types, our initial guesstimate above will
601 * have been wrong. Need 10 chars for ASN, a seperator each and
602 * potentially two segment delimiters, plus a space between each
603 * segment and trailing zero.
605 * This definitely didn't work with the value of 5 bytes and
608 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
609 if ( (len
+ SEGMENT_STR_LEN(seg
)) > str_size
)
611 str_size
= len
+ SEGMENT_STR_LEN(seg
);
612 str_buf
= XREALLOC (MTYPE_AS_STR
, str_buf
, str_size
);
615 #undef SEGMENT_STR_LEN
617 if (seg
->type
!= AS_SEQUENCE
)
618 len
+= snprintf (str_buf
+ len
, str_size
- len
,
620 aspath_delimiter_char (seg
->type
, AS_SEG_START
));
622 jseg_list
= json_object_new_array();
624 /* write out the ASNs, with their seperators, bar the last one*/
625 for (i
= 0; i
< seg
->length
; i
++)
627 json_object_array_add(jseg_list
, json_object_new_int(seg
->as
[i
]));
629 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%u", seg
->as
[i
]);
631 if (i
< (seg
->length
- 1))
632 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c", seperator
);
635 jseg
= json_object_new_object();
636 json_object_string_add(jseg
, "type", aspath_segment_type_str
[seg
->type
]);
637 json_object_object_add(jseg
, "list", jseg_list
);
638 json_object_array_add(jaspath_segments
, jseg
);
640 if (seg
->type
!= AS_SEQUENCE
)
641 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c",
642 aspath_delimiter_char (seg
->type
, AS_SEG_END
));
644 len
+= snprintf (str_buf
+ len
, str_size
- len
, " ");
649 assert (len
< str_size
);
655 json_object_string_add(as
->json
, "string", str_buf
);
656 json_object_object_add(as
->json
, "segments", jaspath_segments
);
657 json_object_int_add(as
->json
, "length", aspath_count_hops (as
));
662 aspath_str_update (struct aspath
*as
)
665 XFREE (MTYPE_AS_STR
, as
->str
);
669 json_object_free(as
->json
);
673 aspath_make_str_count (as
);
676 /* Intern allocated AS path. */
678 aspath_intern (struct aspath
*aspath
)
682 /* Assert this AS path structure is not interned and has the string
683 representation built. */
684 assert (aspath
->refcnt
== 0);
685 assert (aspath
->str
);
687 /* Check AS path hash. */
688 find
= hash_get (ashash
, aspath
, hash_alloc_intern
);
690 aspath_free (aspath
);
697 /* Duplicate aspath structure. Created same aspath structure but
698 reference count and AS path string is cleared. */
700 aspath_dup (struct aspath
*aspath
)
702 unsigned short buflen
= aspath
->str_len
+ 1;
705 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
708 if (aspath
->segments
)
709 new->segments
= assegment_dup_all (aspath
->segments
);
714 new->str
= XMALLOC (MTYPE_AS_STR
, buflen
);
715 new->str_len
= aspath
->str_len
;
717 /* copy the string data */
718 if (aspath
->str_len
> 0)
719 memcpy (new->str
, aspath
->str
, buflen
);
727 aspath_hash_alloc (void *arg
)
729 const struct aspath
*aspath
= arg
;
732 /* Malformed AS path value. */
733 assert (aspath
->str
);
735 /* New aspath structure is needed. */
736 new = XMALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
738 /* Reuse segments and string representation */
740 new->segments
= aspath
->segments
;
741 new->str
= aspath
->str
;
742 new->str_len
= aspath
->str_len
;
743 new->json
= aspath
->json
;
748 /* parse as-segment byte stream in struct assegment */
750 assegments_parse (struct stream
*s
, size_t length
,
751 struct assegment
**result
, int use32bit
)
753 struct assegment_header segh
;
754 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
757 /* empty aspath (ie iBGP or somesuch) */
761 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
762 zlog_debug ("[AS4SEG] Parse aspath segment: got total byte length %lu",
763 (unsigned long) length
);
765 if ((STREAM_READABLE(s
) < length
)
766 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
767 || (length
% AS16_VALUE_SIZE
))
770 while (bytes
< length
)
775 if ((length
- bytes
) <= AS_HEADER_SIZE
)
778 assegment_free_all (head
);
782 /* softly softly, get the header first on its own */
783 segh
.type
= stream_getc (s
);
784 segh
.length
= stream_getc (s
);
786 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
788 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
789 zlog_debug ("[AS4SEG] Parse aspath segment: got type %d, length %d",
790 segh
.type
, segh
.length
);
793 if ( ((bytes
+ seg_size
) > length
)
794 /* 1771bis 4.3b: seg length contains one or more */
795 || (segh
.length
== 0)
796 /* Paranoia in case someone changes type of segment length.
797 * Shift both values by 0x10 to make the comparison operate
798 * on more, than 8 bits (otherwise it's a warning, bug #564).
800 || ((sizeof segh
.length
> 1)
801 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
)))
804 assegment_free_all (head
);
812 case AS_CONFED_SEQUENCE
:
817 assegment_free_all (head
);
821 /* now its safe to trust lengths */
822 seg
= assegment_new (segh
.type
, segh
.length
);
826 else /* it's the first segment */
829 for (i
= 0; i
< segh
.length
; i
++)
830 seg
->as
[i
] = (use32bit
) ? stream_getl (s
) : stream_getw (s
);
834 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
835 zlog_debug ("[AS4SEG] Parse aspath segment: Bytes now: %lu",
836 (unsigned long) bytes
);
841 *result
= assegment_normalise (head
);
845 /* AS path parse function. pnt is a pointer to byte stream and length
846 is length of byte stream. If there is same AS path in the the AS
847 path hash then return it else make new AS path structure.
849 On error NULL is returned.
852 aspath_parse (struct stream
*s
, size_t length
, int use32bit
)
857 /* If length is odd it's malformed AS path. */
858 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
859 * otherwise its malformed when length is larger than 2 and (length-2)
860 * is not dividable by 4.
861 * But... this time we're lazy
863 if (length
% AS16_VALUE_SIZE
)
866 memset (&as
, 0, sizeof (struct aspath
));
867 if (assegments_parse (s
, length
, &as
.segments
, use32bit
) < 0)
870 /* If already same aspath exist then return it. */
871 find
= hash_get (ashash
, &as
, aspath_hash_alloc
);
873 /* bug! should not happen, let the daemon crash below */
876 /* if the aspath was already hashed free temporary memory. */
879 assegment_free_all (as
.segments
);
880 /* aspath_key_make() always updates the string */
881 XFREE (MTYPE_AS_STR
, as
.str
);
884 json_object_free(as
.json
);
895 assegment_data_put (struct stream
*s
, as_t
*as
, int num
, int use32bit
)
898 assert (num
<= AS_SEGMENT_MAX
);
900 for (i
= 0; i
< num
; i
++)
902 stream_putl (s
, as
[i
]);
905 if ( as
[i
] <= BGP_AS_MAX
)
906 stream_putw(s
, as
[i
]);
908 stream_putw(s
, BGP_AS_TRANS
);
913 assegment_header_put (struct stream
*s
, u_char type
, int length
)
916 assert (length
<= AS_SEGMENT_MAX
);
917 stream_putc (s
, type
);
918 lenp
= stream_get_endp (s
);
919 stream_putc (s
, length
);
923 /* write aspath data to stream */
925 aspath_put (struct stream
*s
, struct aspath
*as
, int use32bit
)
927 struct assegment
*seg
= as
->segments
;
930 if (!seg
|| seg
->length
== 0)
936 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
937 * At the moment, we would write out a partial aspath, and our peer
938 * will complain and drop the session :-/
940 * The general assumption here is that many things tested will
941 * never happen. And, in real live, up to now, they have not.
943 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
) <= STREAM_WRITEABLE(s
)))
945 struct assegment
*next
= seg
->next
;
950 /* Overlength segments have to be split up */
951 while ( (seg
->length
- written
) > AS_SEGMENT_MAX
)
953 assegment_header_put (s
, seg
->type
, AS_SEGMENT_MAX
);
954 assegment_data_put (s
, seg
->as
, AS_SEGMENT_MAX
, use32bit
);
955 written
+= AS_SEGMENT_MAX
;
956 bytes
+= ASSEGMENT_SIZE (written
, use32bit
);
959 /* write the final segment, probably is also the first */
960 lenp
= assegment_header_put (s
, seg
->type
, seg
->length
- written
);
961 assegment_data_put (s
, (seg
->as
+ written
), seg
->length
- written
,
964 /* Sequence-type segments can be 'packed' together
965 * Case of a segment which was overlength and split up
966 * will be missed here, but that doesn't matter.
968 while (next
&& ASSEGMENTS_PACKABLE (seg
, next
))
970 /* NB: We should never normally get here given we
971 * normalise aspath data when parse them. However, better
972 * safe than sorry. We potentially could call
973 * assegment_normalise here instead, but it's cheaper and
974 * easier to do it on the fly here rather than go through
975 * the segment list twice every time we write out
979 /* Next segment's data can fit in this one */
980 assegment_data_put (s
, next
->as
, next
->length
, use32bit
);
982 /* update the length of the segment header */
983 stream_putc_at (s
, lenp
, seg
->length
- written
+ next
->length
);
984 asns_packed
+= next
->length
;
989 bytes
+= ASSEGMENT_SIZE (seg
->length
- written
+ asns_packed
,
997 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
998 * We have no way to manage the storage, so we use a static stream
999 * wrapper around aspath_put.
1002 aspath_snmp_pathseg (struct aspath
*as
, size_t *varlen
)
1004 #define SNMP_PATHSEG_MAX 1024
1007 snmp_stream
= stream_new (SNMP_PATHSEG_MAX
);
1009 stream_reset (snmp_stream
);
1016 aspath_put (snmp_stream
, as
, 0); /* use 16 bit for now here */
1018 *varlen
= stream_get_endp (snmp_stream
);
1019 return stream_pnt(snmp_stream
);
1022 #define min(A,B) ((A) < (B) ? (A) : (B))
1024 static struct assegment
*
1025 aspath_aggregate_as_set_add (struct aspath
*aspath
, struct assegment
*asset
,
1030 /* If this is first AS set member, create new as-set segment. */
1033 asset
= assegment_new (AS_SET
, 1);
1034 if (! aspath
->segments
)
1035 aspath
->segments
= asset
;
1038 struct assegment
*seg
= aspath
->segments
;
1043 asset
->type
= AS_SET
;
1049 /* Check this AS value already exists or not. */
1050 for (i
= 0; i
< asset
->length
; i
++)
1051 if (asset
->as
[i
] == as
)
1055 asset
->as
= XREALLOC (MTYPE_AS_SEG_DATA
, asset
->as
,
1056 asset
->length
* AS_VALUE_SIZE
);
1057 asset
->as
[asset
->length
- 1] = as
;
1064 /* Modify as1 using as2 for aggregation. */
1066 aspath_aggregate (struct aspath
*as1
, struct aspath
*as2
)
1072 struct assegment
*seg1
= as1
->segments
;
1073 struct assegment
*seg2
= as2
->segments
;
1074 struct aspath
*aspath
= NULL
;
1075 struct assegment
*asset
= NULL
;
1076 struct assegment
*prevseg
= NULL
;
1078 /* First of all check common leading sequence. */
1079 while (seg1
&& seg2
)
1081 /* Check segment type. */
1082 if (seg1
->type
!= seg2
->type
)
1085 /* Minimum segment length. */
1086 minlen
= min (seg1
->length
, seg2
->length
);
1088 for (match
= 0; match
< minlen
; match
++)
1089 if (seg1
->as
[match
] != seg2
->as
[match
])
1094 struct assegment
*seg
= assegment_new (seg1
->type
, 0);
1096 seg
= assegment_append_asns (seg
, seg1
->as
, match
);
1100 aspath
= aspath_new ();
1101 aspath
->segments
= seg
;
1104 prevseg
->next
= seg
;
1109 if (match
!= minlen
|| match
!= seg1
->length
1110 || seg1
->length
!= seg2
->length
)
1112 /* We are moving on to the next segment to reset match */
1121 aspath
= aspath_new();
1123 /* Make as-set using rest of all information. */
1127 for (i
= from
; i
< seg1
->length
; i
++)
1128 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg1
->as
[i
]);
1137 for (i
= from
; i
< seg2
->length
; i
++)
1138 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg2
->as
[i
]);
1144 assegment_normalise (aspath
->segments
);
1145 aspath_str_update (aspath
);
1149 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1150 attribute, check the leftmost AS number in the AS_PATH attribute is
1151 or not the peer's AS number. */
1153 aspath_firstas_check (struct aspath
*aspath
, as_t asno
)
1155 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
1158 if (aspath
->segments
1159 && (aspath
->segments
->type
== AS_SEQUENCE
)
1160 && (aspath
->segments
->as
[0] == asno
))
1167 aspath_get_first_as (struct aspath
*aspath
)
1169 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1172 return aspath
->segments
->as
[0];
1176 aspath_get_last_as (struct aspath
*aspath
)
1179 unsigned int last_as
= 0;
1180 const struct assegment
*seg
;
1182 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1185 seg
= aspath
->segments
;
1189 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1190 for (i
= 0; i
< seg
->length
; i
++)
1191 last_as
= seg
->as
[i
];
1198 /* AS path loop check. If aspath contains asno then return >= 1. */
1200 aspath_loop_check (struct aspath
*aspath
, as_t asno
)
1202 struct assegment
*seg
;
1205 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
1208 seg
= aspath
->segments
;
1214 for (i
= 0; i
< seg
->length
; i
++)
1215 if (seg
->as
[i
] == asno
)
1223 /* When all of AS path is private AS return 1. */
1225 aspath_private_as_check (struct aspath
*aspath
)
1227 struct assegment
*seg
;
1229 if ( !(aspath
&& aspath
->segments
) )
1232 seg
= aspath
->segments
;
1238 for (i
= 0; i
< seg
->length
; i
++)
1240 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1248 /* Return True if the entire ASPATH consist of the specified ASN */
1250 aspath_single_asn_check (struct aspath
*aspath
, as_t asn
)
1252 struct assegment
*seg
;
1254 if ( !(aspath
&& aspath
->segments
) )
1257 seg
= aspath
->segments
;
1263 for (i
= 0; i
< seg
->length
; i
++)
1265 if (seg
->as
[i
] != asn
)
1273 /* Replace all instances of the target ASN with our own ASN */
1275 aspath_replace_specific_asn (struct aspath
*aspath
, as_t target_asn
,
1279 struct assegment
*seg
;
1281 new = aspath_dup(aspath
);
1282 seg
= new->segments
;
1288 for (i
= 0; i
< seg
->length
; i
++)
1290 if (seg
->as
[i
] == target_asn
)
1291 seg
->as
[i
] = our_asn
;
1296 aspath_str_update(new);
1300 /* Replace all private ASNs with our own ASN */
1302 aspath_replace_private_asns (struct aspath
*aspath
, as_t asn
)
1305 struct assegment
*seg
;
1307 new = aspath_dup(aspath
);
1308 seg
= new->segments
;
1314 for (i
= 0; i
< seg
->length
; i
++)
1316 if (BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1322 aspath_str_update(new);
1326 /* Remove all private ASNs */
1328 aspath_remove_private_asns (struct aspath
*aspath
)
1331 struct assegment
*seg
;
1332 struct assegment
*new_seg
;
1333 struct assegment
*last_new_seg
;
1338 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
1342 last_new_seg
= NULL
;
1343 seg
= aspath
->segments
;
1347 for (i
= 0; i
< seg
->length
; i
++)
1350 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1356 // The entire segment is private so skip it
1363 // The entire segment is public so copy it
1364 else if (public == seg
->length
)
1366 new_seg
= assegment_dup (seg
);
1369 // The segment is a mix of public and private ASNs. Copy as many spots as
1370 // there are public ASNs then come back and fill in only the public ASNs.
1373 new_seg
= assegment_new (seg
->type
, public);
1375 for (i
= 0; i
< seg
->length
; i
++)
1378 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1380 new_seg
->as
[j
] = seg
->as
[i
];
1386 // This is the first segment so set the aspath segments pointer to this one
1388 new->segments
= new_seg
;
1390 last_new_seg
->next
= new_seg
;
1392 last_new_seg
= new_seg
;
1396 aspath_str_update(new);
1400 /* AS path confed check. If aspath contains confed set or sequence then return 1. */
1402 aspath_confed_check (struct aspath
*aspath
)
1404 struct assegment
*seg
;
1406 if ( !(aspath
&& aspath
->segments
) )
1409 seg
= aspath
->segments
;
1413 if (seg
->type
== AS_CONFED_SET
|| seg
->type
== AS_CONFED_SEQUENCE
)
1420 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1421 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1423 aspath_left_confed_check (struct aspath
*aspath
)
1426 if ( !(aspath
&& aspath
->segments
) )
1429 if ( (aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1430 || (aspath
->segments
->type
== AS_CONFED_SET
) )
1436 /* Merge as1 to as2. as2 should be uninterned aspath. */
1437 static struct aspath
*
1438 aspath_merge (struct aspath
*as1
, struct aspath
*as2
)
1440 struct assegment
*last
, *new;
1445 last
= new = assegment_dup_all (as1
->segments
);
1447 /* find the last valid segment */
1448 while (last
&& last
->next
)
1451 last
->next
= as2
->segments
;
1452 as2
->segments
= new;
1453 aspath_str_update (as2
);
1457 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1459 aspath_prepend (struct aspath
*as1
, struct aspath
*as2
)
1461 struct assegment
*seg1
;
1462 struct assegment
*seg2
;
1467 seg1
= as1
->segments
;
1468 seg2
= as2
->segments
;
1470 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1473 as2
->segments
= assegment_dup_all (as1
->segments
);
1474 aspath_str_update (as2
);
1478 /* If as1 is empty AS, no prepending to do. */
1482 /* find the tail as1's segment chain. */
1483 while (seg1
&& seg1
->next
)
1486 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1487 if (seg1
->type
== AS_SEQUENCE
&& seg2
->type
== AS_CONFED_SEQUENCE
)
1488 as2
= aspath_delete_confed_seq (as2
);
1490 /* Compare last segment type of as1 and first segment type of as2. */
1491 if (seg1
->type
!= seg2
->type
)
1492 return aspath_merge (as1
, as2
);
1494 if (seg1
->type
== AS_SEQUENCE
)
1496 /* We have two chains of segments, as1->segments and seg2,
1497 * and we have to attach them together, merging the attaching
1498 * segments together into one.
1500 * 1. dupe as1->segments onto head of as2
1501 * 2. merge seg2's asns onto last segment of this new chain
1502 * 3. attach chain after seg2
1505 /* dupe as1 onto as2's head */
1506 seg1
= as2
->segments
= assegment_dup_all (as1
->segments
);
1508 /* refind the tail of as2, reusing seg1 */
1509 while (seg1
&& seg1
->next
)
1512 /* merge the old head, seg2, into tail, seg1 */
1513 seg1
= assegment_append_asns (seg1
, seg2
->as
, seg2
->length
);
1515 /* bypass the merged seg2, and attach any chain after it to
1516 * chain descending from as2's head
1518 seg1
->next
= seg2
->next
;
1520 /* seg2 is now referenceless and useless*/
1521 assegment_free (seg2
);
1523 /* we've now prepended as1's segment chain to as2, merging
1524 * the inbetween AS_SEQUENCE of seg2 in the process
1526 aspath_str_update (as2
);
1531 /* AS_SET merge code is needed at here. */
1532 return aspath_merge (as1
, as2
);
1534 /* XXX: Ermmm, what if as1 has multiple segments?? */
1539 /* Iterate over AS_PATH segments and wipe all occurences of the
1540 * listed AS numbers. Hence some segments may lose some or even
1541 * all data on the way, the operation is implemented as a smarter
1542 * version of aspath_dup(), which allocates memory to hold the new
1543 * data, not the original. The new AS path is returned.
1546 aspath_filter_exclude (struct aspath
* source
, struct aspath
* exclude_list
)
1548 struct assegment
* srcseg
, * exclseg
, * lastseg
;
1549 struct aspath
* newpath
;
1551 newpath
= aspath_new();
1554 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
)
1556 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1557 struct assegment
* newseg
;
1559 /* Find out, how much ASns are we going to pick from this segment.
1560 * We can't perform filtering right inline, because the size of
1561 * the new segment isn't known at the moment yet.
1563 for (i
= 0; i
< srcseg
->length
; i
++)
1566 for (exclseg
= exclude_list
->segments
; exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1567 for (y
= 0; y
< exclseg
->length
; y
++)
1568 if (srcseg
->as
[i
] == exclseg
->as
[y
])
1571 // There's no sense in testing the rest of exclusion list, bail out.
1577 /* newlen is now the number of ASns to copy */
1581 /* Actual copying. Allocate memory and iterate once more, performing filtering. */
1582 newseg
= assegment_new (srcseg
->type
, newlen
);
1583 for (i
= 0; i
< srcseg
->length
; i
++)
1586 for (exclseg
= exclude_list
->segments
; exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1587 for (y
= 0; y
< exclseg
->length
; y
++)
1588 if (srcseg
->as
[i
] == exclseg
->as
[y
])
1595 newseg
->as
[done
++] = srcseg
->as
[i
];
1597 /* At his point newlen must be equal to done, and both must be positive. Append
1598 * the filtered segment to the gross result. */
1600 newpath
->segments
= newseg
;
1602 lastseg
->next
= newseg
;
1605 aspath_str_update (newpath
);
1606 /* We are happy returning even an empty AS_PATH, because the administrator
1607 * might expect this very behaviour. There's a mean to avoid this, if necessary,
1608 * by having a match rule against certain AS_PATH regexps in the route-map index.
1610 aspath_free (source
);
1614 /* Add specified AS to the leftmost of aspath. */
1615 static struct aspath
*
1616 aspath_add_asns (struct aspath
*aspath
, as_t asno
, u_char type
, unsigned num
)
1618 struct assegment
*assegment
= aspath
->segments
;
1621 if (assegment
&& assegment
->type
== type
)
1623 /* extend existing segment */
1624 aspath
->segments
= assegment_prepend_asns (aspath
->segments
, asno
, num
);
1628 /* prepend with new segment */
1629 struct assegment
*newsegment
= assegment_new (type
, num
);
1630 for (i
= 0; i
< num
; i
++)
1631 newsegment
->as
[i
] = asno
;
1633 /* insert potentially replacing empty segment */
1634 if (assegment
&& assegment
->length
== 0)
1636 newsegment
->next
= assegment
->next
;
1637 assegment_free (assegment
);
1640 newsegment
->next
= assegment
;
1641 aspath
->segments
= newsegment
;
1644 aspath_str_update (aspath
);
1648 /* Add specified AS to the leftmost of aspath num times. */
1650 aspath_add_seq_n (struct aspath
*aspath
, as_t asno
, unsigned num
)
1652 return aspath_add_asns (aspath
, asno
, AS_SEQUENCE
, num
);
1655 /* Add specified AS to the leftmost of aspath. */
1657 aspath_add_seq (struct aspath
*aspath
, as_t asno
)
1659 return aspath_add_asns (aspath
, asno
, AS_SEQUENCE
, 1);
1662 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1663 as2's leftmost AS is same return 1. */
1665 aspath_cmp_left (const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1667 const struct assegment
*seg1
;
1668 const struct assegment
*seg2
;
1670 if (!(aspath1
&& aspath2
))
1673 seg1
= aspath1
->segments
;
1674 seg2
= aspath2
->segments
;
1676 /* If both paths are originated in this AS then we do want to compare MED */
1680 /* find first non-confed segments for each */
1681 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1682 || (seg1
->type
== AS_CONFED_SET
)))
1685 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1686 || (seg2
->type
== AS_CONFED_SET
)))
1691 && (seg1
->type
== AS_SEQUENCE
) && (seg2
->type
== AS_SEQUENCE
)))
1694 if (seg1
->as
[0] == seg2
->as
[0])
1700 /* Truncate an aspath after a number of hops, and put the hops remaining
1701 * at the front of another aspath. Needed for AS4 compat.
1703 * Returned aspath is a /new/ aspath, which should either by free'd or
1704 * interned by the caller, as desired.
1707 aspath_reconcile_as4 ( struct aspath
*aspath
, struct aspath
*as4path
)
1709 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1710 struct aspath
*newpath
= NULL
, *mergedpath
;
1711 int hops
, cpasns
= 0;
1716 seg
= aspath
->segments
;
1718 /* CONFEDs should get reconciled too.. */
1719 hops
= (aspath_count_hops (aspath
) + aspath_count_confeds (aspath
))
1720 - aspath_count_hops (as4path
);
1724 if (BGP_DEBUG (as4
, AS4
))
1725 zlog_warn ("[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1726 /* Something's gone wrong. The RFC says we should now ignore AS4_PATH,
1727 * which is daft behaviour - it contains vital loop-detection
1728 * information which must have been removed from AS_PATH.
1730 hops
= aspath_count_hops (aspath
);
1735 newpath
= aspath_dup (as4path
);
1736 aspath_str_update(newpath
);
1740 if ( BGP_DEBUG(as4
, AS4
))
1741 zlog_debug("[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1742 aspath
->str
, as4path
->str
);
1744 while (seg
&& hops
> 0)
1751 cpasns
= seg
->length
;
1753 case AS_CONFED_SEQUENCE
:
1754 /* Should never split a confed-sequence, if hop-count
1755 * suggests we must then something's gone wrong somewhere.
1757 * Most important goal is to preserve AS_PATHs prime function
1758 * as loop-detector, so we fudge the numbers so that the entire
1759 * confed-sequence is merged in.
1761 if (hops
< seg
->length
)
1763 if (BGP_DEBUG (as4
, AS4
))
1764 zlog_debug ("[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1765 " across 2/4 ASN boundary somewhere, broken..");
1769 cpasns
= MIN(seg
->length
, hops
);
1770 hops
-= seg
->length
;
1773 assert (cpasns
<= seg
->length
);
1775 newseg
= assegment_new (seg
->type
, 0);
1776 newseg
= assegment_append_asns (newseg
, seg
->as
, cpasns
);
1780 newpath
= aspath_new ();
1781 newpath
->segments
= newseg
;
1784 prevseg
->next
= newseg
;
1790 /* We may be able to join some segments here, and we must
1791 * do this because... we want normalised aspaths in out hash
1792 * and we do not want to stumble in aspath_put.
1794 mergedpath
= aspath_merge (newpath
, aspath_dup(as4path
));
1795 aspath_free (newpath
);
1796 mergedpath
->segments
= assegment_normalise (mergedpath
->segments
);
1797 aspath_str_update (mergedpath
);
1799 if ( BGP_DEBUG(as4
, AS4
))
1800 zlog_debug ("[AS4] result of synthesizing is %s",
1806 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1807 as2's leftmost AS is same return 1. (confederation as-path
1810 aspath_cmp_left_confed (const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1812 if (! (aspath1
&& aspath2
) )
1815 if ( !(aspath1
->segments
&& aspath2
->segments
) )
1818 if ( (aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1819 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
) )
1822 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1828 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1829 * RFC 5065 section 4.1.c.1
1831 * 1) if any path segments of the AS_PATH are of the type
1832 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1833 * removed from the AS_PATH attribute, leaving the sanitized
1834 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1837 aspath_delete_confed_seq (struct aspath
*aspath
)
1839 struct assegment
*seg
, *prev
, *next
;
1840 char removed_confed_segment
;
1842 if (!(aspath
&& aspath
->segments
))
1845 seg
= aspath
->segments
;
1846 removed_confed_segment
= 0;
1854 if (seg
->type
== AS_CONFED_SEQUENCE
|| seg
->type
== AS_CONFED_SET
)
1856 /* This is the first segment in the aspath */
1857 if (aspath
->segments
== seg
)
1858 aspath
->segments
= seg
->next
;
1860 prev
->next
= seg
->next
;
1862 assegment_free (seg
);
1863 removed_confed_segment
= 1;
1871 if (removed_confed_segment
)
1872 aspath_str_update (aspath
);
1877 /* Add new AS number to the leftmost part of the aspath as
1878 AS_CONFED_SEQUENCE. */
1880 aspath_add_confed_seq (struct aspath
*aspath
, as_t asno
)
1882 return aspath_add_asns (aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1885 /* Add new as value to as path structure. */
1887 aspath_as_add (struct aspath
*as
, as_t asno
)
1889 struct assegment
*seg
= as
->segments
;
1894 /* Last segment search procedure. */
1898 assegment_append_asns (seg
, &asno
, 1);
1901 /* Add new as segment to the as path. */
1903 aspath_segment_add (struct aspath
*as
, int type
)
1905 struct assegment
*seg
= as
->segments
;
1906 struct assegment
*new = assegment_new (type
, 0);
1921 return aspath_parse (NULL
, 0, 1); /* 32Bit ;-) */
1925 aspath_empty_get (void)
1927 struct aspath
*aspath
;
1929 aspath
= aspath_new ();
1930 aspath_make_str_count (aspath
);
1937 return ashash
->count
;
1941 Theoretically, one as path can have:
1943 One BGP packet size should be less than 4096.
1944 One BGP attribute size should be less than 4096 - BGP header size.
1945 One BGP aspath size should be less than 4096 - BGP header size -
1946 BGP mandantry attribute size.
1949 /* AS path string lexical token enum. */
1955 as_token_confed_seq_start
,
1956 as_token_confed_seq_end
,
1957 as_token_confed_set_start
,
1958 as_token_confed_set_end
,
1962 /* Return next token and point for string parse. */
1964 aspath_gettoken (const char *buf
, enum as_token
*token
, u_long
*asno
)
1966 const char *p
= buf
;
1968 /* Skip seperators (space for sequences, ',' for sets). */
1969 while (isspace ((int) *p
) || *p
== ',')
1972 /* Check the end of the string and type specify characters
1979 *token
= as_token_set_start
;
1983 *token
= as_token_set_end
;
1987 *token
= as_token_confed_seq_start
;
1991 *token
= as_token_confed_seq_end
;
1995 *token
= as_token_confed_set_start
;
1999 *token
= as_token_confed_set_end
;
2004 /* Check actual AS value. */
2005 if (isdigit ((int) *p
))
2009 *token
= as_token_asval
;
2013 while (isdigit ((int) *p
))
2016 asval
+= (*p
- '0');
2023 /* There is no match then return unknown token. */
2024 *token
= as_token_unknown
;
2029 aspath_str2aspath (const char *str
)
2031 enum as_token token
= as_token_unknown
;
2034 struct aspath
*aspath
;
2037 aspath
= aspath_new ();
2039 /* We start default type as AS_SEQUENCE. */
2040 as_type
= AS_SEQUENCE
;
2043 while ((str
= aspath_gettoken (str
, &token
, &asno
)) != NULL
)
2047 case as_token_asval
:
2050 aspath_segment_add (aspath
, as_type
);
2053 aspath_as_add (aspath
, asno
);
2055 case as_token_set_start
:
2057 aspath_segment_add (aspath
, as_type
);
2060 case as_token_set_end
:
2061 as_type
= AS_SEQUENCE
;
2064 case as_token_confed_seq_start
:
2065 as_type
= AS_CONFED_SEQUENCE
;
2066 aspath_segment_add (aspath
, as_type
);
2069 case as_token_confed_seq_end
:
2070 as_type
= AS_SEQUENCE
;
2073 case as_token_confed_set_start
:
2074 as_type
= AS_CONFED_SET
;
2075 aspath_segment_add (aspath
, as_type
);
2078 case as_token_confed_set_end
:
2079 as_type
= AS_SEQUENCE
;
2082 case as_token_unknown
:
2084 aspath_free (aspath
);
2089 aspath_make_str_count (aspath
);
2094 /* Make hash value by raw aspath data. */
2096 aspath_key_make (void *p
)
2098 struct aspath
*aspath
= (struct aspath
*) p
;
2099 unsigned int key
= 0;
2102 aspath_str_update (aspath
);
2104 key
= jhash (aspath
->str
, aspath
->str_len
, 2334325);
2109 /* If two aspath have same value then return 1 else return 0 */
2111 aspath_cmp (const void *arg1
, const void *arg2
)
2113 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2114 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2116 while (seg1
|| seg2
)
2119 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2121 if (seg1
->type
!= seg2
->type
)
2123 if (seg1
->length
!= seg2
->length
)
2125 for (i
= 0; i
< seg1
->length
; i
++)
2126 if (seg1
->as
[i
] != seg2
->as
[i
])
2134 /* AS path hash initialize. */
2138 ashash
= hash_create_size (32768, aspath_key_make
, aspath_cmp
);
2142 aspath_finish (void)
2144 hash_clean (ashash
, (void (*)(void *))aspath_free
);
2149 stream_free (snmp_stream
);
2152 /* return and as path value */
2154 aspath_print (struct aspath
*as
)
2156 return (as
? as
->str
: NULL
);
2159 /* Printing functions */
2160 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
2161 * AS_PATH wasn't empty.
2164 aspath_print_vty (struct vty
*vty
, const char *format
, struct aspath
*as
, const char * suffix
)
2167 vty_out (vty
, format
, as
->str
);
2168 if (as
->str_len
&& strlen (suffix
))
2169 vty_out (vty
, "%s", suffix
);
2173 aspath_show_all_iterator (struct hash_backet
*backet
, struct vty
*vty
)
2177 as
= (struct aspath
*) backet
->data
;
2179 vty_out (vty
, "[%p:%u] (%ld) ", (void *)backet
, backet
->key
, as
->refcnt
);
2180 vty_out (vty
, "%s%s", as
->str
, VTY_NEWLINE
);
2183 /* Print all aspath and hash information. This function is used from
2184 `show ip bgp paths' command. */
2186 aspath_print_all_vty (struct vty
*vty
)
2188 hash_iterate (ashash
,
2189 (void (*) (struct hash_backet
*, void *))
2190 aspath_show_all_iterator
,