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
471 && (seg
->as
[i
] < BGP_PRIVATE_AS_MIN
472 || seg
->as
[i
] > BGP_PRIVATE_AS_MAX
))
473 highest
= seg
->as
[i
];
479 /* Return 1 if there are any 4-byte ASes in the path */
481 aspath_has_as4 (struct aspath
*aspath
)
483 struct assegment
*seg
= aspath
->segments
;
488 for (i
= 0; i
< seg
->length
; i
++)
489 if (seg
->as
[i
] > BGP_AS_MAX
)
496 /* Convert aspath structure to string expression. */
498 aspath_make_str_count (struct aspath
*as
)
500 struct assegment
*seg
;
508 as
->str
= XMALLOC (MTYPE_AS_STR
, 1);
516 /* ASN takes 5 to 10 chars plus seperator, see below.
517 * If there is one differing segment type, we need an additional
518 * 2 chars for segment delimiters, and the final '\0'.
519 * Hopefully this is large enough to avoid hitting the realloc
520 * code below for most common sequences.
522 * This was changed to 10 after the well-known BGP assertion, which
523 * had hit some parts of the Internet in May of 2009.
525 #define ASN_STR_LEN (10 + 1)
526 str_size
= MAX (assegment_count_asns (seg
, 0) * ASN_STR_LEN
+ 2 + 1,
527 ASPATH_STR_DEFAULT_LEN
);
528 str_buf
= XMALLOC (MTYPE_AS_STR
, str_size
);
535 /* Check AS type validity. Set seperator for segment */
543 case AS_CONFED_SEQUENCE
:
547 XFREE (MTYPE_AS_STR
, str_buf
);
553 /* We might need to increase str_buf, particularly if path has
554 * differing segments types, our initial guesstimate above will
555 * have been wrong. Need 10 chars for ASN, a seperator each and
556 * potentially two segment delimiters, plus a space between each
557 * segment and trailing zero.
559 * This definitely didn't work with the value of 5 bytes and
562 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
563 if ( (len
+ SEGMENT_STR_LEN(seg
)) > str_size
)
565 str_size
= len
+ SEGMENT_STR_LEN(seg
);
566 str_buf
= XREALLOC (MTYPE_AS_STR
, str_buf
, str_size
);
569 #undef SEGMENT_STR_LEN
571 if (seg
->type
!= AS_SEQUENCE
)
572 len
+= snprintf (str_buf
+ len
, str_size
- len
,
574 aspath_delimiter_char (seg
->type
, AS_SEG_START
));
576 /* write out the ASNs, with their seperators, bar the last one*/
577 for (i
= 0; i
< seg
->length
; i
++)
579 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%u", seg
->as
[i
]);
581 if (i
< (seg
->length
- 1))
582 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c", seperator
);
585 if (seg
->type
!= AS_SEQUENCE
)
586 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c",
587 aspath_delimiter_char (seg
->type
, AS_SEG_END
));
589 len
+= snprintf (str_buf
+ len
, str_size
- len
, " ");
594 assert (len
< str_size
);
604 aspath_str_update (struct aspath
*as
)
607 XFREE (MTYPE_AS_STR
, as
->str
);
608 aspath_make_str_count (as
);
611 /* Intern allocated AS path. */
613 aspath_intern (struct aspath
*aspath
)
617 /* Assert this AS path structure is not interned and has the string
618 representation built. */
619 assert (aspath
->refcnt
== 0);
620 assert (aspath
->str
);
622 /* Check AS path hash. */
623 find
= hash_get (ashash
, aspath
, hash_alloc_intern
);
625 aspath_free (aspath
);
632 /* Duplicate aspath structure. Created same aspath structure but
633 reference count and AS path string is cleared. */
635 aspath_dup (struct aspath
*aspath
)
637 unsigned short buflen
= aspath
->str_len
+ 1;
640 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
642 if (aspath
->segments
)
643 new->segments
= assegment_dup_all (aspath
->segments
);
648 new->str
= XMALLOC (MTYPE_AS_STR
, buflen
);
649 new->str_len
= aspath
->str_len
;
651 /* copy the string data */
652 if (aspath
->str_len
> 0)
653 memcpy (new->str
, aspath
->str
, buflen
);
661 aspath_hash_alloc (void *arg
)
663 const struct aspath
*aspath
= arg
;
666 /* Malformed AS path value. */
667 assert (aspath
->str
);
671 /* New aspath structure is needed. */
672 new = XMALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
674 /* Reuse segments and string representation */
676 new->segments
= aspath
->segments
;
677 new->str
= aspath
->str
;
678 new->str_len
= aspath
->str_len
;
683 /* parse as-segment byte stream in struct assegment */
685 assegments_parse (struct stream
*s
, size_t length
,
686 struct assegment
**result
, int use32bit
)
688 struct assegment_header segh
;
689 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
692 /* empty aspath (ie iBGP or somesuch) */
696 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
697 zlog_debug ("[AS4SEG] Parse aspath segment: got total byte length %lu",
698 (unsigned long) length
);
700 if ((STREAM_READABLE(s
) < length
)
701 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
702 || (length
% AS16_VALUE_SIZE
))
705 while (bytes
< length
)
710 if ((length
- bytes
) <= AS_HEADER_SIZE
)
713 assegment_free_all (head
);
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 * Shift both values by 0x10 to make the comparison operate
733 * on more, than 8 bits (otherwise it's a warning, bug #564).
735 || ((sizeof segh
.length
> 1)
736 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
)))
739 assegment_free_all (head
);
747 case AS_CONFED_SEQUENCE
:
752 assegment_free_all (head
);
756 /* now its safe to trust lengths */
757 seg
= assegment_new (segh
.type
, segh
.length
);
761 else /* it's the first segment */
764 for (i
= 0; i
< segh
.length
; i
++)
765 seg
->as
[i
] = (use32bit
) ? stream_getl (s
) : stream_getw (s
);
769 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
770 zlog_debug ("[AS4SEG] Parse aspath segment: Bytes now: %lu",
771 (unsigned long) bytes
);
776 *result
= assegment_normalise (head
);
780 /* AS path parse function. pnt is a pointer to byte stream and length
781 is length of byte stream. If there is same AS path in the the AS
782 path hash then return it else make new AS path structure.
784 On error NULL is returned.
787 aspath_parse (struct stream
*s
, size_t length
, int use32bit
)
792 /* If length is odd it's malformed AS path. */
793 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
794 * otherwise its malformed when length is larger than 2 and (length-2)
795 * is not dividable by 4.
796 * But... this time we're lazy
798 if (length
% AS16_VALUE_SIZE
)
801 memset (&as
, 0, sizeof (struct aspath
));
802 if (assegments_parse (s
, length
, &as
.segments
, use32bit
) < 0)
805 /* If already same aspath exist then return it. */
806 find
= hash_get (ashash
, &as
, aspath_hash_alloc
);
808 /* bug! should not happen, let the daemon crash below */
811 /* if the aspath was already hashed free temporary memory. */
814 assegment_free_all (as
.segments
);
815 /* aspath_key_make() always updates the string */
816 XFREE (MTYPE_AS_STR
, as
.str
);
825 assegment_data_put (struct stream
*s
, as_t
*as
, int num
, int use32bit
)
828 assert (num
<= AS_SEGMENT_MAX
);
830 for (i
= 0; i
< num
; i
++)
832 stream_putl (s
, as
[i
]);
835 if ( as
[i
] <= BGP_AS_MAX
)
836 stream_putw(s
, as
[i
]);
838 stream_putw(s
, BGP_AS_TRANS
);
843 assegment_header_put (struct stream
*s
, u_char type
, int length
)
846 assert (length
<= AS_SEGMENT_MAX
);
847 stream_putc (s
, type
);
848 lenp
= stream_get_endp (s
);
849 stream_putc (s
, length
);
853 /* write aspath data to stream */
855 aspath_put (struct stream
*s
, struct aspath
*as
, int use32bit
)
857 struct assegment
*seg
= as
->segments
;
860 if (!seg
|| seg
->length
== 0)
866 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
867 * At the moment, we would write out a partial aspath, and our peer
868 * will complain and drop the session :-/
870 * The general assumption here is that many things tested will
871 * never happen. And, in real live, up to now, they have not.
873 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
) <= STREAM_WRITEABLE(s
)))
875 struct assegment
*next
= seg
->next
;
880 /* Overlength segments have to be split up */
881 while ( (seg
->length
- written
) > AS_SEGMENT_MAX
)
883 assegment_header_put (s
, seg
->type
, AS_SEGMENT_MAX
);
884 assegment_data_put (s
, seg
->as
, AS_SEGMENT_MAX
, use32bit
);
885 written
+= AS_SEGMENT_MAX
;
886 bytes
+= ASSEGMENT_SIZE (written
, use32bit
);
889 /* write the final segment, probably is also the first */
890 lenp
= assegment_header_put (s
, seg
->type
, seg
->length
- written
);
891 assegment_data_put (s
, (seg
->as
+ written
), seg
->length
- written
,
894 /* Sequence-type segments can be 'packed' together
895 * Case of a segment which was overlength and split up
896 * will be missed here, but that doesn't matter.
898 while (next
&& ASSEGMENTS_PACKABLE (seg
, next
))
900 /* NB: We should never normally get here given we
901 * normalise aspath data when parse them. However, better
902 * safe than sorry. We potentially could call
903 * assegment_normalise here instead, but it's cheaper and
904 * easier to do it on the fly here rather than go through
905 * the segment list twice every time we write out
909 /* Next segment's data can fit in this one */
910 assegment_data_put (s
, next
->as
, next
->length
, use32bit
);
912 /* update the length of the segment header */
913 stream_putc_at (s
, lenp
, seg
->length
- written
+ next
->length
);
914 asns_packed
+= next
->length
;
919 bytes
+= ASSEGMENT_SIZE (seg
->length
- written
+ asns_packed
,
927 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
928 * We have no way to manage the storage, so we use a static stream
929 * wrapper around aspath_put.
932 aspath_snmp_pathseg (struct aspath
*as
, size_t *varlen
)
934 #define SNMP_PATHSEG_MAX 1024
937 snmp_stream
= stream_new (SNMP_PATHSEG_MAX
);
939 stream_reset (snmp_stream
);
946 aspath_put (snmp_stream
, as
, 0); /* use 16 bit for now here */
948 *varlen
= stream_get_endp (snmp_stream
);
949 return stream_pnt(snmp_stream
);
952 #define min(A,B) ((A) < (B) ? (A) : (B))
954 static struct assegment
*
955 aspath_aggregate_as_set_add (struct aspath
*aspath
, struct assegment
*asset
,
960 /* If this is first AS set member, create new as-set segment. */
963 asset
= assegment_new (AS_SET
, 1);
964 if (! aspath
->segments
)
965 aspath
->segments
= asset
;
968 struct assegment
*seg
= aspath
->segments
;
973 asset
->type
= AS_SET
;
979 /* Check this AS value already exists or not. */
980 for (i
= 0; i
< asset
->length
; i
++)
981 if (asset
->as
[i
] == as
)
985 asset
->as
= XREALLOC (MTYPE_AS_SEG_DATA
, asset
->as
,
986 asset
->length
* AS_VALUE_SIZE
);
987 asset
->as
[asset
->length
- 1] = as
;
994 /* Modify as1 using as2 for aggregation. */
996 aspath_aggregate (struct aspath
*as1
, struct aspath
*as2
)
1002 struct assegment
*seg1
= as1
->segments
;
1003 struct assegment
*seg2
= as2
->segments
;
1004 struct aspath
*aspath
= NULL
;
1005 struct assegment
*asset
;
1006 struct assegment
*prevseg
= NULL
;
1013 /* First of all check common leading sequence. */
1014 while (seg1
&& seg2
)
1016 /* Check segment type. */
1017 if (seg1
->type
!= seg2
->type
)
1020 /* Minimum segment length. */
1021 minlen
= min (seg1
->length
, seg2
->length
);
1023 for (match
= 0; match
< minlen
; match
++)
1024 if (seg1
->as
[match
] != seg2
->as
[match
])
1029 struct assegment
*seg
= assegment_new (seg1
->type
, 0);
1031 seg
= assegment_append_asns (seg
, seg1
->as
, match
);
1035 aspath
= aspath_new ();
1036 aspath
->segments
= seg
;
1039 prevseg
->next
= seg
;
1044 if (match
!= minlen
|| match
!= seg1
->length
1045 || seg1
->length
!= seg2
->length
)
1053 aspath
= aspath_new();
1055 /* Make as-set using rest of all information. */
1059 for (i
= from
; i
< seg1
->length
; i
++)
1060 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg1
->as
[i
]);
1069 for (i
= from
; i
< seg2
->length
; i
++)
1070 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg2
->as
[i
]);
1076 assegment_normalise (aspath
->segments
);
1077 aspath_str_update (aspath
);
1081 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1082 attribute, check the leftmost AS number in the AS_PATH attribute is
1083 or not the peer's AS number. */
1085 aspath_firstas_check (struct aspath
*aspath
, as_t asno
)
1087 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
1090 if (aspath
->segments
1091 && (aspath
->segments
->type
== AS_SEQUENCE
)
1092 && (aspath
->segments
->as
[0] == asno
))
1098 /* AS path loop check. If aspath contains asno then return >= 1. */
1100 aspath_loop_check (struct aspath
*aspath
, as_t asno
)
1102 struct assegment
*seg
;
1105 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
1108 seg
= aspath
->segments
;
1114 for (i
= 0; i
< seg
->length
; i
++)
1115 if (seg
->as
[i
] == asno
)
1123 /* When all of AS path is private AS return 1. */
1125 aspath_private_as_check (struct aspath
*aspath
)
1127 struct assegment
*seg
;
1129 if ( !(aspath
&& aspath
->segments
) )
1132 seg
= aspath
->segments
;
1138 for (i
= 0; i
< seg
->length
; i
++)
1140 if ( (seg
->as
[i
] < BGP_PRIVATE_AS_MIN
)
1141 || (seg
->as
[i
] > BGP_PRIVATE_AS_MAX
) )
1149 /* AS path confed check. If aspath contains confed set or sequence then return 1. */
1151 aspath_confed_check (struct aspath
*aspath
)
1153 struct assegment
*seg
;
1155 if ( !(aspath
&& aspath
->segments
) )
1158 seg
= aspath
->segments
;
1162 if (seg
->type
== AS_CONFED_SET
|| seg
->type
== AS_CONFED_SEQUENCE
)
1169 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1170 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1172 aspath_left_confed_check (struct aspath
*aspath
)
1175 if ( !(aspath
&& aspath
->segments
) )
1178 if ( (aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1179 || (aspath
->segments
->type
== AS_CONFED_SET
) )
1185 /* Merge as1 to as2. as2 should be uninterned aspath. */
1186 static struct aspath
*
1187 aspath_merge (struct aspath
*as1
, struct aspath
*as2
)
1189 struct assegment
*last
, *new;
1194 last
= new = assegment_dup_all (as1
->segments
);
1196 /* find the last valid segment */
1197 while (last
&& last
->next
)
1200 last
->next
= as2
->segments
;
1201 as2
->segments
= new;
1202 aspath_str_update (as2
);
1206 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1208 aspath_prepend (struct aspath
*as1
, struct aspath
*as2
)
1210 struct assegment
*seg1
;
1211 struct assegment
*seg2
;
1216 seg1
= as1
->segments
;
1217 seg2
= as2
->segments
;
1219 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1222 as2
->segments
= assegment_dup_all (as1
->segments
);
1223 aspath_str_update (as2
);
1227 /* If as1 is empty AS, no prepending to do. */
1231 /* find the tail as1's segment chain. */
1232 while (seg1
&& seg1
->next
)
1235 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1236 if (seg1
->type
== AS_SEQUENCE
&& seg2
->type
== AS_CONFED_SEQUENCE
)
1237 as2
= aspath_delete_confed_seq (as2
);
1239 /* Compare last segment type of as1 and first segment type of as2. */
1240 if (seg1
->type
!= seg2
->type
)
1241 return aspath_merge (as1
, as2
);
1243 if (seg1
->type
== AS_SEQUENCE
)
1245 /* We have two chains of segments, as1->segments and seg2,
1246 * and we have to attach them together, merging the attaching
1247 * segments together into one.
1249 * 1. dupe as1->segments onto head of as2
1250 * 2. merge seg2's asns onto last segment of this new chain
1251 * 3. attach chain after seg2
1254 /* dupe as1 onto as2's head */
1255 seg1
= as2
->segments
= assegment_dup_all (as1
->segments
);
1257 /* refind the tail of as2, reusing seg1 */
1258 while (seg1
&& seg1
->next
)
1261 /* merge the old head, seg2, into tail, seg1 */
1262 seg1
= assegment_append_asns (seg1
, seg2
->as
, seg2
->length
);
1264 /* bypass the merged seg2, and attach any chain after it to
1265 * chain descending from as2's head
1267 seg1
->next
= seg2
->next
;
1269 /* seg2 is now referenceless and useless*/
1270 assegment_free (seg2
);
1272 /* we've now prepended as1's segment chain to as2, merging
1273 * the inbetween AS_SEQUENCE of seg2 in the process
1275 aspath_str_update (as2
);
1280 /* AS_SET merge code is needed at here. */
1281 return aspath_merge (as1
, as2
);
1283 /* XXX: Ermmm, what if as1 has multiple segments?? */
1288 /* Iterate over AS_PATH segments and wipe all occurences of the
1289 * listed AS numbers. Hence some segments may lose some or even
1290 * all data on the way, the operation is implemented as a smarter
1291 * version of aspath_dup(), which allocates memory to hold the new
1292 * data, not the original. The new AS path is returned.
1295 aspath_filter_exclude (struct aspath
* source
, struct aspath
* exclude_list
)
1297 struct assegment
* srcseg
, * exclseg
, * lastseg
;
1298 struct aspath
* newpath
;
1300 newpath
= aspath_new();
1303 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
)
1305 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1306 struct assegment
* newseg
;
1308 /* Find out, how much ASns are we going to pick from this segment.
1309 * We can't perform filtering right inline, because the size of
1310 * the new segment isn't known at the moment yet.
1312 for (i
= 0; i
< srcseg
->length
; i
++)
1315 for (exclseg
= exclude_list
->segments
; exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1316 for (y
= 0; y
< exclseg
->length
; y
++)
1317 if (srcseg
->as
[i
] == exclseg
->as
[y
])
1320 // There's no sense in testing the rest of exclusion list, bail out.
1326 /* newlen is now the number of ASns to copy */
1330 /* Actual copying. Allocate memory and iterate once more, performing filtering. */
1331 newseg
= assegment_new (srcseg
->type
, newlen
);
1332 for (i
= 0; i
< srcseg
->length
; i
++)
1335 for (exclseg
= exclude_list
->segments
; exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1336 for (y
= 0; y
< exclseg
->length
; y
++)
1337 if (srcseg
->as
[i
] == exclseg
->as
[y
])
1344 newseg
->as
[done
++] = srcseg
->as
[i
];
1346 /* At his point newlen must be equal to done, and both must be positive. Append
1347 * the filtered segment to the gross result. */
1349 newpath
->segments
= newseg
;
1351 lastseg
->next
= newseg
;
1354 aspath_str_update (newpath
);
1355 /* We are happy returning even an empty AS_PATH, because the administrator
1356 * might expect this very behaviour. There's a mean to avoid this, if necessary,
1357 * by having a match rule against certain AS_PATH regexps in the route-map index.
1359 aspath_free (source
);
1363 /* Add specified AS to the leftmost of aspath. */
1364 static struct aspath
*
1365 aspath_add_one_as (struct aspath
*aspath
, as_t asno
, u_char type
)
1367 struct assegment
*assegment
= aspath
->segments
;
1369 /* In case of empty aspath. */
1370 if (assegment
== NULL
|| assegment
->length
== 0)
1372 aspath
->segments
= assegment_new (type
, 1);
1373 aspath
->segments
->as
[0] = asno
;
1376 assegment_free (assegment
);
1381 if (assegment
->type
== type
)
1382 aspath
->segments
= assegment_prepend_asns (aspath
->segments
, asno
, 1);
1385 /* create new segment
1386 * push it onto head of aspath's segment chain
1388 struct assegment
*newsegment
;
1390 newsegment
= assegment_new (type
, 1);
1391 newsegment
->as
[0] = asno
;
1393 newsegment
->next
= assegment
;
1394 aspath
->segments
= newsegment
;
1400 /* Add specified AS to the leftmost of aspath. */
1402 aspath_add_seq (struct aspath
*aspath
, as_t asno
)
1404 return aspath_add_one_as (aspath
, asno
, AS_SEQUENCE
);
1407 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1408 as2's leftmost AS is same return 1. */
1410 aspath_cmp_left (const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1412 const struct assegment
*seg1
;
1413 const struct assegment
*seg2
;
1415 if (!(aspath1
&& aspath2
))
1418 seg1
= aspath1
->segments
;
1419 seg2
= aspath2
->segments
;
1421 /* find first non-confed segments for each */
1422 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1423 || (seg1
->type
== AS_CONFED_SET
)))
1426 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1427 || (seg2
->type
== AS_CONFED_SET
)))
1432 && (seg1
->type
== AS_SEQUENCE
) && (seg2
->type
== AS_SEQUENCE
)))
1435 if (seg1
->as
[0] == seg2
->as
[0])
1441 /* Truncate an aspath after a number of hops, and put the hops remaining
1442 * at the front of another aspath. Needed for AS4 compat.
1444 * Returned aspath is a /new/ aspath, which should either by free'd or
1445 * interned by the caller, as desired.
1448 aspath_reconcile_as4 ( struct aspath
*aspath
, struct aspath
*as4path
)
1450 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1451 struct aspath
*newpath
= NULL
, *mergedpath
;
1452 int hops
, cpasns
= 0;
1457 seg
= aspath
->segments
;
1459 /* CONFEDs should get reconciled too.. */
1460 hops
= (aspath_count_hops (aspath
) + aspath_count_confeds (aspath
))
1461 - aspath_count_hops (as4path
);
1465 if (BGP_DEBUG (as4
, AS4
))
1466 zlog_warn ("[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1467 /* Something's gone wrong. The RFC says we should now ignore AS4_PATH,
1468 * which is daft behaviour - it contains vital loop-detection
1469 * information which must have been removed from AS_PATH.
1471 hops
= aspath_count_hops (aspath
);
1475 return aspath_dup (as4path
);
1477 if ( BGP_DEBUG(as4
, AS4
))
1478 zlog_debug("[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1479 aspath
->str
, as4path
->str
);
1481 while (seg
&& hops
> 0)
1488 cpasns
= seg
->length
;
1490 case AS_CONFED_SEQUENCE
:
1491 /* Should never split a confed-sequence, if hop-count
1492 * suggests we must then something's gone wrong somewhere.
1494 * Most important goal is to preserve AS_PATHs prime function
1495 * as loop-detector, so we fudge the numbers so that the entire
1496 * confed-sequence is merged in.
1498 if (hops
< seg
->length
)
1500 if (BGP_DEBUG (as4
, AS4
))
1501 zlog_debug ("[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1502 " across 2/4 ASN boundary somewhere, broken..");
1506 cpasns
= MIN(seg
->length
, hops
);
1507 hops
-= seg
->length
;
1510 assert (cpasns
<= seg
->length
);
1512 newseg
= assegment_new (seg
->type
, 0);
1513 newseg
= assegment_append_asns (newseg
, seg
->as
, cpasns
);
1517 newpath
= aspath_new ();
1518 newpath
->segments
= newseg
;
1521 prevseg
->next
= newseg
;
1527 /* We may be able to join some segments here, and we must
1528 * do this because... we want normalised aspaths in out hash
1529 * and we do not want to stumble in aspath_put.
1531 mergedpath
= aspath_merge (newpath
, aspath_dup(as4path
));
1532 aspath_free (newpath
);
1533 mergedpath
->segments
= assegment_normalise (mergedpath
->segments
);
1534 aspath_str_update (mergedpath
);
1536 if ( BGP_DEBUG(as4
, AS4
))
1537 zlog_debug ("[AS4] result of synthesizing is %s",
1543 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1544 as2's leftmost AS is same return 1. (confederation as-path
1547 aspath_cmp_left_confed (const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1549 if (! (aspath1
&& aspath2
) )
1552 if ( !(aspath1
->segments
&& aspath2
->segments
) )
1555 if ( (aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1556 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
) )
1559 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1565 /* Delete all leading AS_CONFED_SEQUENCE/SET segments from aspath.
1566 * See RFC3065, 6.1 c1 */
1568 aspath_delete_confed_seq (struct aspath
*aspath
)
1570 struct assegment
*seg
;
1572 if (!(aspath
&& aspath
->segments
))
1575 seg
= aspath
->segments
;
1577 /* "if the first path segment of the AS_PATH is
1578 * of type AS_CONFED_SEQUENCE,"
1580 if (aspath
->segments
->type
!= AS_CONFED_SEQUENCE
)
1583 /* "... that segment and any immediately following segments
1584 * of the type AS_CONFED_SET or AS_CONFED_SEQUENCE are removed
1585 * from the AS_PATH attribute,"
1588 (seg
->type
== AS_CONFED_SEQUENCE
|| seg
->type
== AS_CONFED_SET
))
1590 aspath
->segments
= seg
->next
;
1591 assegment_free (seg
);
1592 seg
= aspath
->segments
;
1594 aspath_str_update (aspath
);
1598 /* Add new AS number to the leftmost part of the aspath as
1599 AS_CONFED_SEQUENCE. */
1601 aspath_add_confed_seq (struct aspath
*aspath
, as_t asno
)
1603 return aspath_add_one_as (aspath
, asno
, AS_CONFED_SEQUENCE
);
1606 /* Add new as value to as path structure. */
1608 aspath_as_add (struct aspath
*as
, as_t asno
)
1610 struct assegment
*seg
= as
->segments
;
1615 /* Last segment search procedure. */
1619 assegment_append_asns (seg
, &asno
, 1);
1622 /* Add new as segment to the as path. */
1624 aspath_segment_add (struct aspath
*as
, int type
)
1626 struct assegment
*seg
= as
->segments
;
1627 struct assegment
*new = assegment_new (type
, 0);
1642 return aspath_parse (NULL
, 0, 1); /* 32Bit ;-) */
1646 aspath_empty_get (void)
1648 struct aspath
*aspath
;
1650 aspath
= aspath_new ();
1651 aspath_make_str_count (aspath
);
1658 return ashash
->count
;
1662 Theoretically, one as path can have:
1664 One BGP packet size should be less than 4096.
1665 One BGP attribute size should be less than 4096 - BGP header size.
1666 One BGP aspath size should be less than 4096 - BGP header size -
1667 BGP mandantry attribute size.
1670 /* AS path string lexical token enum. */
1676 as_token_confed_seq_start
,
1677 as_token_confed_seq_end
,
1678 as_token_confed_set_start
,
1679 as_token_confed_set_end
,
1683 /* Return next token and point for string parse. */
1685 aspath_gettoken (const char *buf
, enum as_token
*token
, u_long
*asno
)
1687 const char *p
= buf
;
1689 /* Skip seperators (space for sequences, ',' for sets). */
1690 while (isspace ((int) *p
) || *p
== ',')
1693 /* Check the end of the string and type specify characters
1700 *token
= as_token_set_start
;
1704 *token
= as_token_set_end
;
1708 *token
= as_token_confed_seq_start
;
1712 *token
= as_token_confed_seq_end
;
1716 *token
= as_token_confed_set_start
;
1720 *token
= as_token_confed_set_end
;
1725 /* Check actual AS value. */
1726 if (isdigit ((int) *p
))
1730 *token
= as_token_asval
;
1734 while (isdigit ((int) *p
))
1737 asval
+= (*p
- '0');
1744 /* There is no match then return unknown token. */
1745 *token
= as_token_unknown
;
1750 aspath_str2aspath (const char *str
)
1752 enum as_token token
= as_token_unknown
;
1755 struct aspath
*aspath
;
1758 aspath
= aspath_new ();
1760 /* We start default type as AS_SEQUENCE. */
1761 as_type
= AS_SEQUENCE
;
1764 while ((str
= aspath_gettoken (str
, &token
, &asno
)) != NULL
)
1768 case as_token_asval
:
1771 aspath_segment_add (aspath
, as_type
);
1774 aspath_as_add (aspath
, asno
);
1776 case as_token_set_start
:
1778 aspath_segment_add (aspath
, as_type
);
1781 case as_token_set_end
:
1782 as_type
= AS_SEQUENCE
;
1785 case as_token_confed_seq_start
:
1786 as_type
= AS_CONFED_SEQUENCE
;
1787 aspath_segment_add (aspath
, as_type
);
1790 case as_token_confed_seq_end
:
1791 as_type
= AS_SEQUENCE
;
1794 case as_token_confed_set_start
:
1795 as_type
= AS_CONFED_SET
;
1796 aspath_segment_add (aspath
, as_type
);
1799 case as_token_confed_set_end
:
1800 as_type
= AS_SEQUENCE
;
1803 case as_token_unknown
:
1805 aspath_free (aspath
);
1810 aspath_make_str_count (aspath
);
1815 /* Make hash value by raw aspath data. */
1817 aspath_key_make (void *p
)
1819 struct aspath
*aspath
= (struct aspath
*) p
;
1820 unsigned int key
= 0;
1823 aspath_str_update (aspath
);
1825 key
= jhash (aspath
->str
, aspath
->str_len
, 2334325);
1830 /* If two aspath have same value then return 1 else return 0 */
1832 aspath_cmp (const void *arg1
, const void *arg2
)
1834 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
1835 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
1837 while (seg1
|| seg2
)
1840 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
1842 if (seg1
->type
!= seg2
->type
)
1844 if (seg1
->length
!= seg2
->length
)
1846 for (i
= 0; i
< seg1
->length
; i
++)
1847 if (seg1
->as
[i
] != seg2
->as
[i
])
1855 /* AS path hash initialize. */
1859 ashash
= hash_create_size (32768, aspath_key_make
, aspath_cmp
);
1863 aspath_finish (void)
1869 stream_free (snmp_stream
);
1872 /* return and as path value */
1874 aspath_print (struct aspath
*as
)
1876 return (as
? as
->str
: NULL
);
1879 /* Printing functions */
1880 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
1881 * AS_PATH wasn't empty.
1884 aspath_print_vty (struct vty
*vty
, const char *format
, struct aspath
*as
, const char * suffix
)
1887 vty_out (vty
, format
, as
->str
);
1888 if (as
->str_len
&& strlen (suffix
))
1889 vty_out (vty
, "%s", suffix
);
1893 aspath_show_all_iterator (struct hash_backet
*backet
, struct vty
*vty
)
1897 as
= (struct aspath
*) backet
->data
;
1899 vty_out (vty
, "[%p:%u] (%ld) ", backet
, backet
->key
, as
->refcnt
);
1900 vty_out (vty
, "%s%s", as
->str
, VTY_NEWLINE
);
1903 /* Print all aspath and hash information. This function is used from
1904 `show ip bgp paths' command. */
1906 aspath_print_all_vty (struct vty
*vty
)
1908 hash_iterate (ashash
,
1909 (void (*) (struct hash_backet
*, void *))
1910 aspath_show_all_iterator
,