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
34 #include "bgpd/bgpd.h"
35 #include "bgpd/bgp_aspath.h"
36 #include "bgpd/bgp_debug.h"
37 #include "bgpd/bgp_attr.h"
39 /* Attr. Flags and Attr. Type Code. */
40 #define AS_HEADER_SIZE 2
42 /* Now FOUR octets are used for AS value. */
43 #define AS_VALUE_SIZE sizeof (as_t)
44 /* This is the old one */
45 #define AS16_VALUE_SIZE sizeof (as16_t)
47 /* Maximum protocol segment length value */
48 #define AS_SEGMENT_MAX 255
50 /* The following length and size macros relate specifically to Quagga's
51 * internal representation of AS-Segments, not per se to the on-wire
52 * sizes and lengths. At present (200508) they sort of match, however
53 * the ONLY functions which should now about the on-wire syntax are
54 * aspath_put, assegment_put and assegment_parse.
56 * aspath_put returns bytes written, the only definitive record of
57 * size of wire-format attribute..
60 /* Calculated size in bytes of ASN segment data to hold N ASN's */
61 #define ASSEGMENT_DATA_SIZE(N,S) \
62 ((N) * ( (S) ? AS_VALUE_SIZE : AS16_VALUE_SIZE) )
64 /* Calculated size of segment struct to hold N ASN's */
65 #define ASSEGMENT_SIZE(N,S) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N,S))
67 /* AS segment octet length. */
68 #define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S)
70 /* AS_SEQUENCE segments can be packed together */
71 /* Can the types of X and Y be considered for packing? */
72 #define ASSEGMENT_TYPES_PACKABLE(X,Y) \
73 ( ((X)->type == (Y)->type) \
74 && ((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
89 /* Hash for aspath. This is the top level structure of AS path. */
90 static struct hash
*ashash
;
92 /* Stream for SNMP. See aspath_snmp_pathseg */
93 static struct stream
*snmp_stream
;
95 /* Callers are required to initialize the memory */
97 assegment_data_new (int num
)
99 return (XMALLOC (MTYPE_AS_SEG_DATA
, ASSEGMENT_DATA_SIZE (num
, 1)));
103 assegment_data_free (as_t
*asdata
)
105 XFREE (MTYPE_AS_SEG_DATA
, asdata
);
108 const char *aspath_segment_type_str
[] = {
112 "as-confed-sequence",
116 /* Get a new segment. Note that 0 is an allowed length,
117 * and will result in a segment with no allocated data segment.
118 * the caller should immediately assign data to the segment, as the segment
119 * otherwise is not generally valid
121 static struct assegment
*
122 assegment_new (u_char type
, u_short length
)
124 struct assegment
*new;
126 new = XCALLOC (MTYPE_AS_SEG
, sizeof (struct assegment
));
129 new->as
= assegment_data_new (length
);
131 new->length
= length
;
138 assegment_free (struct assegment
*seg
)
144 assegment_data_free (seg
->as
);
145 memset (seg
, 0xfe, sizeof(struct assegment
));
146 XFREE (MTYPE_AS_SEG
, seg
);
151 /* free entire chain of segments */
153 assegment_free_all (struct assegment
*seg
)
155 struct assegment
*prev
;
161 assegment_free (prev
);
165 /* Duplicate just the given assegment and its data */
166 static struct assegment
*
167 assegment_dup (struct assegment
*seg
)
169 struct assegment
*new;
171 new = assegment_new (seg
->type
, seg
->length
);
172 memcpy (new->as
, seg
->as
, ASSEGMENT_DATA_SIZE (new->length
, 1) );
177 /* Duplicate entire chain of assegments, return the head */
178 static struct assegment
*
179 assegment_dup_all (struct assegment
*seg
)
181 struct assegment
*new = NULL
;
182 struct assegment
*head
= NULL
;
188 new->next
= assegment_dup (seg
);
192 head
= new = assegment_dup (seg
);
199 /* prepend the as number to given segment, given num of times */
200 static struct assegment
*
201 assegment_prepend_asns (struct assegment
*seg
, as_t asnum
, int num
)
209 if (num
>= AS_SEGMENT_MAX
)
210 return seg
; /* we don't do huge prepends */
212 if ((newas
= assegment_data_new (seg
->length
+ num
)) == NULL
)
215 for (i
= 0; i
< num
; i
++)
218 memcpy (newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE (seg
->length
, 1));
219 assegment_data_free (seg
->as
);
226 /* append given array of as numbers to the segment */
227 static struct assegment
*
228 assegment_append_asns (struct assegment
*seg
, as_t
*asnos
, int num
)
232 newas
= XREALLOC (MTYPE_AS_SEG_DATA
, seg
->as
,
233 ASSEGMENT_DATA_SIZE (seg
->length
+ num
, 1));
238 memcpy (seg
->as
+ seg
->length
, asnos
, ASSEGMENT_DATA_SIZE(num
, 1));
243 assegment_free_all (seg
);
248 int_cmp (const void *p1
, const void *p2
)
250 const as_t
*as1
= p1
;
251 const as_t
*as2
= p2
;
253 return (*as1
== *as2
)
254 ? 0 : ( (*as1
> *as2
) ? 1 : -1);
257 /* normalise the segment.
258 * In particular, merge runs of AS_SEQUENCEs into one segment
259 * Internally, we do not care about the wire segment length limit, and
260 * we want each distinct AS_PATHs to have the exact same internal
261 * representation - eg, so that our hashing actually works..
263 static struct assegment
*
264 assegment_normalise (struct assegment
*head
)
266 struct assegment
*seg
= head
, *pin
;
267 struct assegment
*tmp
;
276 /* Sort values SET segments, for determinism in paths to aid
277 * creation of hash values / path comparisons
278 * and because it helps other lesser implementations ;)
280 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
)
285 qsort (seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
288 for (i
=1; i
< seg
->length
; i
++)
290 if (seg
->as
[tail
] == seg
->as
[i
])
295 seg
->as
[tail
] = seg
->as
[i
];
297 /* seg->length can be 0.. */
299 seg
->length
= tail
+ 1;
302 /* read ahead from the current, pinned segment while the segments
303 * are packable/mergeable. Append all following packable segments
304 * to the segment we have pinned and remove these appended
307 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
))
312 /* append the next sequence to the pinned sequence */
313 pin
= assegment_append_asns (pin
, seg
->as
, seg
->length
);
315 /* bypass the next sequence */
316 pin
->next
= seg
->next
;
318 /* get rid of the now referenceless segment */
319 assegment_free (tmp
);
328 static struct aspath
*
331 return XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
334 /* Free AS path structure. */
336 aspath_free (struct aspath
*aspath
)
340 if (aspath
->segments
)
341 assegment_free_all (aspath
->segments
);
343 XFREE (MTYPE_AS_STR
, aspath
->str
);
347 json_object_free(aspath
->json
);
351 XFREE (MTYPE_AS_PATH
, aspath
);
354 /* Unintern aspath from AS path bucket. */
356 aspath_unintern (struct aspath
**aspath
)
359 struct aspath
*asp
= *aspath
;
364 if (asp
->refcnt
== 0)
366 /* This aspath must exist in aspath hash table. */
367 ret
= hash_release (ashash
, asp
);
368 assert (ret
!= NULL
);
374 /* Return the start or end delimiters for a particular Segment type */
375 #define AS_SEG_START 0
378 aspath_delimiter_char (u_char type
, u_char which
)
386 } aspath_delim_char
[] =
388 { AS_SET
, '{', '}' },
389 { AS_CONFED_SET
, '[', ']' },
390 { AS_CONFED_SEQUENCE
, '(', ')' },
394 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++)
396 if (aspath_delim_char
[i
].type
== type
)
398 if (which
== AS_SEG_START
)
399 return aspath_delim_char
[i
].start
;
400 else if (which
== AS_SEG_END
)
401 return aspath_delim_char
[i
].end
;
407 /* countup asns from this segment and index onward */
409 assegment_count_asns (struct assegment
*seg
, int from
)
415 count
+= seg
->length
;
418 count
+= (seg
->length
- from
);
427 aspath_count_confeds (struct aspath
*aspath
)
430 struct assegment
*seg
= aspath
->segments
;
434 if (seg
->type
== AS_CONFED_SEQUENCE
)
435 count
+= seg
->length
;
436 else if (seg
->type
== AS_CONFED_SET
)
445 aspath_count_hops (const struct aspath
*aspath
)
448 struct assegment
*seg
= aspath
->segments
;
452 if (seg
->type
== AS_SEQUENCE
)
453 count
+= seg
->length
;
454 else if (seg
->type
== AS_SET
)
462 /* Estimate size aspath /might/ take if encoded into an
465 * This is a quick estimate, not definitive! aspath_put()
466 * may return a different number!!
469 aspath_size (struct aspath
*aspath
)
472 struct assegment
*seg
= aspath
->segments
;
476 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
482 /* Return highest public ASN in path */
484 aspath_highest (struct aspath
*aspath
)
486 struct assegment
*seg
= aspath
->segments
;
492 for (i
= 0; i
< seg
->length
; i
++)
493 if (seg
->as
[i
] > highest
&& !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
494 highest
= seg
->as
[i
];
500 /* Return the left-most ASN in path */
502 aspath_leftmost (struct aspath
*aspath
)
504 struct assegment
*seg
= aspath
->segments
;
507 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
508 leftmost
= seg
->as
[0];
513 /* Return 1 if there are any 4-byte ASes in the path */
515 aspath_has_as4 (struct aspath
*aspath
)
517 struct assegment
*seg
= aspath
->segments
;
522 for (i
= 0; i
< seg
->length
; i
++)
523 if (seg
->as
[i
] > BGP_AS_MAX
)
530 /* Convert aspath structure to string expression. */
532 aspath_make_str_count (struct aspath
*as
)
534 struct assegment
*seg
;
538 json_object
*jaspath_segments
= NULL
;
539 json_object
*jseg
= NULL
;
540 json_object
*jseg_list
= NULL
;
542 as
->json
= json_object_new_object();
543 jaspath_segments
= json_object_new_array();
548 json_object_string_add(as
->json
, "string", "Local");
549 json_object_object_add(as
->json
, "segments", jaspath_segments
);
550 json_object_int_add(as
->json
, "length", 0);
551 as
->str
= XMALLOC (MTYPE_AS_STR
, 1);
559 /* ASN takes 5 to 10 chars plus seperator, see below.
560 * If there is one differing segment type, we need an additional
561 * 2 chars for segment delimiters, and the final '\0'.
562 * Hopefully this is large enough to avoid hitting the realloc
563 * code below for most common sequences.
565 * This was changed to 10 after the well-known BGP assertion, which
566 * had hit some parts of the Internet in May of 2009.
568 #define ASN_STR_LEN (10 + 1)
569 str_size
= MAX (assegment_count_asns (seg
, 0) * ASN_STR_LEN
+ 2 + 1,
570 ASPATH_STR_DEFAULT_LEN
);
571 str_buf
= XMALLOC (MTYPE_AS_STR
, str_size
);
578 /* Check AS type validity. Set seperator for segment */
586 case AS_CONFED_SEQUENCE
:
590 XFREE (MTYPE_AS_STR
, str_buf
);
593 json_object_free(as
->json
);
598 /* We might need to increase str_buf, particularly if path has
599 * differing segments types, our initial guesstimate above will
600 * have been wrong. Need 10 chars for ASN, a seperator each and
601 * potentially two segment delimiters, plus a space between each
602 * segment and trailing zero.
604 * This definitely didn't work with the value of 5 bytes and
607 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
608 if ( (len
+ SEGMENT_STR_LEN(seg
)) > str_size
)
610 str_size
= len
+ SEGMENT_STR_LEN(seg
);
611 str_buf
= XREALLOC (MTYPE_AS_STR
, str_buf
, str_size
);
614 #undef SEGMENT_STR_LEN
616 if (seg
->type
!= AS_SEQUENCE
)
617 len
+= snprintf (str_buf
+ len
, str_size
- len
,
619 aspath_delimiter_char (seg
->type
, AS_SEG_START
));
621 jseg_list
= json_object_new_array();
623 /* write out the ASNs, with their seperators, bar the last one*/
624 for (i
= 0; i
< seg
->length
; i
++)
626 json_object_array_add(jseg_list
, json_object_new_int(seg
->as
[i
]));
628 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%u", seg
->as
[i
]);
630 if (i
< (seg
->length
- 1))
631 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c", seperator
);
634 jseg
= json_object_new_object();
635 json_object_string_add(jseg
, "type", aspath_segment_type_str
[seg
->type
]);
636 json_object_object_add(jseg
, "list", jseg_list
);
637 json_object_array_add(jaspath_segments
, jseg
);
639 if (seg
->type
!= AS_SEQUENCE
)
640 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c",
641 aspath_delimiter_char (seg
->type
, AS_SEG_END
));
643 len
+= snprintf (str_buf
+ len
, str_size
- len
, " ");
648 assert (len
< str_size
);
654 json_object_string_add(as
->json
, "string", str_buf
);
655 json_object_object_add(as
->json
, "segments", jaspath_segments
);
656 json_object_int_add(as
->json
, "length", aspath_count_hops (as
));
661 aspath_str_update (struct aspath
*as
)
664 XFREE (MTYPE_AS_STR
, as
->str
);
668 json_object_free(as
->json
);
672 aspath_make_str_count (as
);
675 /* Intern allocated AS path. */
677 aspath_intern (struct aspath
*aspath
)
681 /* Assert this AS path structure is not interned and has the string
682 representation built. */
683 assert (aspath
->refcnt
== 0);
684 assert (aspath
->str
);
686 /* Check AS path hash. */
687 find
= hash_get (ashash
, aspath
, hash_alloc_intern
);
689 aspath_free (aspath
);
696 /* Duplicate aspath structure. Created same aspath structure but
697 reference count and AS path string is cleared. */
699 aspath_dup (struct aspath
*aspath
)
701 unsigned short buflen
= aspath
->str_len
+ 1;
704 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
707 if (aspath
->segments
)
708 new->segments
= assegment_dup_all (aspath
->segments
);
713 new->str
= XMALLOC (MTYPE_AS_STR
, buflen
);
714 new->str_len
= aspath
->str_len
;
716 /* copy the string data */
717 if (aspath
->str_len
> 0)
718 memcpy (new->str
, aspath
->str
, buflen
);
726 aspath_hash_alloc (void *arg
)
728 const struct aspath
*aspath
= arg
;
731 /* Malformed AS path value. */
732 assert (aspath
->str
);
734 /* New aspath structure is needed. */
735 new = XMALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
737 /* Reuse segments and string representation */
739 new->segments
= aspath
->segments
;
740 new->str
= aspath
->str
;
741 new->str_len
= aspath
->str_len
;
742 new->json
= aspath
->json
;
747 /* parse as-segment byte stream in struct assegment */
749 assegments_parse (struct stream
*s
, size_t length
,
750 struct assegment
**result
, int use32bit
)
752 struct assegment_header segh
;
753 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
756 /* empty aspath (ie iBGP or somesuch) */
760 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
761 zlog_debug ("[AS4SEG] Parse aspath segment: got total byte length %lu",
762 (unsigned long) length
);
764 if ((STREAM_READABLE(s
) < length
)
765 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
766 || (length
% AS16_VALUE_SIZE
))
769 while (bytes
< length
)
774 if ((length
- bytes
) <= AS_HEADER_SIZE
)
777 assegment_free_all (head
);
781 /* softly softly, get the header first on its own */
782 segh
.type
= stream_getc (s
);
783 segh
.length
= stream_getc (s
);
785 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
787 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
788 zlog_debug ("[AS4SEG] Parse aspath segment: got type %d, length %d",
789 segh
.type
, segh
.length
);
792 if ( ((bytes
+ seg_size
) > length
)
793 /* 1771bis 4.3b: seg length contains one or more */
794 || (segh
.length
== 0)
795 /* Paranoia in case someone changes type of segment length.
796 * Shift both values by 0x10 to make the comparison operate
797 * on more, than 8 bits (otherwise it's a warning, bug #564).
799 || ((sizeof segh
.length
> 1)
800 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
)))
803 assegment_free_all (head
);
811 case AS_CONFED_SEQUENCE
:
816 assegment_free_all (head
);
820 /* now its safe to trust lengths */
821 seg
= assegment_new (segh
.type
, segh
.length
);
825 else /* it's the first segment */
828 for (i
= 0; i
< segh
.length
; i
++)
829 seg
->as
[i
] = (use32bit
) ? stream_getl (s
) : stream_getw (s
);
833 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
834 zlog_debug ("[AS4SEG] Parse aspath segment: Bytes now: %lu",
835 (unsigned long) bytes
);
840 *result
= assegment_normalise (head
);
844 /* AS path parse function. pnt is a pointer to byte stream and length
845 is length of byte stream. If there is same AS path in the the AS
846 path hash then return it else make new AS path structure.
848 On error NULL is returned.
851 aspath_parse (struct stream
*s
, size_t length
, int use32bit
)
856 /* If length is odd it's malformed AS path. */
857 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
858 * otherwise its malformed when length is larger than 2 and (length-2)
859 * is not dividable by 4.
860 * But... this time we're lazy
862 if (length
% AS16_VALUE_SIZE
)
865 memset (&as
, 0, sizeof (struct aspath
));
866 if (assegments_parse (s
, length
, &as
.segments
, use32bit
) < 0)
869 /* If already same aspath exist then return it. */
870 find
= hash_get (ashash
, &as
, aspath_hash_alloc
);
872 /* bug! should not happen, let the daemon crash below */
875 /* if the aspath was already hashed free temporary memory. */
878 assegment_free_all (as
.segments
);
879 /* aspath_key_make() always updates the string */
880 XFREE (MTYPE_AS_STR
, as
.str
);
883 json_object_free(as
.json
);
894 assegment_data_put (struct stream
*s
, as_t
*as
, int num
, int use32bit
)
897 assert (num
<= AS_SEGMENT_MAX
);
899 for (i
= 0; i
< num
; i
++)
901 stream_putl (s
, as
[i
]);
904 if ( as
[i
] <= BGP_AS_MAX
)
905 stream_putw(s
, as
[i
]);
907 stream_putw(s
, BGP_AS_TRANS
);
912 assegment_header_put (struct stream
*s
, u_char type
, int length
)
915 assert (length
<= AS_SEGMENT_MAX
);
916 stream_putc (s
, type
);
917 lenp
= stream_get_endp (s
);
918 stream_putc (s
, length
);
922 /* write aspath data to stream */
924 aspath_put (struct stream
*s
, struct aspath
*as
, int use32bit
)
926 struct assegment
*seg
= as
->segments
;
929 if (!seg
|| seg
->length
== 0)
935 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
936 * At the moment, we would write out a partial aspath, and our peer
937 * will complain and drop the session :-/
939 * The general assumption here is that many things tested will
940 * never happen. And, in real live, up to now, they have not.
942 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
) <= STREAM_WRITEABLE(s
)))
944 struct assegment
*next
= seg
->next
;
949 /* Overlength segments have to be split up */
950 while ( (seg
->length
- written
) > AS_SEGMENT_MAX
)
952 assegment_header_put (s
, seg
->type
, AS_SEGMENT_MAX
);
953 assegment_data_put (s
, seg
->as
, AS_SEGMENT_MAX
, use32bit
);
954 written
+= AS_SEGMENT_MAX
;
955 bytes
+= ASSEGMENT_SIZE (written
, use32bit
);
958 /* write the final segment, probably is also the first */
959 lenp
= assegment_header_put (s
, seg
->type
, seg
->length
- written
);
960 assegment_data_put (s
, (seg
->as
+ written
), seg
->length
- written
,
963 /* Sequence-type segments can be 'packed' together
964 * Case of a segment which was overlength and split up
965 * will be missed here, but that doesn't matter.
967 while (next
&& ASSEGMENTS_PACKABLE (seg
, next
))
969 /* NB: We should never normally get here given we
970 * normalise aspath data when parse them. However, better
971 * safe than sorry. We potentially could call
972 * assegment_normalise here instead, but it's cheaper and
973 * easier to do it on the fly here rather than go through
974 * the segment list twice every time we write out
978 /* Next segment's data can fit in this one */
979 assegment_data_put (s
, next
->as
, next
->length
, use32bit
);
981 /* update the length of the segment header */
982 stream_putc_at (s
, lenp
, seg
->length
- written
+ next
->length
);
983 asns_packed
+= next
->length
;
988 bytes
+= ASSEGMENT_SIZE (seg
->length
- written
+ asns_packed
,
996 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
997 * We have no way to manage the storage, so we use a static stream
998 * wrapper around aspath_put.
1001 aspath_snmp_pathseg (struct aspath
*as
, size_t *varlen
)
1003 #define SNMP_PATHSEG_MAX 1024
1006 snmp_stream
= stream_new (SNMP_PATHSEG_MAX
);
1008 stream_reset (snmp_stream
);
1015 aspath_put (snmp_stream
, as
, 0); /* use 16 bit for now here */
1017 *varlen
= stream_get_endp (snmp_stream
);
1018 return stream_pnt(snmp_stream
);
1021 #define min(A,B) ((A) < (B) ? (A) : (B))
1023 static struct assegment
*
1024 aspath_aggregate_as_set_add (struct aspath
*aspath
, struct assegment
*asset
,
1029 /* If this is first AS set member, create new as-set segment. */
1032 asset
= assegment_new (AS_SET
, 1);
1033 if (! aspath
->segments
)
1034 aspath
->segments
= asset
;
1037 struct assegment
*seg
= aspath
->segments
;
1042 asset
->type
= AS_SET
;
1048 /* Check this AS value already exists or not. */
1049 for (i
= 0; i
< asset
->length
; i
++)
1050 if (asset
->as
[i
] == as
)
1054 asset
->as
= XREALLOC (MTYPE_AS_SEG_DATA
, asset
->as
,
1055 asset
->length
* AS_VALUE_SIZE
);
1056 asset
->as
[asset
->length
- 1] = as
;
1063 /* Modify as1 using as2 for aggregation. */
1065 aspath_aggregate (struct aspath
*as1
, struct aspath
*as2
)
1071 struct assegment
*seg1
= as1
->segments
;
1072 struct assegment
*seg2
= as2
->segments
;
1073 struct aspath
*aspath
= NULL
;
1074 struct assegment
*asset
= NULL
;
1075 struct assegment
*prevseg
= NULL
;
1077 /* First of all check common leading sequence. */
1078 while (seg1
&& seg2
)
1080 /* Check segment type. */
1081 if (seg1
->type
!= seg2
->type
)
1084 /* Minimum segment length. */
1085 minlen
= min (seg1
->length
, seg2
->length
);
1087 for (match
= 0; match
< minlen
; match
++)
1088 if (seg1
->as
[match
] != seg2
->as
[match
])
1093 struct assegment
*seg
= assegment_new (seg1
->type
, 0);
1095 seg
= assegment_append_asns (seg
, seg1
->as
, match
);
1099 aspath
= aspath_new ();
1100 aspath
->segments
= seg
;
1103 prevseg
->next
= seg
;
1108 if (match
!= minlen
|| match
!= seg1
->length
1109 || seg1
->length
!= seg2
->length
)
1111 /* We are moving on to the next segment to reset match */
1120 aspath
= aspath_new();
1122 /* Make as-set using rest of all information. */
1126 for (i
= from
; i
< seg1
->length
; i
++)
1127 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg1
->as
[i
]);
1136 for (i
= from
; i
< seg2
->length
; i
++)
1137 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg2
->as
[i
]);
1143 assegment_normalise (aspath
->segments
);
1144 aspath_str_update (aspath
);
1148 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1149 attribute, check the leftmost AS number in the AS_PATH attribute is
1150 or not the peer's AS number. */
1152 aspath_firstas_check (struct aspath
*aspath
, as_t asno
)
1154 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
1157 if (aspath
->segments
1158 && (aspath
->segments
->type
== AS_SEQUENCE
)
1159 && (aspath
->segments
->as
[0] == asno
))
1166 aspath_get_first_as (struct aspath
*aspath
)
1168 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1171 return aspath
->segments
->as
[0];
1175 aspath_get_last_as (struct aspath
*aspath
)
1178 unsigned int last_as
= 0;
1179 const struct assegment
*seg
;
1181 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1184 seg
= aspath
->segments
;
1188 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1189 for (i
= 0; i
< seg
->length
; i
++)
1190 last_as
= seg
->as
[i
];
1197 /* AS path loop check. If aspath contains asno then return >= 1. */
1199 aspath_loop_check (struct aspath
*aspath
, as_t asno
)
1201 struct assegment
*seg
;
1204 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
1207 seg
= aspath
->segments
;
1213 for (i
= 0; i
< seg
->length
; i
++)
1214 if (seg
->as
[i
] == asno
)
1222 /* When all of AS path is private AS return 1. */
1224 aspath_private_as_check (struct aspath
*aspath
)
1226 struct assegment
*seg
;
1228 if ( !(aspath
&& aspath
->segments
) )
1231 seg
= aspath
->segments
;
1237 for (i
= 0; i
< seg
->length
; i
++)
1239 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1247 /* Return True if the entire ASPATH consist of the specified ASN */
1249 aspath_single_asn_check (struct aspath
*aspath
, as_t asn
)
1251 struct assegment
*seg
;
1253 if ( !(aspath
&& aspath
->segments
) )
1256 seg
= aspath
->segments
;
1262 for (i
= 0; i
< seg
->length
; i
++)
1264 if (seg
->as
[i
] != asn
)
1272 /* Replace all instances of the target ASN with our own ASN */
1274 aspath_replace_specific_asn (struct aspath
*aspath
, as_t target_asn
,
1278 struct assegment
*seg
;
1280 new = aspath_dup(aspath
);
1281 seg
= new->segments
;
1287 for (i
= 0; i
< seg
->length
; i
++)
1289 if (seg
->as
[i
] == target_asn
)
1290 seg
->as
[i
] = our_asn
;
1295 aspath_str_update(new);
1299 /* Replace all private ASNs with our own ASN */
1301 aspath_replace_private_asns (struct aspath
*aspath
, as_t asn
)
1304 struct assegment
*seg
;
1306 new = aspath_dup(aspath
);
1307 seg
= new->segments
;
1313 for (i
= 0; i
< seg
->length
; i
++)
1315 if (BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1321 aspath_str_update(new);
1325 /* Remove all private ASNs */
1327 aspath_remove_private_asns (struct aspath
*aspath
)
1330 struct assegment
*seg
;
1331 struct assegment
*new_seg
;
1332 struct assegment
*last_new_seg
;
1337 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
1341 last_new_seg
= NULL
;
1342 seg
= aspath
->segments
;
1346 for (i
= 0; i
< seg
->length
; i
++)
1349 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1355 // The entire segment is private so skip it
1362 // The entire segment is public so copy it
1363 else if (public == seg
->length
)
1365 new_seg
= assegment_dup (seg
);
1368 // The segment is a mix of public and private ASNs. Copy as many spots as
1369 // there are public ASNs then come back and fill in only the public ASNs.
1372 new_seg
= assegment_new (seg
->type
, public);
1374 for (i
= 0; i
< seg
->length
; i
++)
1377 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1379 new_seg
->as
[j
] = seg
->as
[i
];
1385 // This is the first segment so set the aspath segments pointer to this one
1387 new->segments
= new_seg
;
1389 last_new_seg
->next
= new_seg
;
1391 last_new_seg
= new_seg
;
1395 aspath_str_update(new);
1399 /* AS path confed check. If aspath contains confed set or sequence then return 1. */
1401 aspath_confed_check (struct aspath
*aspath
)
1403 struct assegment
*seg
;
1405 if ( !(aspath
&& aspath
->segments
) )
1408 seg
= aspath
->segments
;
1412 if (seg
->type
== AS_CONFED_SET
|| seg
->type
== AS_CONFED_SEQUENCE
)
1419 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1420 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1422 aspath_left_confed_check (struct aspath
*aspath
)
1425 if ( !(aspath
&& aspath
->segments
) )
1428 if ( (aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1429 || (aspath
->segments
->type
== AS_CONFED_SET
) )
1435 /* Merge as1 to as2. as2 should be uninterned aspath. */
1436 static struct aspath
*
1437 aspath_merge (struct aspath
*as1
, struct aspath
*as2
)
1439 struct assegment
*last
, *new;
1444 last
= new = assegment_dup_all (as1
->segments
);
1446 /* find the last valid segment */
1447 while (last
&& last
->next
)
1450 last
->next
= as2
->segments
;
1451 as2
->segments
= new;
1452 aspath_str_update (as2
);
1456 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1458 aspath_prepend (struct aspath
*as1
, struct aspath
*as2
)
1460 struct assegment
*seg1
;
1461 struct assegment
*seg2
;
1466 seg1
= as1
->segments
;
1467 seg2
= as2
->segments
;
1469 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1472 as2
->segments
= assegment_dup_all (as1
->segments
);
1473 aspath_str_update (as2
);
1477 /* If as1 is empty AS, no prepending to do. */
1481 /* find the tail as1's segment chain. */
1482 while (seg1
&& seg1
->next
)
1485 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1486 if (seg1
->type
== AS_SEQUENCE
&& seg2
->type
== AS_CONFED_SEQUENCE
)
1487 as2
= aspath_delete_confed_seq (as2
);
1489 /* Compare last segment type of as1 and first segment type of as2. */
1490 if (seg1
->type
!= seg2
->type
)
1491 return aspath_merge (as1
, as2
);
1493 if (seg1
->type
== AS_SEQUENCE
)
1495 /* We have two chains of segments, as1->segments and seg2,
1496 * and we have to attach them together, merging the attaching
1497 * segments together into one.
1499 * 1. dupe as1->segments onto head of as2
1500 * 2. merge seg2's asns onto last segment of this new chain
1501 * 3. attach chain after seg2
1504 /* dupe as1 onto as2's head */
1505 seg1
= as2
->segments
= assegment_dup_all (as1
->segments
);
1507 /* refind the tail of as2, reusing seg1 */
1508 while (seg1
&& seg1
->next
)
1511 /* merge the old head, seg2, into tail, seg1 */
1512 seg1
= assegment_append_asns (seg1
, seg2
->as
, seg2
->length
);
1514 /* bypass the merged seg2, and attach any chain after it to
1515 * chain descending from as2's head
1517 seg1
->next
= seg2
->next
;
1519 /* seg2 is now referenceless and useless*/
1520 assegment_free (seg2
);
1522 /* we've now prepended as1's segment chain to as2, merging
1523 * the inbetween AS_SEQUENCE of seg2 in the process
1525 aspath_str_update (as2
);
1530 /* AS_SET merge code is needed at here. */
1531 return aspath_merge (as1
, as2
);
1533 /* XXX: Ermmm, what if as1 has multiple segments?? */
1538 /* Iterate over AS_PATH segments and wipe all occurences of the
1539 * listed AS numbers. Hence some segments may lose some or even
1540 * all data on the way, the operation is implemented as a smarter
1541 * version of aspath_dup(), which allocates memory to hold the new
1542 * data, not the original. The new AS path is returned.
1545 aspath_filter_exclude (struct aspath
* source
, struct aspath
* exclude_list
)
1547 struct assegment
* srcseg
, * exclseg
, * lastseg
;
1548 struct aspath
* newpath
;
1550 newpath
= aspath_new();
1553 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
)
1555 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1556 struct assegment
* newseg
;
1558 /* Find out, how much ASns are we going to pick from this segment.
1559 * We can't perform filtering right inline, because the size of
1560 * the new segment isn't known at the moment yet.
1562 for (i
= 0; i
< srcseg
->length
; i
++)
1565 for (exclseg
= exclude_list
->segments
; exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1566 for (y
= 0; y
< exclseg
->length
; y
++)
1567 if (srcseg
->as
[i
] == exclseg
->as
[y
])
1570 // There's no sense in testing the rest of exclusion list, bail out.
1576 /* newlen is now the number of ASns to copy */
1580 /* Actual copying. Allocate memory and iterate once more, performing filtering. */
1581 newseg
= assegment_new (srcseg
->type
, newlen
);
1582 for (i
= 0; i
< srcseg
->length
; i
++)
1585 for (exclseg
= exclude_list
->segments
; exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1586 for (y
= 0; y
< exclseg
->length
; y
++)
1587 if (srcseg
->as
[i
] == exclseg
->as
[y
])
1594 newseg
->as
[done
++] = srcseg
->as
[i
];
1596 /* At his point newlen must be equal to done, and both must be positive. Append
1597 * the filtered segment to the gross result. */
1599 newpath
->segments
= newseg
;
1601 lastseg
->next
= newseg
;
1604 aspath_str_update (newpath
);
1605 /* We are happy returning even an empty AS_PATH, because the administrator
1606 * might expect this very behaviour. There's a mean to avoid this, if necessary,
1607 * by having a match rule against certain AS_PATH regexps in the route-map index.
1609 aspath_free (source
);
1613 /* Add specified AS to the leftmost of aspath. */
1614 static struct aspath
*
1615 aspath_add_asns (struct aspath
*aspath
, as_t asno
, u_char type
, unsigned num
)
1617 struct assegment
*assegment
= aspath
->segments
;
1620 if (assegment
&& assegment
->type
== type
)
1622 /* extend existing segment */
1623 aspath
->segments
= assegment_prepend_asns (aspath
->segments
, asno
, num
);
1627 /* prepend with new segment */
1628 struct assegment
*newsegment
= assegment_new (type
, num
);
1629 for (i
= 0; i
< num
; i
++)
1630 newsegment
->as
[i
] = asno
;
1632 /* insert potentially replacing empty segment */
1633 if (assegment
&& assegment
->length
== 0)
1635 newsegment
->next
= assegment
->next
;
1636 assegment_free (assegment
);
1639 newsegment
->next
= assegment
;
1640 aspath
->segments
= newsegment
;
1643 aspath_str_update (aspath
);
1647 /* Add specified AS to the leftmost of aspath num times. */
1649 aspath_add_seq_n (struct aspath
*aspath
, as_t asno
, unsigned num
)
1651 return aspath_add_asns (aspath
, asno
, AS_SEQUENCE
, num
);
1654 /* Add specified AS to the leftmost of aspath. */
1656 aspath_add_seq (struct aspath
*aspath
, as_t asno
)
1658 return aspath_add_asns (aspath
, asno
, AS_SEQUENCE
, 1);
1661 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1662 as2's leftmost AS is same return 1. */
1664 aspath_cmp_left (const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1666 const struct assegment
*seg1
;
1667 const struct assegment
*seg2
;
1669 if (!(aspath1
&& aspath2
))
1672 seg1
= aspath1
->segments
;
1673 seg2
= aspath2
->segments
;
1675 /* If both paths are originated in this AS then we do want to compare MED */
1679 /* find first non-confed segments for each */
1680 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1681 || (seg1
->type
== AS_CONFED_SET
)))
1684 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1685 || (seg2
->type
== AS_CONFED_SET
)))
1690 && (seg1
->type
== AS_SEQUENCE
) && (seg2
->type
== AS_SEQUENCE
)))
1693 if (seg1
->as
[0] == seg2
->as
[0])
1699 /* Truncate an aspath after a number of hops, and put the hops remaining
1700 * at the front of another aspath. Needed for AS4 compat.
1702 * Returned aspath is a /new/ aspath, which should either by free'd or
1703 * interned by the caller, as desired.
1706 aspath_reconcile_as4 ( struct aspath
*aspath
, struct aspath
*as4path
)
1708 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1709 struct aspath
*newpath
= NULL
, *mergedpath
;
1710 int hops
, cpasns
= 0;
1715 seg
= aspath
->segments
;
1717 /* CONFEDs should get reconciled too.. */
1718 hops
= (aspath_count_hops (aspath
) + aspath_count_confeds (aspath
))
1719 - aspath_count_hops (as4path
);
1723 if (BGP_DEBUG (as4
, AS4
))
1724 zlog_warn ("[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1725 /* Something's gone wrong. The RFC says we should now ignore AS4_PATH,
1726 * which is daft behaviour - it contains vital loop-detection
1727 * information which must have been removed from AS_PATH.
1729 hops
= aspath_count_hops (aspath
);
1734 newpath
= aspath_dup (as4path
);
1735 aspath_str_update(newpath
);
1739 if ( BGP_DEBUG(as4
, AS4
))
1740 zlog_debug("[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1741 aspath
->str
, as4path
->str
);
1743 while (seg
&& hops
> 0)
1750 cpasns
= seg
->length
;
1752 case AS_CONFED_SEQUENCE
:
1753 /* Should never split a confed-sequence, if hop-count
1754 * suggests we must then something's gone wrong somewhere.
1756 * Most important goal is to preserve AS_PATHs prime function
1757 * as loop-detector, so we fudge the numbers so that the entire
1758 * confed-sequence is merged in.
1760 if (hops
< seg
->length
)
1762 if (BGP_DEBUG (as4
, AS4
))
1763 zlog_debug ("[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1764 " across 2/4 ASN boundary somewhere, broken..");
1768 cpasns
= MIN(seg
->length
, hops
);
1769 hops
-= seg
->length
;
1772 assert (cpasns
<= seg
->length
);
1774 newseg
= assegment_new (seg
->type
, 0);
1775 newseg
= assegment_append_asns (newseg
, seg
->as
, cpasns
);
1779 newpath
= aspath_new ();
1780 newpath
->segments
= newseg
;
1783 prevseg
->next
= newseg
;
1789 /* We may be able to join some segments here, and we must
1790 * do this because... we want normalised aspaths in out hash
1791 * and we do not want to stumble in aspath_put.
1793 mergedpath
= aspath_merge (newpath
, aspath_dup(as4path
));
1794 aspath_free (newpath
);
1795 mergedpath
->segments
= assegment_normalise (mergedpath
->segments
);
1796 aspath_str_update (mergedpath
);
1798 if ( BGP_DEBUG(as4
, AS4
))
1799 zlog_debug ("[AS4] result of synthesizing is %s",
1805 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1806 as2's leftmost AS is same return 1. (confederation as-path
1809 aspath_cmp_left_confed (const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1811 if (! (aspath1
&& aspath2
) )
1814 if ( !(aspath1
->segments
&& aspath2
->segments
) )
1817 if ( (aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1818 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
) )
1821 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1827 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1828 * RFC 5065 section 4.1.c.1
1830 * 1) if any path segments of the AS_PATH are of the type
1831 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1832 * removed from the AS_PATH attribute, leaving the sanitized
1833 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1836 aspath_delete_confed_seq (struct aspath
*aspath
)
1838 struct assegment
*seg
, *prev
, *next
;
1839 char removed_confed_segment
;
1841 if (!(aspath
&& aspath
->segments
))
1844 seg
= aspath
->segments
;
1845 removed_confed_segment
= 0;
1853 if (seg
->type
== AS_CONFED_SEQUENCE
|| seg
->type
== AS_CONFED_SET
)
1855 /* This is the first segment in the aspath */
1856 if (aspath
->segments
== seg
)
1857 aspath
->segments
= seg
->next
;
1859 prev
->next
= seg
->next
;
1861 assegment_free (seg
);
1862 removed_confed_segment
= 1;
1870 if (removed_confed_segment
)
1871 aspath_str_update (aspath
);
1876 /* Add new AS number to the leftmost part of the aspath as
1877 AS_CONFED_SEQUENCE. */
1879 aspath_add_confed_seq (struct aspath
*aspath
, as_t asno
)
1881 return aspath_add_asns (aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1884 /* Add new as value to as path structure. */
1886 aspath_as_add (struct aspath
*as
, as_t asno
)
1888 struct assegment
*seg
= as
->segments
;
1893 /* Last segment search procedure. */
1897 assegment_append_asns (seg
, &asno
, 1);
1900 /* Add new as segment to the as path. */
1902 aspath_segment_add (struct aspath
*as
, int type
)
1904 struct assegment
*seg
= as
->segments
;
1905 struct assegment
*new = assegment_new (type
, 0);
1920 return aspath_parse (NULL
, 0, 1); /* 32Bit ;-) */
1924 aspath_empty_get (void)
1926 struct aspath
*aspath
;
1928 aspath
= aspath_new ();
1929 aspath_make_str_count (aspath
);
1936 return ashash
->count
;
1940 Theoretically, one as path can have:
1942 One BGP packet size should be less than 4096.
1943 One BGP attribute size should be less than 4096 - BGP header size.
1944 One BGP aspath size should be less than 4096 - BGP header size -
1945 BGP mandantry attribute size.
1948 /* AS path string lexical token enum. */
1954 as_token_confed_seq_start
,
1955 as_token_confed_seq_end
,
1956 as_token_confed_set_start
,
1957 as_token_confed_set_end
,
1961 /* Return next token and point for string parse. */
1963 aspath_gettoken (const char *buf
, enum as_token
*token
, u_long
*asno
)
1965 const char *p
= buf
;
1967 /* Skip seperators (space for sequences, ',' for sets). */
1968 while (isspace ((int) *p
) || *p
== ',')
1971 /* Check the end of the string and type specify characters
1978 *token
= as_token_set_start
;
1982 *token
= as_token_set_end
;
1986 *token
= as_token_confed_seq_start
;
1990 *token
= as_token_confed_seq_end
;
1994 *token
= as_token_confed_set_start
;
1998 *token
= as_token_confed_set_end
;
2003 /* Check actual AS value. */
2004 if (isdigit ((int) *p
))
2008 *token
= as_token_asval
;
2012 while (isdigit ((int) *p
))
2015 asval
+= (*p
- '0');
2022 /* There is no match then return unknown token. */
2023 *token
= as_token_unknown
;
2028 aspath_str2aspath (const char *str
)
2030 enum as_token token
= as_token_unknown
;
2033 struct aspath
*aspath
;
2036 aspath
= aspath_new ();
2038 /* We start default type as AS_SEQUENCE. */
2039 as_type
= AS_SEQUENCE
;
2042 while ((str
= aspath_gettoken (str
, &token
, &asno
)) != NULL
)
2046 case as_token_asval
:
2049 aspath_segment_add (aspath
, as_type
);
2052 aspath_as_add (aspath
, asno
);
2054 case as_token_set_start
:
2056 aspath_segment_add (aspath
, as_type
);
2059 case as_token_set_end
:
2060 as_type
= AS_SEQUENCE
;
2063 case as_token_confed_seq_start
:
2064 as_type
= AS_CONFED_SEQUENCE
;
2065 aspath_segment_add (aspath
, as_type
);
2068 case as_token_confed_seq_end
:
2069 as_type
= AS_SEQUENCE
;
2072 case as_token_confed_set_start
:
2073 as_type
= AS_CONFED_SET
;
2074 aspath_segment_add (aspath
, as_type
);
2077 case as_token_confed_set_end
:
2078 as_type
= AS_SEQUENCE
;
2081 case as_token_unknown
:
2083 aspath_free (aspath
);
2088 aspath_make_str_count (aspath
);
2093 /* Make hash value by raw aspath data. */
2095 aspath_key_make (void *p
)
2097 struct aspath
*aspath
= (struct aspath
*) p
;
2098 unsigned int key
= 0;
2101 aspath_str_update (aspath
);
2103 key
= jhash (aspath
->str
, aspath
->str_len
, 2334325);
2108 /* If two aspath have same value then return 1 else return 0 */
2110 aspath_cmp (const void *arg1
, const void *arg2
)
2112 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2113 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2115 while (seg1
|| seg2
)
2118 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2120 if (seg1
->type
!= seg2
->type
)
2122 if (seg1
->length
!= seg2
->length
)
2124 for (i
= 0; i
< seg1
->length
; i
++)
2125 if (seg1
->as
[i
] != seg2
->as
[i
])
2133 /* AS path hash initialize. */
2137 ashash
= hash_create_size (32768, aspath_key_make
, aspath_cmp
);
2141 aspath_finish (void)
2143 hash_clean (ashash
, (void (*)(void *))aspath_free
);
2148 stream_free (snmp_stream
);
2151 /* return and as path value */
2153 aspath_print (struct aspath
*as
)
2155 return (as
? as
->str
: NULL
);
2158 /* Printing functions */
2159 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
2160 * AS_PATH wasn't empty.
2163 aspath_print_vty (struct vty
*vty
, const char *format
, struct aspath
*as
, const char * suffix
)
2166 vty_out (vty
, format
, as
->str
);
2167 if (as
->str_len
&& strlen (suffix
))
2168 vty_out (vty
, "%s", suffix
);
2172 aspath_show_all_iterator (struct hash_backet
*backet
, struct vty
*vty
)
2176 as
= (struct aspath
*) backet
->data
;
2178 vty_out (vty
, "[%p:%u] (%ld) ", (void *)backet
, backet
->key
, as
->refcnt
);
2179 vty_out (vty
, "%s%s", as
->str
, VTY_NEWLINE
);
2182 /* Print all aspath and hash information. This function is used from
2183 `show [ip] bgp paths' command. */
2185 aspath_print_all_vty (struct vty
*vty
)
2187 hash_iterate (ashash
,
2188 (void (*) (struct hash_backet
*, void *))
2189 aspath_show_all_iterator
,