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
32 #include "bgpd/bgpd.h"
33 #include "bgpd/bgp_aspath.h"
35 /* Attr. Flags and Attr. Type Code. */
36 #define AS_HEADER_SIZE 2
38 /* Two octet is used for AS value. */
39 #define AS_VALUE_SIZE sizeof (as_t)
41 /* Maximum protocol segment length value */
42 #define AS_SEGMENT_MAX 255
44 /* The following length and size macros relate specifically to Quagga's
45 * internal representation of AS-Segments, not per se to the on-wire
46 * sizes and lengths. At present (200508) they sort of match, however
47 * the ONLY functions which should now about the on-wire syntax are
48 * aspath_put, assegment_put and assegment_parse.
51 /* Calculated size in bytes of ASN segment data to hold N ASN's */
52 #define ASSEGMENT_DATA_SIZE(N) ((N) * AS_VALUE_SIZE)
54 /* Calculated size of segment struct to hold N ASN's */
55 #define ASSEGMENT_SIZE(N) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N))
57 /* AS segment octet length. */
58 #define ASSEGMENT_LEN(X) ASSEGMENT_SIZE((X)->length)
60 /* AS_SEQUENCE segments can be packed together */
61 /* Can the types of X and Y be considered for packing? */
62 #define ASSEGMENT_TYPES_PACKABLE(X,Y) \
63 ( ((X)->type == (Y)->type) \
64 && ((X)->type == AS_SEQUENCE))
65 /* Types and length of X,Y suitable for packing? */
66 #define ASSEGMENTS_PACKABLE(X,Y) \
67 ( ASSEGMENT_TYPES_PACKABLE( (X), (Y)) \
68 && ( ((X)->length + (Y)->length) <= AS_SEGMENT_MAX ) )
70 /* As segment header - the on-wire representation
71 * NOT the internal representation!
73 struct assegment_header
79 /* Hash for aspath. This is the top level structure of AS path. */
82 /* Stream for SNMP. See aspath_snmp_pathseg */
83 static struct stream
*snmp_stream
;
86 assegment_data_new (int num
)
88 return (XCALLOC (MTYPE_AS_SEG_DATA
, ASSEGMENT_DATA_SIZE (num
)));
92 assegment_data_free (as_t
*asdata
)
94 XFREE (MTYPE_AS_SEG_DATA
,asdata
);
97 /* Get a new segment. Note that 0 is an allowed length,
98 * and will result in a segment with no allocated data segment.
99 * the caller should immediately assign data to the segment, as the segment
100 * otherwise is not generally valid
102 static struct assegment
*
103 assegment_new (u_char type
, u_short length
)
105 struct assegment
*new;
107 new = XCALLOC (MTYPE_AS_SEG
, sizeof (struct assegment
));
110 new->as
= assegment_data_new (length
);
112 new->length
= length
;
119 assegment_free (struct assegment
*seg
)
125 XFREE (MTYPE_AS_SEG_DATA
, seg
->as
);
126 memset (seg
, 0xfe, sizeof(struct assegment
));
127 XFREE (MTYPE_AS_SEG
, seg
);
132 /* free entire chain of segments */
134 assegment_free_all (struct assegment
*seg
)
136 struct assegment
*prev
;
142 assegment_free (prev
);
146 /* Duplicate just the given assegment and its data */
147 static struct assegment
*
148 assegment_dup (struct assegment
*seg
)
150 struct assegment
*new;
152 new = assegment_new (seg
->type
, seg
->length
);
153 memcpy (new->as
, seg
->as
, ASSEGMENT_DATA_SIZE (new->length
) );
158 /* Duplicate entire chain of assegments, return the head */
159 static struct assegment
*
160 assegment_dup_all (struct assegment
*seg
)
162 struct assegment
*new = NULL
;
163 struct assegment
*head
= NULL
;
169 new->next
= assegment_dup (seg
);
173 head
= new = assegment_dup (seg
);
180 /* prepend the as number to given segment, given num of times */
181 static struct assegment
*
182 assegment_prepend_asns (struct assegment
*seg
, as_t asnum
, int num
)
189 if (num
>= AS_SEGMENT_MAX
)
190 return seg
; /* we don't do huge prepends */
192 newas
= assegment_data_new (seg
->length
+ num
);
197 for (i
= 0; i
< num
; i
++)
200 memcpy (newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE (seg
->length
));
201 XFREE (MTYPE_AS_SEG_DATA
, seg
->as
);
207 assegment_free_all (seg
);
211 /* append given array of as numbers to the segment */
212 static struct assegment
*
213 assegment_append_asns (struct assegment
*seg
, as_t
*asnos
, int num
)
217 newas
= XREALLOC (MTYPE_AS_SEG_DATA
, seg
->as
,
218 ASSEGMENT_DATA_SIZE (seg
->length
+ num
));
223 memcpy (seg
->as
+ seg
->length
, asnos
, ASSEGMENT_DATA_SIZE(num
));
228 assegment_free_all (seg
);
233 int_cmp (const void *p1
, const void *p2
)
235 const as_t
*as1
= p1
;
236 const as_t
*as2
= p2
;
238 return (*as1
== *as2
)
239 ? 0 : ( (*as1
> *as2
) ? 1 : -1);
242 /* normalise the segment.
243 * In particular, merge runs of AS_SEQUENCEs into one segment
244 * Internally, we do not care about the wire segment length limit, and
245 * we want each distinct AS_PATHs to have the exact same internal
246 * representation - eg, so that our hashing actually works..
248 static struct assegment
*
249 assegment_normalise (struct assegment
*head
)
251 struct assegment
*seg
= head
, *pin
;
252 struct assegment
*tmp
;
261 /* Sort values SET segments, for determinism in paths to aid
262 * creation of hash values / path comparisons
263 * and because it helps other lesser implementations ;)
265 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
)
266 qsort (seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
268 /* read ahead from the current, pinned segment while the segments
269 * are packable/mergeable. Append all following packable segments
270 * to the segment we have pinned and remove these appended
273 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
))
278 /* append the next sequence to the pinned sequence */
279 pin
= assegment_append_asns (pin
, seg
->as
, seg
->length
);
281 /* bypass the next sequence */
282 pin
->next
= seg
->next
;
284 /* get rid of the now referenceless segment */
285 assegment_free (tmp
);
294 static struct aspath
*
297 struct aspath
*aspath
;
299 aspath
= XMALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
300 memset (aspath
, 0, sizeof (struct aspath
));
304 /* Free AS path structure. */
306 aspath_free (struct aspath
*aspath
)
310 if (aspath
->segments
)
311 assegment_free_all (aspath
->segments
);
313 XFREE (MTYPE_AS_STR
, aspath
->str
);
314 XFREE (MTYPE_AS_PATH
, aspath
);
317 /* Unintern aspath from AS path bucket. */
319 aspath_unintern (struct aspath
*aspath
)
326 if (aspath
->refcnt
== 0)
328 /* This aspath must exist in aspath hash table. */
329 ret
= hash_release (ashash
, aspath
);
330 assert (ret
!= NULL
);
331 aspath_free (aspath
);
335 /* Return the start or end delimiters for a particular Segment type */
336 #define AS_SEG_START 0
339 aspath_delimiter_char (u_char type
, u_char which
)
347 } aspath_delim_char
[] =
349 { AS_SET
, '{', '}' },
350 { AS_CONFED_SET
, '[', ']' },
351 { AS_CONFED_SEQUENCE
, '(', ')' },
355 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++)
357 if (aspath_delim_char
[i
].type
== type
)
359 if (which
== AS_SEG_START
)
360 return aspath_delim_char
[i
].start
;
361 else if (which
== AS_SEG_END
)
362 return aspath_delim_char
[i
].end
;
368 /* countup asns from this segment and index onward */
370 assegment_count_asns (struct assegment
*seg
, int from
)
376 count
+= seg
->length
;
379 count
+= (seg
->length
- from
);
388 aspath_count_confeds (struct aspath
*aspath
)
391 struct assegment
*seg
= aspath
->segments
;
395 if (seg
->type
== AS_CONFED_SEQUENCE
)
396 count
+= seg
->length
;
397 else if (seg
->type
== AS_CONFED_SET
)
406 aspath_count_hops (struct aspath
*aspath
)
409 struct assegment
*seg
= aspath
->segments
;
413 if (seg
->type
== AS_SEQUENCE
)
414 count
+= seg
->length
;
415 else if (seg
->type
== AS_SET
)
424 aspath_size (struct aspath
*aspath
)
427 struct assegment
*seg
= aspath
->segments
;
431 size
+= ASSEGMENT_SIZE(seg
->length
);
437 /* Convert aspath structure to string expression. */
439 aspath_make_str_count (struct aspath
*as
)
441 struct assegment
*seg
;
449 str_buf
= XMALLOC (MTYPE_AS_STR
, 1);
456 /* ASN takes 5 chars at least, plus seperator, see below.
457 * If there is one differing segment type, we need an additional
458 * 2 chars for segment delimiters, and the final '\0'.
459 * Hopefully this is large enough to avoid hitting the realloc
460 * code below for most common sequences.
462 #define ASN_STR_LEN (5 + 1)
463 str_size
= MAX (assegment_count_asns (seg
, 0) * ASN_STR_LEN
+ 2 + 1,
464 ASPATH_STR_DEFAULT_LEN
);
465 str_buf
= XMALLOC (MTYPE_AS_STR
, str_size
);
472 /* Check AS type validity. Set seperator for segment */
480 case AS_CONFED_SEQUENCE
:
484 XFREE (MTYPE_AS_STR
, str_buf
);
488 /* We might need to increase str_buf, particularly if path has
489 * differing segments types, our initial guesstimate above will
490 * have been wrong. need 5 chars for ASN, a seperator each and
491 * potentially two segment delimiters, plus a space between each
492 * segment and trailing zero.
494 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
495 if ( (len
+ SEGMENT_STR_LEN(seg
)) > str_size
)
497 str_size
= len
+ SEGMENT_STR_LEN(seg
);
498 str_buf
= XREALLOC (MTYPE_AS_STR
, str_buf
, str_size
);
501 #undef SEGMENT_STR_LEN
503 if (seg
->type
!= AS_SEQUENCE
)
504 len
+= snprintf (str_buf
+ len
, str_size
- len
,
506 aspath_delimiter_char (seg
->type
, AS_SEG_START
));
508 /* write out the ASNs, with their seperators, bar the last one*/
509 for (i
= 0; i
< seg
->length
; i
++)
511 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%u", seg
->as
[i
]);
513 if (i
< (seg
->length
- 1))
514 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c", seperator
);
517 if (seg
->type
!= AS_SEQUENCE
)
518 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c",
519 aspath_delimiter_char (seg
->type
, AS_SEG_END
));
521 len
+= snprintf (str_buf
+ len
, str_size
- len
, " ");
526 assert (len
< str_size
);
534 aspath_str_update (struct aspath
*as
)
537 XFREE (MTYPE_AS_STR
, as
->str
);
538 as
->str
= aspath_make_str_count (as
);
541 /* Intern allocated AS path. */
543 aspath_intern (struct aspath
*aspath
)
547 /* Assert this AS path structure is not interned. */
548 assert (aspath
->refcnt
== 0);
550 /* Check AS path hash. */
551 find
= hash_get (ashash
, aspath
, hash_alloc_intern
);
554 aspath_free (aspath
);
559 find
->str
= aspath_make_str_count (find
);
564 /* Duplicate aspath structure. Created same aspath structure but
565 reference count and AS path string is cleared. */
567 aspath_dup (struct aspath
*aspath
)
571 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
573 if (aspath
->segments
)
574 new->segments
= assegment_dup_all (aspath
->segments
);
576 new->segments
= NULL
;
578 new->str
= aspath_make_str_count (aspath
);
584 aspath_hash_alloc (void *arg
)
586 struct aspath
*aspath
;
588 /* New aspath strucutre is needed. */
589 aspath
= aspath_dup (arg
);
591 /* Malformed AS path value. */
594 aspath_free (aspath
);
601 /* parse as-segment byte stream in struct assegment */
602 static struct assegment
*
603 assegments_parse (struct stream
*s
, size_t length
)
605 struct assegment_header segh
;
606 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
609 /* empty aspath (ie iBGP or somesuch) */
614 if ( (STREAM_READABLE(s
) < length
)
615 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
616 || (length
% AS_VALUE_SIZE
))
619 while ( (STREAM_READABLE(s
) > AS_HEADER_SIZE
)
624 /* softly softly, get the header first on its own */
625 segh
.type
= stream_getc (s
);
626 segh
.length
= stream_getc (s
);
629 if ( ((bytes
+ ASSEGMENT_SIZE(segh
.length
)) > length
)
630 /* 1771bis 4.3b: seg length contains one or more */
631 || (segh
.length
== 0)
632 /* Paranoia in case someone changes type of segment length */
633 || ((sizeof segh
.length
> 1) && segh
.length
> AS_SEGMENT_MAX
))
636 assegment_free_all (head
);
640 /* now its safe to trust lengths */
641 seg
= assegment_new (segh
.type
, segh
.length
);
645 else /* it's the first segment */
648 for (i
= 0; i
< segh
.length
; i
++)
649 seg
->as
[i
] = stream_getw (s
);
651 bytes
+= ASSEGMENT_SIZE(segh
.length
);
656 return assegment_normalise (head
);
659 /* AS path parse function. pnt is a pointer to byte stream and length
660 is length of byte stream. If there is same AS path in the the AS
661 path hash then return it else make new AS path structure. */
663 aspath_parse (struct stream
*s
, size_t length
)
668 /* If length is odd it's malformed AS path. */
669 if (length
% AS_VALUE_SIZE
)
672 as
.segments
= assegments_parse (s
, length
);
674 /* If already same aspath exist then return it. */
675 find
= hash_get (ashash
, &as
, aspath_hash_alloc
);
677 /* aspath_hash_alloc dupes segments too. that probably could be
680 assegment_free_all (as
.segments
);
690 assegment_data_put (struct stream
*s
, as_t
*as
, int num
)
693 assert (num
<= AS_SEGMENT_MAX
);
695 for (i
= 0; i
< num
; i
++)
696 stream_putw (s
, as
[i
]);
700 assegment_header_put (struct stream
*s
, u_char type
, int length
)
703 assert (length
<= AS_SEGMENT_MAX
);
704 stream_putc (s
, type
);
705 lenp
= stream_get_endp (s
);
706 stream_putc (s
, length
);
710 /* write aspath data to stream */
712 aspath_put (struct stream
*s
, struct aspath
*as
)
714 struct assegment
*seg
= as
->segments
;
716 if (!seg
|| seg
->length
== 0)
721 while (seg
&& (ASSEGMENT_LEN (seg
) <= STREAM_WRITEABLE(s
)))
726 /* Overlength segments have to be split up */
727 while ( (seg
->length
- written
) > AS_SEGMENT_MAX
)
729 assegment_header_put (s
, seg
->type
, AS_SEGMENT_MAX
);
730 assegment_data_put (s
, seg
->as
, AS_SEGMENT_MAX
);
731 written
+= AS_SEGMENT_MAX
;
734 /* write the final segment, probably is also the first */
735 lenp
= assegment_header_put (s
, seg
->type
, seg
->length
- written
);
736 assegment_data_put (s
, (seg
->as
+ written
), seg
->length
- written
);
738 /* Sequence-type segments can be 'packed' together
739 * Case of a segment which was overlength and split up
740 * will be missed here, but that doesn't matter.
742 if (seg
->next
&& ASSEGMENTS_PACKABLE (seg
, seg
->next
))
744 /* NB: We should never normally get here given we
745 * normalise aspath data when parse them. However, better
746 * safe than sorry. We potentially could call
747 * assegment_normalise here instead, but it's cheaper and
748 * easier to do it on the fly here rather than go through
749 * the segment list twice every time we write out
753 /* Next segment's data can fit in this one */
754 assegment_data_put (s
, seg
->next
->as
, seg
->next
->length
);
756 /* update the length of the segment header */
757 stream_putc_at (s
, lenp
,
758 seg
->length
- written
+ seg
->next
->length
);
759 seg
= seg
->next
->next
; /* skip to past next */
767 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
768 * We have no way to manage the storage, so we use a static stream
769 * wrapper around aspath_put.
772 aspath_snmp_pathseg (struct aspath
*as
, size_t *varlen
)
774 #define SNMP_PATHSEG_MAX 1024
777 snmp_stream
= stream_new (SNMP_PATHSEG_MAX
);
779 stream_reset (snmp_stream
);
786 aspath_put (snmp_stream
, as
);
788 *varlen
= stream_get_endp (snmp_stream
);
789 return stream_pnt(snmp_stream
);
792 #define min(A,B) ((A) < (B) ? (A) : (B))
794 static struct assegment
*
795 aspath_aggregate_as_set_add (struct aspath
*aspath
, struct assegment
*asset
,
800 /* If this is first AS set member, create new as-set segment. */
803 asset
= assegment_new (AS_SET
, 1);
804 if (! aspath
->segments
)
805 aspath
->segments
= asset
;
808 struct assegment
*seg
= aspath
->segments
;
813 asset
->type
= AS_SET
;
819 /* Check this AS value already exists or not. */
820 for (i
= 0; i
< asset
->length
; i
++)
821 if (asset
->as
[i
] == as
)
825 asset
->as
= XREALLOC (MTYPE_AS_SEG_DATA
, asset
->as
,
826 asset
->length
* AS_VALUE_SIZE
);
827 asset
->as
[asset
->length
- 1] = as
;
834 /* Modify as1 using as2 for aggregation. */
836 aspath_aggregate (struct aspath
*as1
, struct aspath
*as2
)
842 struct assegment
*seg1
= as1
->segments
;
843 struct assegment
*seg2
= as2
->segments
;
844 struct aspath
*aspath
;
845 struct assegment
*asset
;
852 /* First of all check common leading sequence. */
855 /* Check segment type. */
856 if (seg1
->type
!= seg2
->type
)
859 /* Minimum segment length. */
860 minlen
= min (seg1
->length
, seg2
->length
);
862 for (match
= 0; match
< minlen
; match
++)
863 if (seg1
->as
[match
] != seg2
->as
[match
])
869 aspath
= aspath_new ();
870 aspath
->segments
= assegment_new (seg1
->type
, 0);
871 aspath
->segments
= assegment_append_asns (aspath
->segments
,
875 if (match
!= minlen
|| match
!= seg1
->length
876 || seg1
->length
!= seg2
->length
)
884 aspath
= aspath_new();
886 /* Make as-set using rest of all information. */
890 for (i
= from
; i
< seg1
->length
; i
++)
891 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg1
->as
[i
]);
900 for (i
= from
; i
< seg2
->length
; i
++)
901 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg2
->as
[i
]);
907 assegment_normalise (aspath
->segments
);
908 aspath_str_update (aspath
);
912 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
913 attribute, check the leftmost AS number in the AS_PATH attribute is
914 or not the peer's AS number. */
916 aspath_firstas_check (struct aspath
*aspath
, as_t asno
)
918 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
922 && (aspath
->segments
->type
== AS_SEQUENCE
)
923 && (aspath
->segments
->as
[0] == asno
))
929 /* AS path loop check. If aspath contains asno then return 1. */
931 aspath_loop_check (struct aspath
*aspath
, as_t asno
)
933 struct assegment
*seg
;
936 if ( (aspath
== NULL
) || (aspath
->segments
) )
939 seg
= aspath
->segments
;
945 for (i
= 0; i
< seg
->length
; i
++)
946 if (seg
->as
[i
] == asno
)
954 /* When all of AS path is private AS return 1. */
956 aspath_private_as_check (struct aspath
*aspath
)
958 struct assegment
*seg
;
960 if ( !(aspath
&& aspath
->segments
) )
963 seg
= aspath
->segments
;
969 for (i
= 0; i
< seg
->length
; i
++)
971 if ( (seg
->as
[i
] < BGP_PRIVATE_AS_MIN
)
972 || (seg
->as
[i
] > BGP_PRIVATE_AS_MAX
) )
980 /* Merge as1 to as2. as2 should be uninterned aspath. */
981 static struct aspath
*
982 aspath_merge (struct aspath
*as1
, struct aspath
*as2
)
984 struct assegment
*last
, *new;
989 last
= new = assegment_dup_all (as1
->segments
);
991 /* find the last valid segment */
992 while (last
&& last
->next
)
995 last
->next
= as2
->segments
;
997 aspath_str_update (as2
);
1001 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1003 aspath_prepend (struct aspath
*as1
, struct aspath
*as2
)
1005 struct assegment
*seg1
;
1006 struct assegment
*seg2
;
1011 seg1
= as1
->segments
;
1012 seg2
= as2
->segments
;
1014 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1017 as2
->segments
= assegment_dup_all (as1
->segments
);
1018 aspath_str_update (as2
);
1022 /* If as1 is empty AS, no prepending to do. */
1026 /* find the tail as1's segment chain. */
1027 while (seg1
&& seg1
->next
)
1030 /* Compare last segment type of as1 and first segment type of as2. */
1031 if (seg1
->type
!= seg2
->type
)
1032 return aspath_merge (as1
, as2
);
1034 if (seg1
->type
== AS_SEQUENCE
)
1036 /* We have two chains of segments, as1->segments and seg2,
1037 * and we have to attach them together, merging the attaching
1038 * segments together into one.
1040 * 1. dupe as1->segments onto head of as2
1041 * 2. merge seg2's asns onto last segment of this new chain
1042 * 3. attach chain after seg2
1045 /* dupe as1 onto as2's head */
1046 seg1
= as2
->segments
= assegment_dup_all (as1
->segments
);
1048 /* refind the tail of as2, reusing seg1 */
1049 while (seg1
&& seg1
->next
)
1052 /* merge the old head, seg2, into tail, seg1 */
1053 seg1
= assegment_append_asns (seg1
, seg2
->as
, seg2
->length
);
1055 /* bypass the merged seg2, and attach any chain after it to
1056 * chain descending from as2's head
1058 seg1
->next
= seg2
->next
;
1060 /* seg2 is now referenceless and useless*/
1061 assegment_free (seg2
);
1063 /* we've now prepended as1's segment chain to as2, merging
1064 * the inbetween AS_SEQUENCE of seg2 in the process
1066 aspath_str_update (as2
);
1071 /* AS_SET merge code is needed at here. */
1072 return aspath_merge (as1
, as2
);
1074 /* XXX: Ermmm, what if as1 has multiple segments?? */
1079 /* Add specified AS to the leftmost of aspath. */
1080 static struct aspath
*
1081 aspath_add_one_as (struct aspath
*aspath
, as_t asno
, u_char type
)
1083 struct assegment
*assegment
= aspath
->segments
;
1085 /* In case of empty aspath. */
1086 if (assegment
== NULL
|| assegment
->length
== 0)
1088 aspath
->segments
= assegment_new (type
, 1);
1089 aspath
->segments
->as
[0] = asno
;
1092 assegment_free (assegment
);
1097 if (assegment
->type
== type
)
1098 aspath
->segments
= assegment_prepend_asns (aspath
->segments
, asno
, 1);
1101 /* create new segment
1102 * push it onto head of aspath's segment chain
1104 struct assegment
*newsegment
;
1106 newsegment
= assegment_new (type
, 1);
1107 newsegment
->as
[0] = asno
;
1109 newsegment
->next
= assegment
;
1110 aspath
->segments
= newsegment
;
1116 /* Add specified AS to the leftmost of aspath. */
1118 aspath_add_seq (struct aspath
*aspath
, as_t asno
)
1120 return aspath_add_one_as (aspath
, asno
, AS_SEQUENCE
);
1123 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1124 as2's leftmost AS is same return 1. */
1126 aspath_cmp_left (struct aspath
*aspath1
, struct aspath
*aspath2
)
1128 struct assegment
*seg1
= NULL
;
1129 struct assegment
*seg2
= NULL
;
1131 if (!(aspath1
&& aspath2
))
1134 seg1
= aspath1
->segments
;
1135 seg2
= aspath2
->segments
;
1137 /* find first non-confed segments for each */
1138 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1139 || (seg1
->type
== AS_CONFED_SET
)))
1142 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1143 || (seg2
->type
== AS_CONFED_SET
)))
1148 && (seg1
->type
== AS_SEQUENCE
) && (seg2
->type
== AS_SEQUENCE
)))
1151 if (seg1
->as
[0] == seg2
->as
[0])
1157 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1158 as2's leftmost AS is same return 1. (confederation as-path
1161 aspath_cmp_left_confed (struct aspath
*aspath1
, struct aspath
*aspath2
)
1163 if (! (aspath1
&& aspath2
) )
1166 if ( !(aspath1
->segments
&& aspath2
->segments
) )
1169 if ( (aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1170 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
) )
1173 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1179 /* Delete all leading AS_CONFED_SEQUENCE/SET segments from aspath.
1180 * See RFC3065, 6.1 c1 */
1182 aspath_delete_confed_seq (struct aspath
*aspath
)
1184 struct assegment
*seg
;
1186 if (!(aspath
&& aspath
->segments
))
1189 seg
= aspath
->segments
;
1191 /* "if the first path segment of the AS_PATH is
1192 * of type AS_CONFED_SEQUENCE,"
1194 if (aspath
->segments
->type
!= AS_CONFED_SEQUENCE
)
1197 /* "... that segment and any immediately following segments
1198 * of the type AS_CONFED_SET or AS_CONFED_SEQUENCE are removed
1199 * from the AS_PATH attribute,"
1202 (seg
->type
== AS_CONFED_SEQUENCE
|| seg
->type
== AS_CONFED_SET
))
1204 aspath
->segments
= seg
->next
;
1205 assegment_free (seg
);
1206 seg
= aspath
->segments
;
1208 aspath_str_update (aspath
);
1212 /* Add new AS number to the leftmost part of the aspath as
1213 AS_CONFED_SEQUENCE. */
1215 aspath_add_confed_seq (struct aspath
*aspath
, as_t asno
)
1217 return aspath_add_one_as (aspath
, asno
, AS_CONFED_SEQUENCE
);
1220 /* Add new as value to as path structure. */
1222 aspath_as_add (struct aspath
*as
, as_t asno
)
1224 struct assegment
*seg
= as
->segments
;
1226 /* Last segment search procedure. */
1227 while (seg
&& seg
->next
)
1233 assegment_append_asns (seg
, &asno
, 1);
1236 /* Add new as segment to the as path. */
1238 aspath_segment_add (struct aspath
*as
, int type
)
1240 struct assegment
*seg
= as
->segments
;
1241 struct assegment
*new = assegment_new (type
, 0);
1243 while (seg
&& seg
->next
)
1255 return aspath_parse (NULL
, 0);
1259 aspath_empty_get (void)
1261 struct aspath
*aspath
;
1263 aspath
= aspath_new ();
1264 aspath
->str
= aspath_make_str_count (aspath
);
1271 return ashash
->count
;
1275 Theoretically, one as path can have:
1277 One BGP packet size should be less than 4096.
1278 One BGP attribute size should be less than 4096 - BGP header size.
1279 One BGP aspath size should be less than 4096 - BGP header size -
1280 BGP mandantry attribute size.
1283 /* AS path string lexical token enum. */
1289 as_token_confed_seq_start
,
1290 as_token_confed_seq_end
,
1291 as_token_confed_set_start
,
1292 as_token_confed_set_end
,
1296 /* Return next token and point for string parse. */
1298 aspath_gettoken (const char *buf
, enum as_token
*token
, u_short
*asno
)
1300 const char *p
= buf
;
1302 /* Skip seperators (space for sequences, ',' for sets). */
1303 while (isspace ((int) *p
) || *p
== ',')
1306 /* Check the end of the string and type specify characters
1314 *token
= as_token_set_start
;
1319 *token
= as_token_set_end
;
1324 *token
= as_token_confed_seq_start
;
1329 *token
= as_token_confed_seq_end
;
1334 *token
= as_token_confed_set_start
;
1339 *token
= as_token_confed_set_end
;
1345 /* Check actual AS value. */
1346 if (isdigit ((int) *p
))
1350 *token
= as_token_asval
;
1353 while (isdigit ((int) *p
))
1356 asval
+= (*p
- '0');
1363 /* There is no match then return unknown token. */
1364 *token
= as_token_unknown
;
1369 aspath_str2aspath (const char *str
)
1371 enum as_token token
;
1374 struct aspath
*aspath
;
1377 aspath
= aspath_new ();
1379 /* We start default type as AS_SEQUENCE. */
1380 as_type
= AS_SEQUENCE
;
1383 while ((str
= aspath_gettoken (str
, &token
, &asno
)) != NULL
)
1387 case as_token_asval
:
1390 aspath_segment_add (aspath
, as_type
);
1393 aspath_as_add (aspath
, asno
);
1395 case as_token_set_start
:
1397 aspath_segment_add (aspath
, as_type
);
1400 case as_token_set_end
:
1401 as_type
= AS_SEQUENCE
;
1404 case as_token_confed_seq_start
:
1405 as_type
= AS_CONFED_SEQUENCE
;
1406 aspath_segment_add (aspath
, as_type
);
1409 case as_token_confed_seq_end
:
1410 as_type
= AS_SEQUENCE
;
1413 case as_token_confed_set_start
:
1414 as_type
= AS_CONFED_SET
;
1415 aspath_segment_add (aspath
, as_type
);
1418 case as_token_confed_set_end
:
1419 as_type
= AS_SEQUENCE
;
1422 case as_token_unknown
:
1424 aspath_free (aspath
);
1430 aspath
->str
= aspath_make_str_count (aspath
);
1435 /* Make hash value by raw aspath data. */
1437 aspath_key_make (struct aspath
*aspath
)
1439 unsigned int key
= 0;
1441 struct assegment
*seg
= aspath
->segments
;
1442 struct assegment
*prev
= NULL
;
1446 /* segment types should be part of the hash
1447 * otherwise seq(1) and set(1) will hash to same value
1449 if (!(prev
&& seg
->type
== AS_SEQUENCE
&& seg
->type
== prev
->type
))
1452 for (i
= 0; i
< seg
->length
; i
++)
1462 /* If two aspath have same value then return 1 else return 0 */
1464 aspath_cmp (void *arg1
, void *arg2
)
1466 struct assegment
*seg1
= ((struct aspath
*)arg1
)->segments
;
1467 struct assegment
*seg2
= ((struct aspath
*)arg2
)->segments
;
1469 while (seg1
|| seg2
)
1472 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
1474 if (seg1
->type
!= seg2
->type
)
1476 if (seg1
->length
!= seg2
->length
)
1478 for (i
= 0; i
< seg1
->length
; i
++)
1479 if (seg1
->as
[i
] != seg2
->as
[i
])
1487 /* AS path hash initialize. */
1491 ashash
= hash_create_size (32767, aspath_key_make
, aspath_cmp
);
1495 aspath_finish (void)
1500 stream_free (snmp_stream
);
1503 /* return and as path value */
1505 aspath_print (struct aspath
*as
)
1507 return (as
? as
->str
: NULL
);
1510 /* Printing functions */
1512 aspath_print_vty (struct vty
*vty
, struct aspath
*as
)
1514 vty_out (vty
, "%s", as
->str
);
1518 aspath_show_all_iterator (struct hash_backet
*backet
, struct vty
*vty
)
1522 as
= (struct aspath
*) backet
->data
;
1524 vty_out (vty
, "[%p:%u] (%ld) ", backet
, backet
->key
, as
->refcnt
);
1525 vty_out (vty
, "%s%s", as
->str
, VTY_NEWLINE
);
1528 /* Print all aspath and hash information. This function is used from
1529 `show ip bgp paths' command. */
1531 aspath_print_all_vty (struct vty
*vty
)
1533 hash_iterate (ashash
,
1534 (void (*) (struct hash_backet
*, void *))
1535 aspath_show_all_iterator
,