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
33 #include "bgpd/bgpd.h"
34 #include "bgpd/bgp_aspath.h"
35 #include "bgpd/bgp_debug.h"
36 #include "bgpd/bgp_attr.h"
38 /* Attr. Flags and Attr. Type Code. */
39 #define AS_HEADER_SIZE 2
41 /* Now FOUR octets are used for AS value. */
42 #define AS_VALUE_SIZE sizeof (as_t)
43 /* This is the old one */
44 #define AS16_VALUE_SIZE sizeof (as16_t)
46 /* Maximum protocol segment length value */
47 #define AS_SEGMENT_MAX 255
49 /* The following length and size macros relate specifically to Quagga's
50 * internal representation of AS-Segments, not per se to the on-wire
51 * sizes and lengths. At present (200508) they sort of match, however
52 * the ONLY functions which should now about the on-wire syntax are
53 * aspath_put, assegment_put and assegment_parse.
55 * aspath_put returns bytes written, the only definitive record of
56 * size of wire-format attribute..
59 /* Calculated size in bytes of ASN segment data to hold N ASN's */
60 #define ASSEGMENT_DATA_SIZE(N,S) \
61 ((N) * ( (S) ? AS_VALUE_SIZE : AS16_VALUE_SIZE) )
63 /* Calculated size of segment struct to hold N ASN's */
64 #define ASSEGMENT_SIZE(N,S) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N,S))
66 /* AS segment octet length. */
67 #define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S)
69 /* AS_SEQUENCE segments can be packed together */
70 /* Can the types of X and Y be considered for packing? */
71 #define ASSEGMENT_TYPES_PACKABLE(X,Y) \
72 ( ((X)->type == (Y)->type) \
73 && ((X)->type == AS_SEQUENCE))
74 /* Types and length of X,Y suitable for packing? */
75 #define ASSEGMENTS_PACKABLE(X,Y) \
76 ( ASSEGMENT_TYPES_PACKABLE( (X), (Y)) \
77 && ( ((X)->length + (Y)->length) <= AS_SEGMENT_MAX ) )
79 /* As segment header - the on-wire representation
80 * NOT the internal representation!
82 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 */
96 assegment_data_new (int num
)
98 return (XMALLOC (MTYPE_AS_SEG_DATA
, ASSEGMENT_DATA_SIZE (num
, 1)));
101 /* Get a new segment. Note that 0 is an allowed length,
102 * and will result in a segment with no allocated data segment.
103 * the caller should immediately assign data to the segment, as the segment
104 * otherwise is not generally valid
106 static struct assegment
*
107 assegment_new (u_char type
, u_short length
)
109 struct assegment
*new;
111 new = XCALLOC (MTYPE_AS_SEG
, sizeof (struct assegment
));
114 new->as
= assegment_data_new (length
);
116 new->length
= length
;
123 assegment_free (struct assegment
*seg
)
129 XFREE (MTYPE_AS_SEG_DATA
, seg
->as
);
130 memset (seg
, 0xfe, sizeof(struct assegment
));
131 XFREE (MTYPE_AS_SEG
, seg
);
136 /* free entire chain of segments */
138 assegment_free_all (struct assegment
*seg
)
140 struct assegment
*prev
;
146 assegment_free (prev
);
150 /* Duplicate just the given assegment and its data */
151 static struct assegment
*
152 assegment_dup (struct assegment
*seg
)
154 struct assegment
*new;
156 new = assegment_new (seg
->type
, seg
->length
);
157 memcpy (new->as
, seg
->as
, ASSEGMENT_DATA_SIZE (new->length
, 1) );
162 /* Duplicate entire chain of assegments, return the head */
163 static struct assegment
*
164 assegment_dup_all (struct assegment
*seg
)
166 struct assegment
*new = NULL
;
167 struct assegment
*head
= NULL
;
173 new->next
= assegment_dup (seg
);
177 head
= new = assegment_dup (seg
);
184 /* prepend the as number to given segment, given num of times */
185 static struct assegment
*
186 assegment_prepend_asns (struct assegment
*seg
, as_t asnum
, int num
)
194 if (num
>= AS_SEGMENT_MAX
)
195 return seg
; /* we don't do huge prepends */
197 newas
= assegment_data_new (seg
->length
+ num
);
199 for (i
= 0; i
< num
; i
++)
202 memcpy (newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE (seg
->length
, 1));
203 XFREE (MTYPE_AS_SEG_DATA
, seg
->as
);
210 /* append given array of as numbers to the segment */
211 static struct assegment
*
212 assegment_append_asns (struct assegment
*seg
, as_t
*asnos
, int num
)
216 newas
= XREALLOC (MTYPE_AS_SEG_DATA
, seg
->as
,
217 ASSEGMENT_DATA_SIZE (seg
->length
+ num
, 1));
222 memcpy (seg
->as
+ seg
->length
, asnos
, ASSEGMENT_DATA_SIZE(num
, 1));
227 assegment_free_all (seg
);
232 int_cmp (const void *p1
, const void *p2
)
234 const as_t
*as1
= p1
;
235 const as_t
*as2
= p2
;
237 return (*as1
== *as2
)
238 ? 0 : ( (*as1
> *as2
) ? 1 : -1);
241 /* normalise the segment.
242 * In particular, merge runs of AS_SEQUENCEs into one segment
243 * Internally, we do not care about the wire segment length limit, and
244 * we want each distinct AS_PATHs to have the exact same internal
245 * representation - eg, so that our hashing actually works..
247 static struct assegment
*
248 assegment_normalise (struct assegment
*head
)
250 struct assegment
*seg
= head
, *pin
;
251 struct assegment
*tmp
;
260 /* Sort values SET segments, for determinism in paths to aid
261 * creation of hash values / path comparisons
262 * and because it helps other lesser implementations ;)
264 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
)
269 qsort (seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
272 for (i
=1; i
< seg
->length
; i
++)
274 if (seg
->as
[tail
] == seg
->as
[i
])
279 seg
->as
[tail
] = seg
->as
[i
];
281 /* seg->length can be 0.. */
283 seg
->length
= tail
+ 1;
286 /* read ahead from the current, pinned segment while the segments
287 * are packable/mergeable. Append all following packable segments
288 * to the segment we have pinned and remove these appended
291 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
))
296 /* append the next sequence to the pinned sequence */
297 pin
= assegment_append_asns (pin
, seg
->as
, seg
->length
);
299 /* bypass the next sequence */
300 pin
->next
= seg
->next
;
302 /* get rid of the now referenceless segment */
303 assegment_free (tmp
);
312 static struct aspath
*
315 return XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
318 /* Free AS path structure. */
320 aspath_free (struct aspath
*aspath
)
324 if (aspath
->segments
)
325 assegment_free_all (aspath
->segments
);
327 XFREE (MTYPE_AS_STR
, aspath
->str
);
328 XFREE (MTYPE_AS_PATH
, aspath
);
331 /* Unintern aspath from AS path bucket. */
333 aspath_unintern (struct aspath
**aspath
)
336 struct aspath
*asp
= *aspath
;
341 if (asp
->refcnt
== 0)
343 /* This aspath must exist in aspath hash table. */
344 ret
= hash_release (ashash
, asp
);
345 assert (ret
!= NULL
);
351 /* Return the start or end delimiters for a particular Segment type */
352 #define AS_SEG_START 0
355 aspath_delimiter_char (u_char type
, u_char which
)
363 } aspath_delim_char
[] =
365 { AS_SET
, '{', '}' },
366 { AS_CONFED_SET
, '[', ']' },
367 { AS_CONFED_SEQUENCE
, '(', ')' },
371 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++)
373 if (aspath_delim_char
[i
].type
== type
)
375 if (which
== AS_SEG_START
)
376 return aspath_delim_char
[i
].start
;
377 else if (which
== AS_SEG_END
)
378 return aspath_delim_char
[i
].end
;
384 /* countup asns from this segment and index onward */
386 assegment_count_asns (struct assegment
*seg
, int from
)
392 count
+= seg
->length
;
395 count
+= (seg
->length
- from
);
404 aspath_count_confeds (struct aspath
*aspath
)
407 struct assegment
*seg
= aspath
->segments
;
411 if (seg
->type
== AS_CONFED_SEQUENCE
)
412 count
+= seg
->length
;
413 else if (seg
->type
== AS_CONFED_SET
)
422 aspath_count_hops (struct aspath
*aspath
)
425 struct assegment
*seg
= aspath
->segments
;
429 if (seg
->type
== AS_SEQUENCE
)
430 count
+= seg
->length
;
431 else if (seg
->type
== AS_SET
)
439 /* Estimate size aspath /might/ take if encoded into an
442 * This is a quick estimate, not definitive! aspath_put()
443 * may return a different number!!
446 aspath_size (struct aspath
*aspath
)
449 struct assegment
*seg
= aspath
->segments
;
453 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
459 /* Return highest public ASN in path */
461 aspath_highest (struct aspath
*aspath
)
463 struct assegment
*seg
= aspath
->segments
;
469 for (i
= 0; i
< seg
->length
; i
++)
470 if (seg
->as
[i
] > highest
&& !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
471 highest
= seg
->as
[i
];
477 /* Return 1 if there are any 4-byte ASes in the path */
479 aspath_has_as4 (struct aspath
*aspath
)
481 struct assegment
*seg
= aspath
->segments
;
486 for (i
= 0; i
< seg
->length
; i
++)
487 if (seg
->as
[i
] > BGP_AS_MAX
)
494 /* Convert aspath structure to string expression. */
496 aspath_make_str_count (struct aspath
*as
)
498 struct assegment
*seg
;
506 as
->str
= XMALLOC (MTYPE_AS_STR
, 1);
514 /* ASN takes 5 to 10 chars plus seperator, see below.
515 * If there is one differing segment type, we need an additional
516 * 2 chars for segment delimiters, and the final '\0'.
517 * Hopefully this is large enough to avoid hitting the realloc
518 * code below for most common sequences.
520 * This was changed to 10 after the well-known BGP assertion, which
521 * had hit some parts of the Internet in May of 2009.
523 #define ASN_STR_LEN (10 + 1)
524 str_size
= MAX (assegment_count_asns (seg
, 0) * ASN_STR_LEN
+ 2 + 1,
525 ASPATH_STR_DEFAULT_LEN
);
526 str_buf
= XMALLOC (MTYPE_AS_STR
, str_size
);
533 /* Check AS type validity. Set seperator for segment */
541 case AS_CONFED_SEQUENCE
:
545 XFREE (MTYPE_AS_STR
, str_buf
);
551 /* We might need to increase str_buf, particularly if path has
552 * differing segments types, our initial guesstimate above will
553 * have been wrong. Need 10 chars for ASN, a seperator each and
554 * potentially two segment delimiters, plus a space between each
555 * segment and trailing zero.
557 * This definitely didn't work with the value of 5 bytes and
560 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
561 if ( (len
+ SEGMENT_STR_LEN(seg
)) > str_size
)
563 str_size
= len
+ SEGMENT_STR_LEN(seg
);
564 str_buf
= XREALLOC (MTYPE_AS_STR
, str_buf
, str_size
);
567 #undef SEGMENT_STR_LEN
569 if (seg
->type
!= AS_SEQUENCE
)
570 len
+= snprintf (str_buf
+ len
, str_size
- len
,
572 aspath_delimiter_char (seg
->type
, AS_SEG_START
));
574 /* write out the ASNs, with their seperators, bar the last one*/
575 for (i
= 0; i
< seg
->length
; i
++)
577 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%u", seg
->as
[i
]);
579 if (i
< (seg
->length
- 1))
580 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c", seperator
);
583 if (seg
->type
!= AS_SEQUENCE
)
584 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c",
585 aspath_delimiter_char (seg
->type
, AS_SEG_END
));
587 len
+= snprintf (str_buf
+ len
, str_size
- len
, " ");
592 assert (len
< str_size
);
602 aspath_str_update (struct aspath
*as
)
605 XFREE (MTYPE_AS_STR
, as
->str
);
606 aspath_make_str_count (as
);
609 /* Intern allocated AS path. */
611 aspath_intern (struct aspath
*aspath
)
615 /* Assert this AS path structure is not interned and has the string
616 representation built. */
617 assert (aspath
->refcnt
== 0);
618 assert (aspath
->str
);
620 /* Check AS path hash. */
621 find
= hash_get (ashash
, aspath
, hash_alloc_intern
);
623 aspath_free (aspath
);
630 /* Duplicate aspath structure. Created same aspath structure but
631 reference count and AS path string is cleared. */
633 aspath_dup (struct aspath
*aspath
)
635 unsigned short buflen
= aspath
->str_len
+ 1;
638 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
640 if (aspath
->segments
)
641 new->segments
= assegment_dup_all (aspath
->segments
);
646 new->str
= XMALLOC (MTYPE_AS_STR
, buflen
);
647 new->str_len
= aspath
->str_len
;
649 /* copy the string data */
650 if (aspath
->str_len
> 0)
651 memcpy (new->str
, aspath
->str
, buflen
);
659 aspath_hash_alloc (void *arg
)
661 const struct aspath
*aspath
= arg
;
664 /* Malformed AS path value. */
665 assert (aspath
->str
);
669 /* New aspath structure is needed. */
670 new = XMALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
672 /* Reuse segments and string representation */
674 new->segments
= aspath
->segments
;
675 new->str
= aspath
->str
;
676 new->str_len
= aspath
->str_len
;
681 /* parse as-segment byte stream in struct assegment */
683 assegments_parse (struct stream
*s
, size_t length
,
684 struct assegment
**result
, int use32bit
)
686 struct assegment_header segh
;
687 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
690 /* empty aspath (ie iBGP or somesuch) */
694 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
695 zlog_debug ("[AS4SEG] Parse aspath segment: got total byte length %lu",
696 (unsigned long) length
);
698 if ((STREAM_READABLE(s
) < length
)
699 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
700 || (length
% AS16_VALUE_SIZE
))
703 while (bytes
< length
)
708 if ((length
- bytes
) <= AS_HEADER_SIZE
)
711 assegment_free_all (head
);
715 /* softly softly, get the header first on its own */
716 segh
.type
= stream_getc (s
);
717 segh
.length
= stream_getc (s
);
719 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
721 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
722 zlog_debug ("[AS4SEG] Parse aspath segment: got type %d, length %d",
723 segh
.type
, segh
.length
);
726 if ( ((bytes
+ seg_size
) > length
)
727 /* 1771bis 4.3b: seg length contains one or more */
728 || (segh
.length
== 0)
729 /* Paranoia in case someone changes type of segment length.
730 * Shift both values by 0x10 to make the comparison operate
731 * on more, than 8 bits (otherwise it's a warning, bug #564).
733 || ((sizeof segh
.length
> 1)
734 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
)))
737 assegment_free_all (head
);
745 case AS_CONFED_SEQUENCE
:
750 assegment_free_all (head
);
754 /* now its safe to trust lengths */
755 seg
= assegment_new (segh
.type
, segh
.length
);
759 else /* it's the first segment */
762 for (i
= 0; i
< segh
.length
; i
++)
763 seg
->as
[i
] = (use32bit
) ? stream_getl (s
) : stream_getw (s
);
767 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
768 zlog_debug ("[AS4SEG] Parse aspath segment: Bytes now: %lu",
769 (unsigned long) bytes
);
774 *result
= assegment_normalise (head
);
778 /* AS path parse function. pnt is a pointer to byte stream and length
779 is length of byte stream. If there is same AS path in the the AS
780 path hash then return it else make new AS path structure.
782 On error NULL is returned.
785 aspath_parse (struct stream
*s
, size_t length
, int use32bit
)
790 /* If length is odd it's malformed AS path. */
791 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
792 * otherwise its malformed when length is larger than 2 and (length-2)
793 * is not dividable by 4.
794 * But... this time we're lazy
796 if (length
% AS16_VALUE_SIZE
)
799 memset (&as
, 0, sizeof (struct aspath
));
800 if (assegments_parse (s
, length
, &as
.segments
, use32bit
) < 0)
803 /* If already same aspath exist then return it. */
804 find
= hash_get (ashash
, &as
, aspath_hash_alloc
);
806 /* bug! should not happen, let the daemon crash below */
809 /* if the aspath was already hashed free temporary memory. */
812 assegment_free_all (as
.segments
);
813 /* aspath_key_make() always updates the string */
814 XFREE (MTYPE_AS_STR
, as
.str
);
823 assegment_data_put (struct stream
*s
, as_t
*as
, int num
, int use32bit
)
826 assert (num
<= AS_SEGMENT_MAX
);
828 for (i
= 0; i
< num
; i
++)
830 stream_putl (s
, as
[i
]);
833 if ( as
[i
] <= BGP_AS_MAX
)
834 stream_putw(s
, as
[i
]);
836 stream_putw(s
, BGP_AS_TRANS
);
841 assegment_header_put (struct stream
*s
, u_char type
, int length
)
844 assert (length
<= AS_SEGMENT_MAX
);
845 stream_putc (s
, type
);
846 lenp
= stream_get_endp (s
);
847 stream_putc (s
, length
);
851 /* write aspath data to stream */
853 aspath_put (struct stream
*s
, struct aspath
*as
, int use32bit
)
855 struct assegment
*seg
= as
->segments
;
858 if (!seg
|| seg
->length
== 0)
864 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
865 * At the moment, we would write out a partial aspath, and our peer
866 * will complain and drop the session :-/
868 * The general assumption here is that many things tested will
869 * never happen. And, in real live, up to now, they have not.
871 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
) <= STREAM_WRITEABLE(s
)))
873 struct assegment
*next
= seg
->next
;
878 /* Overlength segments have to be split up */
879 while ( (seg
->length
- written
) > AS_SEGMENT_MAX
)
881 assegment_header_put (s
, seg
->type
, AS_SEGMENT_MAX
);
882 assegment_data_put (s
, seg
->as
, AS_SEGMENT_MAX
, use32bit
);
883 written
+= AS_SEGMENT_MAX
;
884 bytes
+= ASSEGMENT_SIZE (written
, use32bit
);
887 /* write the final segment, probably is also the first */
888 lenp
= assegment_header_put (s
, seg
->type
, seg
->length
- written
);
889 assegment_data_put (s
, (seg
->as
+ written
), seg
->length
- written
,
892 /* Sequence-type segments can be 'packed' together
893 * Case of a segment which was overlength and split up
894 * will be missed here, but that doesn't matter.
896 while (next
&& ASSEGMENTS_PACKABLE (seg
, next
))
898 /* NB: We should never normally get here given we
899 * normalise aspath data when parse them. However, better
900 * safe than sorry. We potentially could call
901 * assegment_normalise here instead, but it's cheaper and
902 * easier to do it on the fly here rather than go through
903 * the segment list twice every time we write out
907 /* Next segment's data can fit in this one */
908 assegment_data_put (s
, next
->as
, next
->length
, use32bit
);
910 /* update the length of the segment header */
911 stream_putc_at (s
, lenp
, seg
->length
- written
+ next
->length
);
912 asns_packed
+= next
->length
;
917 bytes
+= ASSEGMENT_SIZE (seg
->length
- written
+ asns_packed
,
925 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
926 * We have no way to manage the storage, so we use a static stream
927 * wrapper around aspath_put.
930 aspath_snmp_pathseg (struct aspath
*as
, size_t *varlen
)
932 #define SNMP_PATHSEG_MAX 1024
935 snmp_stream
= stream_new (SNMP_PATHSEG_MAX
);
937 stream_reset (snmp_stream
);
944 aspath_put (snmp_stream
, as
, 0); /* use 16 bit for now here */
946 *varlen
= stream_get_endp (snmp_stream
);
947 return stream_pnt(snmp_stream
);
950 #define min(A,B) ((A) < (B) ? (A) : (B))
952 static struct assegment
*
953 aspath_aggregate_as_set_add (struct aspath
*aspath
, struct assegment
*asset
,
958 /* If this is first AS set member, create new as-set segment. */
961 asset
= assegment_new (AS_SET
, 1);
962 if (! aspath
->segments
)
963 aspath
->segments
= asset
;
966 struct assegment
*seg
= aspath
->segments
;
971 asset
->type
= AS_SET
;
977 /* Check this AS value already exists or not. */
978 for (i
= 0; i
< asset
->length
; i
++)
979 if (asset
->as
[i
] == as
)
983 asset
->as
= XREALLOC (MTYPE_AS_SEG_DATA
, asset
->as
,
984 asset
->length
* AS_VALUE_SIZE
);
985 asset
->as
[asset
->length
- 1] = as
;
992 /* Modify as1 using as2 for aggregation. */
994 aspath_aggregate (struct aspath
*as1
, struct aspath
*as2
)
1000 struct assegment
*seg1
= as1
->segments
;
1001 struct assegment
*seg2
= as2
->segments
;
1002 struct aspath
*aspath
= NULL
;
1003 struct assegment
*asset
;
1004 struct assegment
*prevseg
= NULL
;
1011 /* First of all check common leading sequence. */
1012 while (seg1
&& seg2
)
1014 /* Check segment type. */
1015 if (seg1
->type
!= seg2
->type
)
1018 /* Minimum segment length. */
1019 minlen
= min (seg1
->length
, seg2
->length
);
1021 for (match
= 0; match
< minlen
; match
++)
1022 if (seg1
->as
[match
] != seg2
->as
[match
])
1027 struct assegment
*seg
= assegment_new (seg1
->type
, 0);
1029 seg
= assegment_append_asns (seg
, seg1
->as
, match
);
1033 aspath
= aspath_new ();
1034 aspath
->segments
= seg
;
1037 prevseg
->next
= seg
;
1042 if (match
!= minlen
|| match
!= seg1
->length
1043 || seg1
->length
!= seg2
->length
)
1045 /* We are moving on to the next segment to reset match */
1054 aspath
= aspath_new();
1056 /* Make as-set using rest of all information. */
1060 for (i
= from
; i
< seg1
->length
; i
++)
1061 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg1
->as
[i
]);
1070 for (i
= from
; i
< seg2
->length
; i
++)
1071 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg2
->as
[i
]);
1077 assegment_normalise (aspath
->segments
);
1078 aspath_str_update (aspath
);
1082 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1083 attribute, check the leftmost AS number in the AS_PATH attribute is
1084 or not the peer's AS number. */
1086 aspath_firstas_check (struct aspath
*aspath
, as_t asno
)
1088 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
1091 if (aspath
->segments
1092 && (aspath
->segments
->type
== AS_SEQUENCE
)
1093 && (aspath
->segments
->as
[0] == asno
))
1099 /* AS path loop check. If aspath contains asno then return >= 1. */
1101 aspath_loop_check (struct aspath
*aspath
, as_t asno
)
1103 struct assegment
*seg
;
1106 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
1109 seg
= aspath
->segments
;
1115 for (i
= 0; i
< seg
->length
; i
++)
1116 if (seg
->as
[i
] == asno
)
1124 /* When all of AS path is private AS return 1. */
1126 aspath_private_as_check (struct aspath
*aspath
)
1128 struct assegment
*seg
;
1130 if ( !(aspath
&& aspath
->segments
) )
1133 seg
= aspath
->segments
;
1139 for (i
= 0; i
< seg
->length
; i
++)
1141 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1149 /* Replace all private ASNs with our own ASN */
1151 aspath_replace_private_asns (struct aspath
*aspath
, as_t asn
)
1154 struct assegment
*seg
;
1156 new = aspath_dup(aspath
);
1157 seg
= new->segments
;
1163 for (i
= 0; i
< seg
->length
; i
++)
1165 if (BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1171 aspath_str_update(new);
1175 /* Remove all private ASNs */
1177 aspath_remove_private_asns (struct aspath
*aspath
)
1180 struct assegment
*seg
;
1181 struct assegment
*new_seg
;
1182 struct assegment
*last_new_seg
;
1187 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
1190 last_new_seg
= NULL
;
1191 seg
= aspath
->segments
;
1195 for (i
= 0; i
< seg
->length
; i
++)
1198 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1204 // The entire segment is private so skip it
1211 // The entire segment is public so copy it
1212 else if (public == seg
->length
)
1214 new_seg
= assegment_dup (seg
);
1217 // The segment is a mix of public and private ASNs. Copy as many spots as
1218 // there are public ASNs then come back and fill in only the public ASNs.
1221 new_seg
= assegment_new (seg
->type
, public);
1223 for (i
= 0; i
< seg
->length
; i
++)
1226 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1228 new_seg
->as
[j
] = seg
->as
[i
];
1234 // This is the first segment so set the aspath segments pointer to this one
1236 new->segments
= new_seg
;
1238 last_new_seg
->next
= new_seg
;
1240 last_new_seg
= new_seg
;
1244 aspath_str_update(new);
1248 /* AS path confed check. If aspath contains confed set or sequence then return 1. */
1250 aspath_confed_check (struct aspath
*aspath
)
1252 struct assegment
*seg
;
1254 if ( !(aspath
&& aspath
->segments
) )
1257 seg
= aspath
->segments
;
1261 if (seg
->type
== AS_CONFED_SET
|| seg
->type
== AS_CONFED_SEQUENCE
)
1268 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1269 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1271 aspath_left_confed_check (struct aspath
*aspath
)
1274 if ( !(aspath
&& aspath
->segments
) )
1277 if ( (aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1278 || (aspath
->segments
->type
== AS_CONFED_SET
) )
1284 /* Merge as1 to as2. as2 should be uninterned aspath. */
1285 static struct aspath
*
1286 aspath_merge (struct aspath
*as1
, struct aspath
*as2
)
1288 struct assegment
*last
, *new;
1293 last
= new = assegment_dup_all (as1
->segments
);
1295 /* find the last valid segment */
1296 while (last
&& last
->next
)
1299 last
->next
= as2
->segments
;
1300 as2
->segments
= new;
1301 aspath_str_update (as2
);
1305 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1307 aspath_prepend (struct aspath
*as1
, struct aspath
*as2
)
1309 struct assegment
*seg1
;
1310 struct assegment
*seg2
;
1315 seg1
= as1
->segments
;
1316 seg2
= as2
->segments
;
1318 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1321 as2
->segments
= assegment_dup_all (as1
->segments
);
1322 aspath_str_update (as2
);
1326 /* If as1 is empty AS, no prepending to do. */
1330 /* find the tail as1's segment chain. */
1331 while (seg1
&& seg1
->next
)
1334 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1335 if (seg1
->type
== AS_SEQUENCE
&& seg2
->type
== AS_CONFED_SEQUENCE
)
1336 as2
= aspath_delete_confed_seq (as2
);
1338 /* Compare last segment type of as1 and first segment type of as2. */
1339 if (seg1
->type
!= seg2
->type
)
1340 return aspath_merge (as1
, as2
);
1342 if (seg1
->type
== AS_SEQUENCE
)
1344 /* We have two chains of segments, as1->segments and seg2,
1345 * and we have to attach them together, merging the attaching
1346 * segments together into one.
1348 * 1. dupe as1->segments onto head of as2
1349 * 2. merge seg2's asns onto last segment of this new chain
1350 * 3. attach chain after seg2
1353 /* dupe as1 onto as2's head */
1354 seg1
= as2
->segments
= assegment_dup_all (as1
->segments
);
1356 /* refind the tail of as2, reusing seg1 */
1357 while (seg1
&& seg1
->next
)
1360 /* merge the old head, seg2, into tail, seg1 */
1361 seg1
= assegment_append_asns (seg1
, seg2
->as
, seg2
->length
);
1363 /* bypass the merged seg2, and attach any chain after it to
1364 * chain descending from as2's head
1366 seg1
->next
= seg2
->next
;
1368 /* seg2 is now referenceless and useless*/
1369 assegment_free (seg2
);
1371 /* we've now prepended as1's segment chain to as2, merging
1372 * the inbetween AS_SEQUENCE of seg2 in the process
1374 aspath_str_update (as2
);
1379 /* AS_SET merge code is needed at here. */
1380 return aspath_merge (as1
, as2
);
1382 /* XXX: Ermmm, what if as1 has multiple segments?? */
1387 /* Iterate over AS_PATH segments and wipe all occurences of the
1388 * listed AS numbers. Hence some segments may lose some or even
1389 * all data on the way, the operation is implemented as a smarter
1390 * version of aspath_dup(), which allocates memory to hold the new
1391 * data, not the original. The new AS path is returned.
1394 aspath_filter_exclude (struct aspath
* source
, struct aspath
* exclude_list
)
1396 struct assegment
* srcseg
, * exclseg
, * lastseg
;
1397 struct aspath
* newpath
;
1399 newpath
= aspath_new();
1402 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
)
1404 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1405 struct assegment
* newseg
;
1407 /* Find out, how much ASns are we going to pick from this segment.
1408 * We can't perform filtering right inline, because the size of
1409 * the new segment isn't known at the moment yet.
1411 for (i
= 0; i
< srcseg
->length
; i
++)
1414 for (exclseg
= exclude_list
->segments
; exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1415 for (y
= 0; y
< exclseg
->length
; y
++)
1416 if (srcseg
->as
[i
] == exclseg
->as
[y
])
1419 // There's no sense in testing the rest of exclusion list, bail out.
1425 /* newlen is now the number of ASns to copy */
1429 /* Actual copying. Allocate memory and iterate once more, performing filtering. */
1430 newseg
= assegment_new (srcseg
->type
, newlen
);
1431 for (i
= 0; i
< srcseg
->length
; i
++)
1434 for (exclseg
= exclude_list
->segments
; exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1435 for (y
= 0; y
< exclseg
->length
; y
++)
1436 if (srcseg
->as
[i
] == exclseg
->as
[y
])
1443 newseg
->as
[done
++] = srcseg
->as
[i
];
1445 /* At his point newlen must be equal to done, and both must be positive. Append
1446 * the filtered segment to the gross result. */
1448 newpath
->segments
= newseg
;
1450 lastseg
->next
= newseg
;
1453 aspath_str_update (newpath
);
1454 /* We are happy returning even an empty AS_PATH, because the administrator
1455 * might expect this very behaviour. There's a mean to avoid this, if necessary,
1456 * by having a match rule against certain AS_PATH regexps in the route-map index.
1458 aspath_free (source
);
1462 /* Add specified AS to the leftmost of aspath. */
1463 static struct aspath
*
1464 aspath_add_one_as (struct aspath
*aspath
, as_t asno
, u_char type
)
1466 struct assegment
*assegment
= aspath
->segments
;
1468 /* In case of empty aspath. */
1469 if (assegment
== NULL
|| assegment
->length
== 0)
1471 aspath
->segments
= assegment_new (type
, 1);
1472 aspath
->segments
->as
[0] = asno
;
1475 assegment_free (assegment
);
1480 if (assegment
->type
== type
)
1481 aspath
->segments
= assegment_prepend_asns (aspath
->segments
, asno
, 1);
1484 /* create new segment
1485 * push it onto head of aspath's segment chain
1487 struct assegment
*newsegment
;
1489 newsegment
= assegment_new (type
, 1);
1490 newsegment
->as
[0] = asno
;
1492 newsegment
->next
= assegment
;
1493 aspath
->segments
= newsegment
;
1499 /* Add specified AS to the leftmost of aspath. */
1501 aspath_add_seq (struct aspath
*aspath
, as_t asno
)
1503 return aspath_add_one_as (aspath
, asno
, AS_SEQUENCE
);
1506 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1507 as2's leftmost AS is same return 1. */
1509 aspath_cmp_left (const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1511 const struct assegment
*seg1
;
1512 const struct assegment
*seg2
;
1514 if (!(aspath1
&& aspath2
))
1517 /* If both paths are originated in this AS then we do want to compare MED */
1518 if (!aspath_count_hops(aspath1
) && !aspath_count_hops(aspath2
))
1521 seg1
= aspath1
->segments
;
1522 seg2
= aspath2
->segments
;
1524 /* find first non-confed segments for each */
1525 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1526 || (seg1
->type
== AS_CONFED_SET
)))
1529 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1530 || (seg2
->type
== AS_CONFED_SET
)))
1535 && (seg1
->type
== AS_SEQUENCE
) && (seg2
->type
== AS_SEQUENCE
)))
1538 if (seg1
->as
[0] == seg2
->as
[0])
1544 /* Truncate an aspath after a number of hops, and put the hops remaining
1545 * at the front of another aspath. Needed for AS4 compat.
1547 * Returned aspath is a /new/ aspath, which should either by free'd or
1548 * interned by the caller, as desired.
1551 aspath_reconcile_as4 ( struct aspath
*aspath
, struct aspath
*as4path
)
1553 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1554 struct aspath
*newpath
= NULL
, *mergedpath
;
1555 int hops
, cpasns
= 0;
1560 seg
= aspath
->segments
;
1562 /* CONFEDs should get reconciled too.. */
1563 hops
= (aspath_count_hops (aspath
) + aspath_count_confeds (aspath
))
1564 - aspath_count_hops (as4path
);
1568 if (BGP_DEBUG (as4
, AS4
))
1569 zlog_warn ("[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1570 /* Something's gone wrong. The RFC says we should now ignore AS4_PATH,
1571 * which is daft behaviour - it contains vital loop-detection
1572 * information which must have been removed from AS_PATH.
1574 hops
= aspath_count_hops (aspath
);
1578 return aspath_dup (as4path
);
1580 if ( BGP_DEBUG(as4
, AS4
))
1581 zlog_debug("[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1582 aspath
->str
, as4path
->str
);
1584 while (seg
&& hops
> 0)
1591 cpasns
= seg
->length
;
1593 case AS_CONFED_SEQUENCE
:
1594 /* Should never split a confed-sequence, if hop-count
1595 * suggests we must then something's gone wrong somewhere.
1597 * Most important goal is to preserve AS_PATHs prime function
1598 * as loop-detector, so we fudge the numbers so that the entire
1599 * confed-sequence is merged in.
1601 if (hops
< seg
->length
)
1603 if (BGP_DEBUG (as4
, AS4
))
1604 zlog_debug ("[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1605 " across 2/4 ASN boundary somewhere, broken..");
1609 cpasns
= MIN(seg
->length
, hops
);
1610 hops
-= seg
->length
;
1613 assert (cpasns
<= seg
->length
);
1615 newseg
= assegment_new (seg
->type
, 0);
1616 newseg
= assegment_append_asns (newseg
, seg
->as
, cpasns
);
1620 newpath
= aspath_new ();
1621 newpath
->segments
= newseg
;
1624 prevseg
->next
= newseg
;
1630 /* We may be able to join some segments here, and we must
1631 * do this because... we want normalised aspaths in out hash
1632 * and we do not want to stumble in aspath_put.
1634 mergedpath
= aspath_merge (newpath
, aspath_dup(as4path
));
1635 aspath_free (newpath
);
1636 mergedpath
->segments
= assegment_normalise (mergedpath
->segments
);
1637 aspath_str_update (mergedpath
);
1639 if ( BGP_DEBUG(as4
, AS4
))
1640 zlog_debug ("[AS4] result of synthesizing is %s",
1646 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1647 as2's leftmost AS is same return 1. (confederation as-path
1650 aspath_cmp_left_confed (const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1652 if (! (aspath1
&& aspath2
) )
1655 if ( !(aspath1
->segments
&& aspath2
->segments
) )
1658 if ( (aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1659 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
) )
1662 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1668 /* Delete all leading AS_CONFED_SEQUENCE/SET segments from aspath.
1669 * See RFC3065, 6.1 c1 */
1671 aspath_delete_confed_seq (struct aspath
*aspath
)
1673 struct assegment
*seg
;
1675 if (!(aspath
&& aspath
->segments
))
1678 seg
= aspath
->segments
;
1680 /* "if the first path segment of the AS_PATH is
1681 * of type AS_CONFED_SEQUENCE,"
1683 if (aspath
->segments
->type
!= AS_CONFED_SEQUENCE
)
1686 /* "... that segment and any immediately following segments
1687 * of the type AS_CONFED_SET or AS_CONFED_SEQUENCE are removed
1688 * from the AS_PATH attribute,"
1691 (seg
->type
== AS_CONFED_SEQUENCE
|| seg
->type
== AS_CONFED_SET
))
1693 aspath
->segments
= seg
->next
;
1694 assegment_free (seg
);
1695 seg
= aspath
->segments
;
1697 aspath_str_update (aspath
);
1701 /* Add new AS number to the leftmost part of the aspath as
1702 AS_CONFED_SEQUENCE. */
1704 aspath_add_confed_seq (struct aspath
*aspath
, as_t asno
)
1706 return aspath_add_one_as (aspath
, asno
, AS_CONFED_SEQUENCE
);
1709 /* Add new as value to as path structure. */
1711 aspath_as_add (struct aspath
*as
, as_t asno
)
1713 struct assegment
*seg
= as
->segments
;
1718 /* Last segment search procedure. */
1722 assegment_append_asns (seg
, &asno
, 1);
1725 /* Add new as segment to the as path. */
1727 aspath_segment_add (struct aspath
*as
, int type
)
1729 struct assegment
*seg
= as
->segments
;
1730 struct assegment
*new = assegment_new (type
, 0);
1745 return aspath_parse (NULL
, 0, 1); /* 32Bit ;-) */
1749 aspath_empty_get (void)
1751 struct aspath
*aspath
;
1753 aspath
= aspath_new ();
1754 aspath_make_str_count (aspath
);
1761 return ashash
->count
;
1765 Theoretically, one as path can have:
1767 One BGP packet size should be less than 4096.
1768 One BGP attribute size should be less than 4096 - BGP header size.
1769 One BGP aspath size should be less than 4096 - BGP header size -
1770 BGP mandantry attribute size.
1773 /* AS path string lexical token enum. */
1779 as_token_confed_seq_start
,
1780 as_token_confed_seq_end
,
1781 as_token_confed_set_start
,
1782 as_token_confed_set_end
,
1786 /* Return next token and point for string parse. */
1788 aspath_gettoken (const char *buf
, enum as_token
*token
, u_long
*asno
)
1790 const char *p
= buf
;
1792 /* Skip seperators (space for sequences, ',' for sets). */
1793 while (isspace ((int) *p
) || *p
== ',')
1796 /* Check the end of the string and type specify characters
1803 *token
= as_token_set_start
;
1807 *token
= as_token_set_end
;
1811 *token
= as_token_confed_seq_start
;
1815 *token
= as_token_confed_seq_end
;
1819 *token
= as_token_confed_set_start
;
1823 *token
= as_token_confed_set_end
;
1828 /* Check actual AS value. */
1829 if (isdigit ((int) *p
))
1833 *token
= as_token_asval
;
1837 while (isdigit ((int) *p
))
1840 asval
+= (*p
- '0');
1847 /* There is no match then return unknown token. */
1848 *token
= as_token_unknown
;
1853 aspath_str2aspath (const char *str
)
1855 enum as_token token
= as_token_unknown
;
1858 struct aspath
*aspath
;
1861 aspath
= aspath_new ();
1863 /* We start default type as AS_SEQUENCE. */
1864 as_type
= AS_SEQUENCE
;
1867 while ((str
= aspath_gettoken (str
, &token
, &asno
)) != NULL
)
1871 case as_token_asval
:
1874 aspath_segment_add (aspath
, as_type
);
1877 aspath_as_add (aspath
, asno
);
1879 case as_token_set_start
:
1881 aspath_segment_add (aspath
, as_type
);
1884 case as_token_set_end
:
1885 as_type
= AS_SEQUENCE
;
1888 case as_token_confed_seq_start
:
1889 as_type
= AS_CONFED_SEQUENCE
;
1890 aspath_segment_add (aspath
, as_type
);
1893 case as_token_confed_seq_end
:
1894 as_type
= AS_SEQUENCE
;
1897 case as_token_confed_set_start
:
1898 as_type
= AS_CONFED_SET
;
1899 aspath_segment_add (aspath
, as_type
);
1902 case as_token_confed_set_end
:
1903 as_type
= AS_SEQUENCE
;
1906 case as_token_unknown
:
1908 aspath_free (aspath
);
1913 aspath_make_str_count (aspath
);
1918 /* Make hash value by raw aspath data. */
1920 aspath_key_make (void *p
)
1922 struct aspath
*aspath
= (struct aspath
*) p
;
1923 unsigned int key
= 0;
1926 aspath_str_update (aspath
);
1928 key
= jhash (aspath
->str
, aspath
->str_len
, 2334325);
1933 /* If two aspath have same value then return 1 else return 0 */
1935 aspath_cmp (const void *arg1
, const void *arg2
)
1937 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
1938 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
1940 while (seg1
|| seg2
)
1943 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
1945 if (seg1
->type
!= seg2
->type
)
1947 if (seg1
->length
!= seg2
->length
)
1949 for (i
= 0; i
< seg1
->length
; i
++)
1950 if (seg1
->as
[i
] != seg2
->as
[i
])
1958 /* AS path hash initialize. */
1962 ashash
= hash_create_size (32768, aspath_key_make
, aspath_cmp
);
1966 aspath_finish (void)
1972 stream_free (snmp_stream
);
1975 /* return and as path value */
1977 aspath_print (struct aspath
*as
)
1979 return (as
? as
->str
: NULL
);
1982 /* Printing functions */
1983 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
1984 * AS_PATH wasn't empty.
1987 aspath_print_vty (struct vty
*vty
, const char *format
, struct aspath
*as
, const char * suffix
)
1990 vty_out (vty
, format
, as
->str
);
1991 if (as
->str_len
&& strlen (suffix
))
1992 vty_out (vty
, "%s", suffix
);
1996 aspath_show_all_iterator (struct hash_backet
*backet
, struct vty
*vty
)
2000 as
= (struct aspath
*) backet
->data
;
2002 vty_out (vty
, "[%p:%u] (%ld) ", backet
, backet
->key
, as
->refcnt
);
2003 vty_out (vty
, "%s%s", as
->str
, VTY_NEWLINE
);
2006 /* Print all aspath and hash information. This function is used from
2007 `show ip bgp paths' command. */
2009 aspath_print_all_vty (struct vty
*vty
)
2011 hash_iterate (ashash
,
2012 (void (*) (struct hash_backet
*, void *))
2013 aspath_show_all_iterator
,