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. */
91 /* Stream for SNMP. See aspath_snmp_pathseg */
92 static struct stream
*snmp_stream
;
95 assegment_data_new (int num
)
97 return (XCALLOC (MTYPE_AS_SEG_DATA
, ASSEGMENT_DATA_SIZE (num
, 1)));
101 assegment_data_free (as_t
*asdata
)
103 XFREE (MTYPE_AS_SEG_DATA
,asdata
);
106 /* Get a new segment. Note that 0 is an allowed length,
107 * and will result in a segment with no allocated data segment.
108 * the caller should immediately assign data to the segment, as the segment
109 * otherwise is not generally valid
111 static struct assegment
*
112 assegment_new (u_char type
, u_short length
)
114 struct assegment
*new;
116 new = XCALLOC (MTYPE_AS_SEG
, sizeof (struct assegment
));
119 new->as
= assegment_data_new (length
);
121 new->length
= length
;
128 assegment_free (struct assegment
*seg
)
134 XFREE (MTYPE_AS_SEG_DATA
, seg
->as
);
135 memset (seg
, 0xfe, sizeof(struct assegment
));
136 XFREE (MTYPE_AS_SEG
, seg
);
141 /* free entire chain of segments */
143 assegment_free_all (struct assegment
*seg
)
145 struct assegment
*prev
;
151 assegment_free (prev
);
155 /* Duplicate just the given assegment and its data */
156 static struct assegment
*
157 assegment_dup (struct assegment
*seg
)
159 struct assegment
*new;
161 new = assegment_new (seg
->type
, seg
->length
);
162 memcpy (new->as
, seg
->as
, ASSEGMENT_DATA_SIZE (new->length
, 1) );
167 /* Duplicate entire chain of assegments, return the head */
168 static struct assegment
*
169 assegment_dup_all (struct assegment
*seg
)
171 struct assegment
*new = NULL
;
172 struct assegment
*head
= NULL
;
178 new->next
= assegment_dup (seg
);
182 head
= new = assegment_dup (seg
);
189 /* prepend the as number to given segment, given num of times */
190 static struct assegment
*
191 assegment_prepend_asns (struct assegment
*seg
, as_t asnum
, int num
)
198 if (num
>= AS_SEGMENT_MAX
)
199 return seg
; /* we don't do huge prepends */
201 newas
= assegment_data_new (seg
->length
+ num
);
206 for (i
= 0; i
< num
; i
++)
209 memcpy (newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE (seg
->length
, 1));
210 XFREE (MTYPE_AS_SEG_DATA
, seg
->as
);
216 assegment_free_all (seg
);
220 /* append given array of as numbers to the segment */
221 static struct assegment
*
222 assegment_append_asns (struct assegment
*seg
, as_t
*asnos
, int num
)
226 newas
= XREALLOC (MTYPE_AS_SEG_DATA
, seg
->as
,
227 ASSEGMENT_DATA_SIZE (seg
->length
+ num
, 1));
232 memcpy (seg
->as
+ seg
->length
, asnos
, ASSEGMENT_DATA_SIZE(num
, 1));
237 assegment_free_all (seg
);
242 int_cmp (const void *p1
, const void *p2
)
244 const as_t
*as1
= p1
;
245 const as_t
*as2
= p2
;
247 return (*as1
== *as2
)
248 ? 0 : ( (*as1
> *as2
) ? 1 : -1);
251 /* normalise the segment.
252 * In particular, merge runs of AS_SEQUENCEs into one segment
253 * Internally, we do not care about the wire segment length limit, and
254 * we want each distinct AS_PATHs to have the exact same internal
255 * representation - eg, so that our hashing actually works..
257 static struct assegment
*
258 assegment_normalise (struct assegment
*head
)
260 struct assegment
*seg
= head
, *pin
;
261 struct assegment
*tmp
;
270 /* Sort values SET segments, for determinism in paths to aid
271 * creation of hash values / path comparisons
272 * and because it helps other lesser implementations ;)
274 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
)
279 qsort (seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
282 for (i
=1; i
< seg
->length
; i
++)
284 if (seg
->as
[tail
] == seg
->as
[i
])
289 seg
->as
[tail
] = seg
->as
[i
];
291 /* seg->length can be 0.. */
293 seg
->length
= tail
+ 1;
296 /* read ahead from the current, pinned segment while the segments
297 * are packable/mergeable. Append all following packable segments
298 * to the segment we have pinned and remove these appended
301 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
))
306 /* append the next sequence to the pinned sequence */
307 pin
= assegment_append_asns (pin
, seg
->as
, seg
->length
);
309 /* bypass the next sequence */
310 pin
->next
= seg
->next
;
312 /* get rid of the now referenceless segment */
313 assegment_free (tmp
);
322 static struct aspath
*
325 return XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
328 /* Free AS path structure. */
330 aspath_free (struct aspath
*aspath
)
334 if (aspath
->segments
)
335 assegment_free_all (aspath
->segments
);
337 XFREE (MTYPE_AS_STR
, aspath
->str
);
338 XFREE (MTYPE_AS_PATH
, aspath
);
341 /* Unintern aspath from AS path bucket. */
343 aspath_unintern (struct aspath
*aspath
)
350 if (aspath
->refcnt
== 0)
352 /* This aspath must exist in aspath hash table. */
353 ret
= hash_release (ashash
, aspath
);
354 assert (ret
!= NULL
);
355 aspath_free (aspath
);
359 /* Return the start or end delimiters for a particular Segment type */
360 #define AS_SEG_START 0
363 aspath_delimiter_char (u_char type
, u_char which
)
371 } aspath_delim_char
[] =
373 { AS_SET
, '{', '}' },
374 { AS_CONFED_SET
, '[', ']' },
375 { AS_CONFED_SEQUENCE
, '(', ')' },
379 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++)
381 if (aspath_delim_char
[i
].type
== type
)
383 if (which
== AS_SEG_START
)
384 return aspath_delim_char
[i
].start
;
385 else if (which
== AS_SEG_END
)
386 return aspath_delim_char
[i
].end
;
392 /* countup asns from this segment and index onward */
394 assegment_count_asns (struct assegment
*seg
, int from
)
400 count
+= seg
->length
;
403 count
+= (seg
->length
- from
);
412 aspath_count_confeds (struct aspath
*aspath
)
415 struct assegment
*seg
= aspath
->segments
;
419 if (seg
->type
== AS_CONFED_SEQUENCE
)
420 count
+= seg
->length
;
421 else if (seg
->type
== AS_CONFED_SET
)
430 aspath_count_hops (struct aspath
*aspath
)
433 struct assegment
*seg
= aspath
->segments
;
437 if (seg
->type
== AS_SEQUENCE
)
438 count
+= seg
->length
;
439 else if (seg
->type
== AS_SET
)
447 /* Estimate size aspath /might/ take if encoded into an
450 * This is a quick estimate, not definitive! aspath_put()
451 * may return a different number!!
454 aspath_size (struct aspath
*aspath
)
457 struct assegment
*seg
= aspath
->segments
;
461 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
467 /* Return highest public ASN in path */
469 aspath_highest (struct aspath
*aspath
)
471 struct assegment
*seg
= aspath
->segments
;
477 for (i
= 0; i
< seg
->length
; i
++)
478 if (seg
->as
[i
] > highest
479 && (seg
->as
[i
] < BGP_PRIVATE_AS_MIN
480 || seg
->as
[i
] > BGP_PRIVATE_AS_MAX
))
481 highest
= seg
->as
[i
];
487 /* Return 1 if there are any 4-byte ASes in the path */
489 aspath_has_as4 (struct aspath
*aspath
)
491 struct assegment
*seg
= aspath
->segments
;
496 for (i
= 0; i
< seg
->length
; i
++)
497 if (seg
->as
[i
] > BGP_AS_MAX
)
504 /* Return number of as numbers in in path */
506 aspath_count_numas (struct aspath
*aspath
)
508 struct assegment
*seg
= aspath
->segments
;
520 /* Convert aspath structure to string expression. */
522 aspath_make_str_count (struct aspath
*as
)
524 struct assegment
*seg
;
532 str_buf
= XMALLOC (MTYPE_AS_STR
, 1);
539 /* ASN takes 5 to 10 chars plus seperator, see below.
540 * If there is one differing segment type, we need an additional
541 * 2 chars for segment delimiters, and the final '\0'.
542 * Hopefully this is large enough to avoid hitting the realloc
543 * code below for most common sequences.
545 * This was changed to 10 after the well-known BGP assertion, which
546 * had hit some parts of the Internet in May of 2009.
548 #define ASN_STR_LEN (10 + 1)
549 str_size
= MAX (assegment_count_asns (seg
, 0) * ASN_STR_LEN
+ 2 + 1,
550 ASPATH_STR_DEFAULT_LEN
);
551 str_buf
= XMALLOC (MTYPE_AS_STR
, str_size
);
558 /* Check AS type validity. Set seperator for segment */
566 case AS_CONFED_SEQUENCE
:
570 XFREE (MTYPE_AS_STR
, str_buf
);
574 /* We might need to increase str_buf, particularly if path has
575 * differing segments types, our initial guesstimate above will
576 * have been wrong. Need 10 chars for ASN, a seperator each and
577 * potentially two segment delimiters, plus a space between each
578 * segment and trailing zero.
580 * This definitely didn't work with the value of 5 bytes and
583 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
584 if ( (len
+ SEGMENT_STR_LEN(seg
)) > str_size
)
586 str_size
= len
+ SEGMENT_STR_LEN(seg
);
587 str_buf
= XREALLOC (MTYPE_AS_STR
, str_buf
, str_size
);
590 #undef SEGMENT_STR_LEN
592 if (seg
->type
!= AS_SEQUENCE
)
593 len
+= snprintf (str_buf
+ len
, str_size
- len
,
595 aspath_delimiter_char (seg
->type
, AS_SEG_START
));
597 /* write out the ASNs, with their seperators, bar the last one*/
598 for (i
= 0; i
< seg
->length
; i
++)
600 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%u", seg
->as
[i
]);
602 if (i
< (seg
->length
- 1))
603 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c", seperator
);
606 if (seg
->type
!= AS_SEQUENCE
)
607 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c",
608 aspath_delimiter_char (seg
->type
, AS_SEG_END
));
610 len
+= snprintf (str_buf
+ len
, str_size
- len
, " ");
615 assert (len
< str_size
);
623 aspath_str_update (struct aspath
*as
)
626 XFREE (MTYPE_AS_STR
, as
->str
);
627 as
->str
= aspath_make_str_count (as
);
630 /* Intern allocated AS path. */
632 aspath_intern (struct aspath
*aspath
)
636 /* Assert this AS path structure is not interned. */
637 assert (aspath
->refcnt
== 0);
639 /* Check AS path hash. */
640 find
= hash_get (ashash
, aspath
, hash_alloc_intern
);
643 aspath_free (aspath
);
648 find
->str
= aspath_make_str_count (find
);
653 /* Duplicate aspath structure. Created same aspath structure but
654 reference count and AS path string is cleared. */
656 aspath_dup (struct aspath
*aspath
)
660 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
662 if (aspath
->segments
)
663 new->segments
= assegment_dup_all (aspath
->segments
);
665 new->segments
= NULL
;
667 new->str
= aspath_make_str_count (aspath
);
673 aspath_hash_alloc (void *arg
)
675 struct aspath
*aspath
;
677 /* New aspath structure is needed. */
678 aspath
= aspath_dup (arg
);
680 /* Malformed AS path value. */
683 aspath_free (aspath
);
690 /* parse as-segment byte stream in struct assegment */
691 static struct assegment
*
692 assegments_parse (struct stream
*s
, size_t length
, int use32bit
)
694 struct assegment_header segh
;
695 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
698 /* empty aspath (ie iBGP or somesuch) */
702 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
703 zlog_debug ("[AS4SEG] Parse aspath segment: got total byte length %lu",
704 (unsigned long) length
);
706 if ( (STREAM_READABLE(s
) < length
)
707 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
708 || (length
% AS16_VALUE_SIZE
))
711 while ( (STREAM_READABLE(s
) > AS_HEADER_SIZE
)
717 /* softly softly, get the header first on its own */
718 segh
.type
= stream_getc (s
);
719 segh
.length
= stream_getc (s
);
721 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
723 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
724 zlog_debug ("[AS4SEG] Parse aspath segment: got type %d, length %d",
725 segh
.type
, segh
.length
);
728 if ( ((bytes
+ seg_size
) > length
)
729 /* 1771bis 4.3b: seg length contains one or more */
730 || (segh
.length
== 0)
731 /* Paranoia in case someone changes type of segment length */
732 || ((sizeof segh
.length
> 1) && (segh
.length
> AS_SEGMENT_MAX
)) )
735 assegment_free_all (head
);
739 /* now its safe to trust lengths */
740 seg
= assegment_new (segh
.type
, segh
.length
);
744 else /* it's the first segment */
747 for (i
= 0; i
< segh
.length
; i
++)
748 seg
->as
[i
] = (use32bit
) ? stream_getl (s
) : stream_getw (s
);
752 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
753 zlog_debug ("[AS4SEG] Parse aspath segment: Bytes now: %lu",
754 (unsigned long) bytes
);
759 return assegment_normalise (head
);
762 /* AS path parse function. pnt is a pointer to byte stream and length
763 is length of byte stream. If there is same AS path in the the AS
764 path hash then return it else make new AS path structure. */
766 aspath_parse (struct stream
*s
, size_t length
, int use32bit
)
771 /* If length is odd it's malformed AS path. */
772 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
773 * otherwise its malformed when length is larger than 2 and (length-2)
774 * is not dividable by 4.
775 * But... this time we're lazy
777 if (length
% AS16_VALUE_SIZE
)
780 memset (&as
, 0, sizeof (struct aspath
));
781 as
.segments
= assegments_parse (s
, length
, use32bit
);
783 /* If already same aspath exist then return it. */
784 find
= hash_get (ashash
, &as
, aspath_hash_alloc
);
786 /* aspath_hash_alloc dupes segments too. that probably could be
789 assegment_free_all (as
.segments
);
791 XFREE (MTYPE_AS_STR
, as
.str
);
801 assegment_data_put (struct stream
*s
, as_t
*as
, int num
, int use32bit
)
804 assert (num
<= AS_SEGMENT_MAX
);
806 for (i
= 0; i
< num
; i
++)
808 stream_putl (s
, as
[i
]);
811 if ( as
[i
] <= BGP_AS_MAX
)
812 stream_putw(s
, as
[i
]);
814 stream_putw(s
, BGP_AS_TRANS
);
819 assegment_header_put (struct stream
*s
, u_char type
, int length
)
822 assert (length
<= AS_SEGMENT_MAX
);
823 stream_putc (s
, type
);
824 lenp
= stream_get_endp (s
);
825 stream_putc (s
, length
);
829 /* write aspath data to stream */
831 aspath_put (struct stream
*s
, struct aspath
*as
, int use32bit
)
833 struct assegment
*seg
= as
->segments
;
836 if (!seg
|| seg
->length
== 0)
842 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
843 * At the moment, we would write out a partial aspath, and our peer
844 * will complain and drop the session :-/
846 * The general assumption here is that many things tested will
847 * never happen. And, in real live, up to now, they have not.
849 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
) <= STREAM_WRITEABLE(s
)))
851 struct assegment
*next
= seg
->next
;
856 /* Overlength segments have to be split up */
857 while ( (seg
->length
- written
) > AS_SEGMENT_MAX
)
859 assegment_header_put (s
, seg
->type
, AS_SEGMENT_MAX
);
860 assegment_data_put (s
, seg
->as
, AS_SEGMENT_MAX
, use32bit
);
861 written
+= AS_SEGMENT_MAX
;
862 bytes
+= ASSEGMENT_SIZE (written
, use32bit
);
865 /* write the final segment, probably is also the first */
866 lenp
= assegment_header_put (s
, seg
->type
, seg
->length
- written
);
867 assegment_data_put (s
, (seg
->as
+ written
), seg
->length
- written
,
870 /* Sequence-type segments can be 'packed' together
871 * Case of a segment which was overlength and split up
872 * will be missed here, but that doesn't matter.
874 while (next
&& ASSEGMENTS_PACKABLE (seg
, next
))
876 /* NB: We should never normally get here given we
877 * normalise aspath data when parse them. However, better
878 * safe than sorry. We potentially could call
879 * assegment_normalise here instead, but it's cheaper and
880 * easier to do it on the fly here rather than go through
881 * the segment list twice every time we write out
885 /* Next segment's data can fit in this one */
886 assegment_data_put (s
, next
->as
, next
->length
, use32bit
);
888 /* update the length of the segment header */
889 stream_putc_at (s
, lenp
, seg
->length
- written
+ next
->length
);
890 asns_packed
+= next
->length
;
895 bytes
+= ASSEGMENT_SIZE (seg
->length
- written
+ asns_packed
,
903 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
904 * We have no way to manage the storage, so we use a static stream
905 * wrapper around aspath_put.
908 aspath_snmp_pathseg (struct aspath
*as
, size_t *varlen
)
910 #define SNMP_PATHSEG_MAX 1024
913 snmp_stream
= stream_new (SNMP_PATHSEG_MAX
);
915 stream_reset (snmp_stream
);
922 aspath_put (snmp_stream
, as
, 0); /* use 16 bit for now here */
924 *varlen
= stream_get_endp (snmp_stream
);
925 return stream_pnt(snmp_stream
);
928 #define min(A,B) ((A) < (B) ? (A) : (B))
930 static struct assegment
*
931 aspath_aggregate_as_set_add (struct aspath
*aspath
, struct assegment
*asset
,
936 /* If this is first AS set member, create new as-set segment. */
939 asset
= assegment_new (AS_SET
, 1);
940 if (! aspath
->segments
)
941 aspath
->segments
= asset
;
944 struct assegment
*seg
= aspath
->segments
;
949 asset
->type
= AS_SET
;
955 /* Check this AS value already exists or not. */
956 for (i
= 0; i
< asset
->length
; i
++)
957 if (asset
->as
[i
] == as
)
961 asset
->as
= XREALLOC (MTYPE_AS_SEG_DATA
, asset
->as
,
962 asset
->length
* AS_VALUE_SIZE
);
963 asset
->as
[asset
->length
- 1] = as
;
970 /* Modify as1 using as2 for aggregation. */
972 aspath_aggregate (struct aspath
*as1
, struct aspath
*as2
)
978 struct assegment
*seg1
= as1
->segments
;
979 struct assegment
*seg2
= as2
->segments
;
980 struct aspath
*aspath
= NULL
;
981 struct assegment
*asset
;
982 struct assegment
*prevseg
= NULL
;
989 /* First of all check common leading sequence. */
992 /* Check segment type. */
993 if (seg1
->type
!= seg2
->type
)
996 /* Minimum segment length. */
997 minlen
= min (seg1
->length
, seg2
->length
);
999 for (match
= 0; match
< minlen
; match
++)
1000 if (seg1
->as
[match
] != seg2
->as
[match
])
1005 struct assegment
*seg
= assegment_new (seg1
->type
, 0);
1007 seg
= assegment_append_asns (seg
, seg1
->as
, match
);
1011 aspath
= aspath_new ();
1012 aspath
->segments
= seg
;
1015 prevseg
->next
= seg
;
1020 if (match
!= minlen
|| match
!= seg1
->length
1021 || seg1
->length
!= seg2
->length
)
1029 aspath
= aspath_new();
1031 /* Make as-set using rest of all information. */
1035 for (i
= from
; i
< seg1
->length
; i
++)
1036 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg1
->as
[i
]);
1045 for (i
= from
; i
< seg2
->length
; i
++)
1046 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg2
->as
[i
]);
1052 assegment_normalise (aspath
->segments
);
1053 aspath_str_update (aspath
);
1057 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1058 attribute, check the leftmost AS number in the AS_PATH attribute is
1059 or not the peer's AS number. */
1061 aspath_firstas_check (struct aspath
*aspath
, as_t asno
)
1063 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
1066 if (aspath
->segments
1067 && (aspath
->segments
->type
== AS_SEQUENCE
)
1068 && (aspath
->segments
->as
[0] == asno
))
1074 /* AS path loop check. If aspath contains asno then return >= 1. */
1076 aspath_loop_check (struct aspath
*aspath
, as_t asno
)
1078 struct assegment
*seg
;
1081 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
1084 seg
= aspath
->segments
;
1090 for (i
= 0; i
< seg
->length
; i
++)
1091 if (seg
->as
[i
] == asno
)
1099 /* When all of AS path is private AS return 1. */
1101 aspath_private_as_check (struct aspath
*aspath
)
1103 struct assegment
*seg
;
1105 if ( !(aspath
&& aspath
->segments
) )
1108 seg
= aspath
->segments
;
1114 for (i
= 0; i
< seg
->length
; i
++)
1116 if ( (seg
->as
[i
] < BGP_PRIVATE_AS_MIN
)
1117 || (seg
->as
[i
] > BGP_PRIVATE_AS_MAX
) )
1125 /* Merge as1 to as2. as2 should be uninterned aspath. */
1126 static struct aspath
*
1127 aspath_merge (struct aspath
*as1
, struct aspath
*as2
)
1129 struct assegment
*last
, *new;
1134 last
= new = assegment_dup_all (as1
->segments
);
1136 /* find the last valid segment */
1137 while (last
&& last
->next
)
1140 last
->next
= as2
->segments
;
1141 as2
->segments
= new;
1142 aspath_str_update (as2
);
1146 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1148 aspath_prepend (struct aspath
*as1
, struct aspath
*as2
)
1150 struct assegment
*seg1
;
1151 struct assegment
*seg2
;
1156 seg1
= as1
->segments
;
1157 seg2
= as2
->segments
;
1159 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1162 as2
->segments
= assegment_dup_all (as1
->segments
);
1163 aspath_str_update (as2
);
1167 /* If as1 is empty AS, no prepending to do. */
1171 /* find the tail as1's segment chain. */
1172 while (seg1
&& seg1
->next
)
1175 /* Compare last segment type of as1 and first segment type of as2. */
1176 if (seg1
->type
!= seg2
->type
)
1177 return aspath_merge (as1
, as2
);
1179 if (seg1
->type
== AS_SEQUENCE
)
1181 /* We have two chains of segments, as1->segments and seg2,
1182 * and we have to attach them together, merging the attaching
1183 * segments together into one.
1185 * 1. dupe as1->segments onto head of as2
1186 * 2. merge seg2's asns onto last segment of this new chain
1187 * 3. attach chain after seg2
1190 /* dupe as1 onto as2's head */
1191 seg1
= as2
->segments
= assegment_dup_all (as1
->segments
);
1193 /* refind the tail of as2, reusing seg1 */
1194 while (seg1
&& seg1
->next
)
1197 /* merge the old head, seg2, into tail, seg1 */
1198 seg1
= assegment_append_asns (seg1
, seg2
->as
, seg2
->length
);
1200 /* bypass the merged seg2, and attach any chain after it to
1201 * chain descending from as2's head
1203 seg1
->next
= seg2
->next
;
1205 /* seg2 is now referenceless and useless*/
1206 assegment_free (seg2
);
1208 /* we've now prepended as1's segment chain to as2, merging
1209 * the inbetween AS_SEQUENCE of seg2 in the process
1211 aspath_str_update (as2
);
1216 /* AS_SET merge code is needed at here. */
1217 return aspath_merge (as1
, as2
);
1219 /* XXX: Ermmm, what if as1 has multiple segments?? */
1224 /* Iterate over AS_PATH segments and wipe all occurences of the
1225 * listed AS numbers. Hence some segments may lose some or even
1226 * all data on the way, the operation is implemented as a smarter
1227 * version of aspath_dup(), which allocates memory to hold the new
1228 * data, not the original. The new AS path is returned.
1231 aspath_filter_exclude (struct aspath
* source
, struct aspath
* exclude_list
)
1233 struct assegment
* srcseg
, * exclseg
, * lastseg
;
1234 struct aspath
* newpath
;
1236 newpath
= aspath_new();
1239 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
)
1241 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1242 struct assegment
* newseg
;
1244 /* Find out, how much ASns are we going to pick from this segment.
1245 * We can't perform filtering right inline, because the size of
1246 * the new segment isn't known at the moment yet.
1248 for (i
= 0; i
< srcseg
->length
; i
++)
1251 for (exclseg
= exclude_list
->segments
; exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1252 for (y
= 0; y
< exclseg
->length
; y
++)
1253 if (srcseg
->as
[i
] == exclseg
->as
[y
])
1256 // There's no sense in testing the rest of exclusion list, bail out.
1262 /* newlen is now the number of ASns to copy */
1266 /* Actual copying. Allocate memory and iterate once more, performing filtering. */
1267 newseg
= assegment_new (srcseg
->type
, newlen
);
1268 for (i
= 0; i
< srcseg
->length
; i
++)
1271 for (exclseg
= exclude_list
->segments
; exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1272 for (y
= 0; y
< exclseg
->length
; y
++)
1273 if (srcseg
->as
[i
] == exclseg
->as
[y
])
1280 newseg
->as
[done
++] = srcseg
->as
[i
];
1282 /* At his point newlen must be equal to done, and both must be positive. Append
1283 * the filtered segment to the gross result. */
1285 newpath
->segments
= newseg
;
1287 lastseg
->next
= newseg
;
1290 aspath_str_update (newpath
);
1291 /* We are happy returning even an empty AS_PATH, because the administrator
1292 * might expect this very behaviour. There's a mean to avoid this, if necessary,
1293 * by having a match rule against certain AS_PATH regexps in the route-map index.
1295 aspath_free (source
);
1299 /* Add specified AS to the leftmost of aspath. */
1300 static struct aspath
*
1301 aspath_add_one_as (struct aspath
*aspath
, as_t asno
, u_char type
)
1303 struct assegment
*assegment
= aspath
->segments
;
1305 /* In case of empty aspath. */
1306 if (assegment
== NULL
|| assegment
->length
== 0)
1308 aspath
->segments
= assegment_new (type
, 1);
1309 aspath
->segments
->as
[0] = asno
;
1312 assegment_free (assegment
);
1317 if (assegment
->type
== type
)
1318 aspath
->segments
= assegment_prepend_asns (aspath
->segments
, asno
, 1);
1321 /* create new segment
1322 * push it onto head of aspath's segment chain
1324 struct assegment
*newsegment
;
1326 newsegment
= assegment_new (type
, 1);
1327 newsegment
->as
[0] = asno
;
1329 newsegment
->next
= assegment
;
1330 aspath
->segments
= newsegment
;
1336 /* Add specified AS to the leftmost of aspath. */
1338 aspath_add_seq (struct aspath
*aspath
, as_t asno
)
1340 return aspath_add_one_as (aspath
, asno
, AS_SEQUENCE
);
1343 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1344 as2's leftmost AS is same return 1. */
1346 aspath_cmp_left (const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1348 const struct assegment
*seg1
= NULL
;
1349 const struct assegment
*seg2
= NULL
;
1351 if (!(aspath1
&& aspath2
))
1354 seg1
= aspath1
->segments
;
1355 seg2
= aspath2
->segments
;
1357 /* find first non-confed segments for each */
1358 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1359 || (seg1
->type
== AS_CONFED_SET
)))
1362 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1363 || (seg2
->type
== AS_CONFED_SET
)))
1368 && (seg1
->type
== AS_SEQUENCE
) && (seg2
->type
== AS_SEQUENCE
)))
1371 if (seg1
->as
[0] == seg2
->as
[0])
1377 /* Truncate an aspath after a number of hops, and put the hops remaining
1378 * at the front of another aspath. Needed for AS4 compat.
1380 * Returned aspath is a /new/ aspath, which should either by free'd or
1381 * interned by the caller, as desired.
1384 aspath_reconcile_as4 ( struct aspath
*aspath
, struct aspath
*as4path
)
1386 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1387 struct aspath
*newpath
= NULL
, *mergedpath
;
1388 int hops
, cpasns
= 0;
1393 seg
= aspath
->segments
;
1395 /* CONFEDs should get reconciled too.. */
1396 hops
= (aspath_count_hops (aspath
) + aspath_count_confeds (aspath
))
1397 - aspath_count_hops (as4path
);
1401 if (BGP_DEBUG (as4
, AS4
))
1402 zlog_warn ("[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1403 /* Something's gone wrong. The RFC says we should now ignore AS4_PATH,
1404 * which is daft behaviour - it contains vital loop-detection
1405 * information which must have been removed from AS_PATH.
1407 hops
= aspath_count_hops (aspath
);
1411 return aspath_dup (as4path
);
1413 if ( BGP_DEBUG(as4
, AS4
))
1414 zlog_debug("[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1415 aspath
->str
, as4path
->str
);
1417 while (seg
&& hops
> 0)
1424 cpasns
= seg
->length
;
1426 case AS_CONFED_SEQUENCE
:
1427 /* Should never split a confed-sequence, if hop-count
1428 * suggests we must then something's gone wrong somewhere.
1430 * Most important goal is to preserve AS_PATHs prime function
1431 * as loop-detector, so we fudge the numbers so that the entire
1432 * confed-sequence is merged in.
1434 if (hops
< seg
->length
)
1436 if (BGP_DEBUG (as4
, AS4
))
1437 zlog_debug ("[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1438 " across 2/4 ASN boundary somewhere, broken..");
1442 cpasns
= MIN(seg
->length
, hops
);
1443 hops
-= seg
->length
;
1446 assert (cpasns
<= seg
->length
);
1448 newseg
= assegment_new (seg
->type
, 0);
1449 newseg
= assegment_append_asns (newseg
, seg
->as
, cpasns
);
1453 newpath
= aspath_new ();
1454 newpath
->segments
= newseg
;
1457 prevseg
->next
= newseg
;
1463 /* We may be able to join some segments here, and we must
1464 * do this because... we want normalised aspaths in out hash
1465 * and we do not want to stumble in aspath_put.
1467 mergedpath
= aspath_merge (newpath
, aspath_dup(as4path
));
1468 aspath_free (newpath
);
1469 mergedpath
->segments
= assegment_normalise (mergedpath
->segments
);
1470 aspath_str_update (mergedpath
);
1472 if ( BGP_DEBUG(as4
, AS4
))
1473 zlog_debug ("[AS4] result of synthesizing is %s",
1479 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1480 as2's leftmost AS is same return 1. (confederation as-path
1483 aspath_cmp_left_confed (const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1485 if (! (aspath1
&& aspath2
) )
1488 if ( !(aspath1
->segments
&& aspath2
->segments
) )
1491 if ( (aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1492 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
) )
1495 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1501 /* Delete all leading AS_CONFED_SEQUENCE/SET segments from aspath.
1502 * See RFC3065, 6.1 c1 */
1504 aspath_delete_confed_seq (struct aspath
*aspath
)
1506 struct assegment
*seg
;
1508 if (!(aspath
&& aspath
->segments
))
1511 seg
= aspath
->segments
;
1513 /* "if the first path segment of the AS_PATH is
1514 * of type AS_CONFED_SEQUENCE,"
1516 if (aspath
->segments
->type
!= AS_CONFED_SEQUENCE
)
1519 /* "... that segment and any immediately following segments
1520 * of the type AS_CONFED_SET or AS_CONFED_SEQUENCE are removed
1521 * from the AS_PATH attribute,"
1524 (seg
->type
== AS_CONFED_SEQUENCE
|| seg
->type
== AS_CONFED_SET
))
1526 aspath
->segments
= seg
->next
;
1527 assegment_free (seg
);
1528 seg
= aspath
->segments
;
1530 aspath_str_update (aspath
);
1534 /* Add new AS number to the leftmost part of the aspath as
1535 AS_CONFED_SEQUENCE. */
1537 aspath_add_confed_seq (struct aspath
*aspath
, as_t asno
)
1539 return aspath_add_one_as (aspath
, asno
, AS_CONFED_SEQUENCE
);
1542 /* Add new as value to as path structure. */
1544 aspath_as_add (struct aspath
*as
, as_t asno
)
1546 struct assegment
*seg
= as
->segments
;
1551 /* Last segment search procedure. */
1555 assegment_append_asns (seg
, &asno
, 1);
1558 /* Add new as segment to the as path. */
1560 aspath_segment_add (struct aspath
*as
, int type
)
1562 struct assegment
*seg
= as
->segments
;
1563 struct assegment
*new = assegment_new (type
, 0);
1578 return aspath_parse (NULL
, 0, 1); /* 32Bit ;-) */
1582 aspath_empty_get (void)
1584 struct aspath
*aspath
;
1586 aspath
= aspath_new ();
1587 aspath
->str
= aspath_make_str_count (aspath
);
1594 return ashash
->count
;
1598 Theoretically, one as path can have:
1600 One BGP packet size should be less than 4096.
1601 One BGP attribute size should be less than 4096 - BGP header size.
1602 One BGP aspath size should be less than 4096 - BGP header size -
1603 BGP mandantry attribute size.
1606 /* AS path string lexical token enum. */
1612 as_token_confed_seq_start
,
1613 as_token_confed_seq_end
,
1614 as_token_confed_set_start
,
1615 as_token_confed_set_end
,
1619 /* Return next token and point for string parse. */
1621 aspath_gettoken (const char *buf
, enum as_token
*token
, u_long
*asno
)
1623 const char *p
= buf
;
1625 /* Skip seperators (space for sequences, ',' for sets). */
1626 while (isspace ((int) *p
) || *p
== ',')
1629 /* Check the end of the string and type specify characters
1636 *token
= as_token_set_start
;
1640 *token
= as_token_set_end
;
1644 *token
= as_token_confed_seq_start
;
1648 *token
= as_token_confed_seq_end
;
1652 *token
= as_token_confed_set_start
;
1656 *token
= as_token_confed_set_end
;
1661 /* Check actual AS value. */
1662 if (isdigit ((int) *p
))
1666 *token
= as_token_asval
;
1670 while (isdigit ((int) *p
))
1673 asval
+= (*p
- '0');
1680 /* There is no match then return unknown token. */
1681 *token
= as_token_unknown
;
1686 aspath_str2aspath (const char *str
)
1688 enum as_token token
= as_token_unknown
;
1691 struct aspath
*aspath
;
1694 aspath
= aspath_new ();
1696 /* We start default type as AS_SEQUENCE. */
1697 as_type
= AS_SEQUENCE
;
1700 while ((str
= aspath_gettoken (str
, &token
, &asno
)) != NULL
)
1704 case as_token_asval
:
1707 aspath_segment_add (aspath
, as_type
);
1710 aspath_as_add (aspath
, asno
);
1712 case as_token_set_start
:
1714 aspath_segment_add (aspath
, as_type
);
1717 case as_token_set_end
:
1718 as_type
= AS_SEQUENCE
;
1721 case as_token_confed_seq_start
:
1722 as_type
= AS_CONFED_SEQUENCE
;
1723 aspath_segment_add (aspath
, as_type
);
1726 case as_token_confed_seq_end
:
1727 as_type
= AS_SEQUENCE
;
1730 case as_token_confed_set_start
:
1731 as_type
= AS_CONFED_SET
;
1732 aspath_segment_add (aspath
, as_type
);
1735 case as_token_confed_set_end
:
1736 as_type
= AS_SEQUENCE
;
1739 case as_token_unknown
:
1741 aspath_free (aspath
);
1746 aspath
->str
= aspath_make_str_count (aspath
);
1751 /* Make hash value by raw aspath data. */
1753 aspath_key_make (void *p
)
1755 struct aspath
* aspath
= (struct aspath
*) p
;
1756 unsigned int key
= 0;
1759 aspath_str_update (aspath
);
1761 key
= jhash (aspath
->str
, strlen(aspath
->str
), 2334325);
1766 /* If two aspath have same value then return 1 else return 0 */
1768 aspath_cmp (const void *arg1
, const void *arg2
)
1770 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
1771 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
1773 while (seg1
|| seg2
)
1776 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
1778 if (seg1
->type
!= seg2
->type
)
1780 if (seg1
->length
!= seg2
->length
)
1782 for (i
= 0; i
< seg1
->length
; i
++)
1783 if (seg1
->as
[i
] != seg2
->as
[i
])
1791 /* AS path hash initialize. */
1795 ashash
= hash_create_size (32767, aspath_key_make
, aspath_cmp
);
1799 aspath_finish (void)
1805 stream_free (snmp_stream
);
1808 /* return and as path value */
1810 aspath_print (struct aspath
*as
)
1812 return (as
? as
->str
: NULL
);
1815 /* Printing functions */
1816 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
1817 * AS_PATH wasn't empty.
1820 aspath_print_vty (struct vty
*vty
, const char *format
, struct aspath
*as
, const char * suffix
)
1823 vty_out (vty
, format
, as
->str
);
1824 if (strlen (as
->str
) && strlen (suffix
))
1825 vty_out (vty
, "%s", suffix
);
1829 aspath_show_all_iterator (struct hash_backet
*backet
, struct vty
*vty
)
1833 as
= (struct aspath
*) backet
->data
;
1835 vty_out (vty
, "[%p:%u] (%ld) ", backet
, backet
->key
, as
->refcnt
);
1836 vty_out (vty
, "%s%s", as
->str
, VTY_NEWLINE
);
1839 /* Print all aspath and hash information. This function is used from
1840 `show ip bgp paths' command. */
1842 aspath_print_all_vty (struct vty
*vty
)
1844 hash_iterate (ashash
,
1845 (void (*) (struct hash_backet
*, void *))
1846 aspath_show_all_iterator
,