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 /* Return highest public ASN in path */
439 aspath_highest (struct aspath
*aspath
)
441 struct assegment
*seg
= aspath
->segments
;
447 for (i
= 0; i
< seg
->length
; i
++)
448 if (seg
->as
[i
] > highest
449 && (seg
->as
[i
] < BGP_PRIVATE_AS_MIN
450 || seg
->as
[i
] > BGP_PRIVATE_AS_MAX
))
451 highest
= seg
->as
[i
];
457 /* Convert aspath structure to string expression. */
459 aspath_make_str_count (struct aspath
*as
)
461 struct assegment
*seg
;
469 str_buf
= XMALLOC (MTYPE_AS_STR
, 1);
476 /* ASN takes 5 chars at least, plus seperator, see below.
477 * If there is one differing segment type, we need an additional
478 * 2 chars for segment delimiters, and the final '\0'.
479 * Hopefully this is large enough to avoid hitting the realloc
480 * code below for most common sequences.
482 #define ASN_STR_LEN (5 + 1)
483 str_size
= MAX (assegment_count_asns (seg
, 0) * ASN_STR_LEN
+ 2 + 1,
484 ASPATH_STR_DEFAULT_LEN
);
485 str_buf
= XMALLOC (MTYPE_AS_STR
, str_size
);
492 /* Check AS type validity. Set seperator for segment */
500 case AS_CONFED_SEQUENCE
:
504 XFREE (MTYPE_AS_STR
, str_buf
);
508 /* We might need to increase str_buf, particularly if path has
509 * differing segments types, our initial guesstimate above will
510 * have been wrong. need 5 chars for ASN, a seperator each and
511 * potentially two segment delimiters, plus a space between each
512 * segment and trailing zero.
514 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
515 if ( (len
+ SEGMENT_STR_LEN(seg
)) > str_size
)
517 str_size
= len
+ SEGMENT_STR_LEN(seg
);
518 str_buf
= XREALLOC (MTYPE_AS_STR
, str_buf
, str_size
);
521 #undef SEGMENT_STR_LEN
523 if (seg
->type
!= AS_SEQUENCE
)
524 len
+= snprintf (str_buf
+ len
, str_size
- len
,
526 aspath_delimiter_char (seg
->type
, AS_SEG_START
));
528 /* write out the ASNs, with their seperators, bar the last one*/
529 for (i
= 0; i
< seg
->length
; i
++)
531 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%u", seg
->as
[i
]);
533 if (i
< (seg
->length
- 1))
534 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c", seperator
);
537 if (seg
->type
!= AS_SEQUENCE
)
538 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c",
539 aspath_delimiter_char (seg
->type
, AS_SEG_END
));
541 len
+= snprintf (str_buf
+ len
, str_size
- len
, " ");
546 assert (len
< str_size
);
554 aspath_str_update (struct aspath
*as
)
557 XFREE (MTYPE_AS_STR
, as
->str
);
558 as
->str
= aspath_make_str_count (as
);
561 /* Intern allocated AS path. */
563 aspath_intern (struct aspath
*aspath
)
567 /* Assert this AS path structure is not interned. */
568 assert (aspath
->refcnt
== 0);
570 /* Check AS path hash. */
571 find
= hash_get (ashash
, aspath
, hash_alloc_intern
);
574 aspath_free (aspath
);
579 find
->str
= aspath_make_str_count (find
);
584 /* Duplicate aspath structure. Created same aspath structure but
585 reference count and AS path string is cleared. */
587 aspath_dup (struct aspath
*aspath
)
591 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
593 if (aspath
->segments
)
594 new->segments
= assegment_dup_all (aspath
->segments
);
596 new->segments
= NULL
;
598 new->str
= aspath_make_str_count (aspath
);
604 aspath_hash_alloc (void *arg
)
606 struct aspath
*aspath
;
608 /* New aspath strucutre is needed. */
609 aspath
= aspath_dup (arg
);
611 /* Malformed AS path value. */
614 aspath_free (aspath
);
621 /* parse as-segment byte stream in struct assegment */
622 static struct assegment
*
623 assegments_parse (struct stream
*s
, size_t length
)
625 struct assegment_header segh
;
626 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
629 /* empty aspath (ie iBGP or somesuch) */
634 if ( (STREAM_READABLE(s
) < length
)
635 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
636 || (length
% AS_VALUE_SIZE
))
639 while ( (STREAM_READABLE(s
) > AS_HEADER_SIZE
)
644 /* softly softly, get the header first on its own */
645 segh
.type
= stream_getc (s
);
646 segh
.length
= stream_getc (s
);
649 if ( ((bytes
+ ASSEGMENT_SIZE(segh
.length
)) > length
)
650 /* 1771bis 4.3b: seg length contains one or more */
651 || (segh
.length
== 0)
652 /* Paranoia in case someone changes type of segment length */
653 || ((sizeof segh
.length
> 1) && segh
.length
> AS_SEGMENT_MAX
))
656 assegment_free_all (head
);
660 /* now its safe to trust lengths */
661 seg
= assegment_new (segh
.type
, segh
.length
);
665 else /* it's the first segment */
668 for (i
= 0; i
< segh
.length
; i
++)
669 seg
->as
[i
] = stream_getw (s
);
671 bytes
+= ASSEGMENT_SIZE(segh
.length
);
676 return assegment_normalise (head
);
679 /* AS path parse function. pnt is a pointer to byte stream and length
680 is length of byte stream. If there is same AS path in the the AS
681 path hash then return it else make new AS path structure. */
683 aspath_parse (struct stream
*s
, size_t length
)
688 /* If length is odd it's malformed AS path. */
689 if (length
% AS_VALUE_SIZE
)
692 as
.segments
= assegments_parse (s
, length
);
694 /* If already same aspath exist then return it. */
695 find
= hash_get (ashash
, &as
, aspath_hash_alloc
);
697 /* aspath_hash_alloc dupes segments too. that probably could be
700 assegment_free_all (as
.segments
);
710 assegment_data_put (struct stream
*s
, as_t
*as
, int num
)
713 assert (num
<= AS_SEGMENT_MAX
);
715 for (i
= 0; i
< num
; i
++)
716 stream_putw (s
, as
[i
]);
720 assegment_header_put (struct stream
*s
, u_char type
, int length
)
723 assert (length
<= AS_SEGMENT_MAX
);
724 stream_putc (s
, type
);
725 lenp
= stream_get_endp (s
);
726 stream_putc (s
, length
);
730 /* write aspath data to stream */
732 aspath_put (struct stream
*s
, struct aspath
*as
)
734 struct assegment
*seg
= as
->segments
;
736 if (!seg
|| seg
->length
== 0)
741 while (seg
&& (ASSEGMENT_LEN (seg
) <= STREAM_WRITEABLE(s
)))
746 /* Overlength segments have to be split up */
747 while ( (seg
->length
- written
) > AS_SEGMENT_MAX
)
749 assegment_header_put (s
, seg
->type
, AS_SEGMENT_MAX
);
750 assegment_data_put (s
, seg
->as
, AS_SEGMENT_MAX
);
751 written
+= AS_SEGMENT_MAX
;
754 /* write the final segment, probably is also the first */
755 lenp
= assegment_header_put (s
, seg
->type
, seg
->length
- written
);
756 assegment_data_put (s
, (seg
->as
+ written
), seg
->length
- written
);
758 /* Sequence-type segments can be 'packed' together
759 * Case of a segment which was overlength and split up
760 * will be missed here, but that doesn't matter.
762 if (seg
->next
&& ASSEGMENTS_PACKABLE (seg
, seg
->next
))
764 /* NB: We should never normally get here given we
765 * normalise aspath data when parse them. However, better
766 * safe than sorry. We potentially could call
767 * assegment_normalise here instead, but it's cheaper and
768 * easier to do it on the fly here rather than go through
769 * the segment list twice every time we write out
773 /* Next segment's data can fit in this one */
774 assegment_data_put (s
, seg
->next
->as
, seg
->next
->length
);
776 /* update the length of the segment header */
777 stream_putc_at (s
, lenp
,
778 seg
->length
- written
+ seg
->next
->length
);
779 seg
= seg
->next
->next
; /* skip to past next */
787 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
788 * We have no way to manage the storage, so we use a static stream
789 * wrapper around aspath_put.
792 aspath_snmp_pathseg (struct aspath
*as
, size_t *varlen
)
794 #define SNMP_PATHSEG_MAX 1024
797 snmp_stream
= stream_new (SNMP_PATHSEG_MAX
);
799 stream_reset (snmp_stream
);
806 aspath_put (snmp_stream
, as
);
808 *varlen
= stream_get_endp (snmp_stream
);
809 return stream_pnt(snmp_stream
);
812 #define min(A,B) ((A) < (B) ? (A) : (B))
814 static struct assegment
*
815 aspath_aggregate_as_set_add (struct aspath
*aspath
, struct assegment
*asset
,
820 /* If this is first AS set member, create new as-set segment. */
823 asset
= assegment_new (AS_SET
, 1);
824 if (! aspath
->segments
)
825 aspath
->segments
= asset
;
828 struct assegment
*seg
= aspath
->segments
;
833 asset
->type
= AS_SET
;
839 /* Check this AS value already exists or not. */
840 for (i
= 0; i
< asset
->length
; i
++)
841 if (asset
->as
[i
] == as
)
845 asset
->as
= XREALLOC (MTYPE_AS_SEG_DATA
, asset
->as
,
846 asset
->length
* AS_VALUE_SIZE
);
847 asset
->as
[asset
->length
- 1] = as
;
854 /* Modify as1 using as2 for aggregation. */
856 aspath_aggregate (struct aspath
*as1
, struct aspath
*as2
)
862 struct assegment
*seg1
= as1
->segments
;
863 struct assegment
*seg2
= as2
->segments
;
864 struct aspath
*aspath
;
865 struct assegment
*asset
;
872 /* First of all check common leading sequence. */
875 /* Check segment type. */
876 if (seg1
->type
!= seg2
->type
)
879 /* Minimum segment length. */
880 minlen
= min (seg1
->length
, seg2
->length
);
882 for (match
= 0; match
< minlen
; match
++)
883 if (seg1
->as
[match
] != seg2
->as
[match
])
889 aspath
= aspath_new ();
890 aspath
->segments
= assegment_new (seg1
->type
, 0);
891 aspath
->segments
= assegment_append_asns (aspath
->segments
,
895 if (match
!= minlen
|| match
!= seg1
->length
896 || seg1
->length
!= seg2
->length
)
904 aspath
= aspath_new();
906 /* Make as-set using rest of all information. */
910 for (i
= from
; i
< seg1
->length
; i
++)
911 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg1
->as
[i
]);
920 for (i
= from
; i
< seg2
->length
; i
++)
921 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg2
->as
[i
]);
927 assegment_normalise (aspath
->segments
);
928 aspath_str_update (aspath
);
932 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
933 attribute, check the leftmost AS number in the AS_PATH attribute is
934 or not the peer's AS number. */
936 aspath_firstas_check (struct aspath
*aspath
, as_t asno
)
938 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
942 && (aspath
->segments
->type
== AS_SEQUENCE
)
943 && (aspath
->segments
->as
[0] == asno
))
949 /* AS path loop check. If aspath contains asno then return >= 1. */
951 aspath_loop_check (struct aspath
*aspath
, as_t asno
)
953 struct assegment
*seg
;
956 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
959 seg
= aspath
->segments
;
965 for (i
= 0; i
< seg
->length
; i
++)
966 if (seg
->as
[i
] == asno
)
974 /* When all of AS path is private AS return 1. */
976 aspath_private_as_check (struct aspath
*aspath
)
978 struct assegment
*seg
;
980 if ( !(aspath
&& aspath
->segments
) )
983 seg
= aspath
->segments
;
989 for (i
= 0; i
< seg
->length
; i
++)
991 if ( (seg
->as
[i
] < BGP_PRIVATE_AS_MIN
)
992 || (seg
->as
[i
] > BGP_PRIVATE_AS_MAX
) )
1000 /* Merge as1 to as2. as2 should be uninterned aspath. */
1001 static struct aspath
*
1002 aspath_merge (struct aspath
*as1
, struct aspath
*as2
)
1004 struct assegment
*last
, *new;
1009 last
= new = assegment_dup_all (as1
->segments
);
1011 /* find the last valid segment */
1012 while (last
&& last
->next
)
1015 last
->next
= as2
->segments
;
1016 as2
->segments
= new;
1017 aspath_str_update (as2
);
1021 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1023 aspath_prepend (struct aspath
*as1
, struct aspath
*as2
)
1025 struct assegment
*seg1
;
1026 struct assegment
*seg2
;
1031 seg1
= as1
->segments
;
1032 seg2
= as2
->segments
;
1034 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1037 as2
->segments
= assegment_dup_all (as1
->segments
);
1038 aspath_str_update (as2
);
1042 /* If as1 is empty AS, no prepending to do. */
1046 /* find the tail as1's segment chain. */
1047 while (seg1
&& seg1
->next
)
1050 /* Compare last segment type of as1 and first segment type of as2. */
1051 if (seg1
->type
!= seg2
->type
)
1052 return aspath_merge (as1
, as2
);
1054 if (seg1
->type
== AS_SEQUENCE
)
1056 /* We have two chains of segments, as1->segments and seg2,
1057 * and we have to attach them together, merging the attaching
1058 * segments together into one.
1060 * 1. dupe as1->segments onto head of as2
1061 * 2. merge seg2's asns onto last segment of this new chain
1062 * 3. attach chain after seg2
1065 /* dupe as1 onto as2's head */
1066 seg1
= as2
->segments
= assegment_dup_all (as1
->segments
);
1068 /* refind the tail of as2, reusing seg1 */
1069 while (seg1
&& seg1
->next
)
1072 /* merge the old head, seg2, into tail, seg1 */
1073 seg1
= assegment_append_asns (seg1
, seg2
->as
, seg2
->length
);
1075 /* bypass the merged seg2, and attach any chain after it to
1076 * chain descending from as2's head
1078 seg1
->next
= seg2
->next
;
1080 /* seg2 is now referenceless and useless*/
1081 assegment_free (seg2
);
1083 /* we've now prepended as1's segment chain to as2, merging
1084 * the inbetween AS_SEQUENCE of seg2 in the process
1086 aspath_str_update (as2
);
1091 /* AS_SET merge code is needed at here. */
1092 return aspath_merge (as1
, as2
);
1094 /* XXX: Ermmm, what if as1 has multiple segments?? */
1099 /* Add specified AS to the leftmost of aspath. */
1100 static struct aspath
*
1101 aspath_add_one_as (struct aspath
*aspath
, as_t asno
, u_char type
)
1103 struct assegment
*assegment
= aspath
->segments
;
1105 /* In case of empty aspath. */
1106 if (assegment
== NULL
|| assegment
->length
== 0)
1108 aspath
->segments
= assegment_new (type
, 1);
1109 aspath
->segments
->as
[0] = asno
;
1112 assegment_free (assegment
);
1117 if (assegment
->type
== type
)
1118 aspath
->segments
= assegment_prepend_asns (aspath
->segments
, asno
, 1);
1121 /* create new segment
1122 * push it onto head of aspath's segment chain
1124 struct assegment
*newsegment
;
1126 newsegment
= assegment_new (type
, 1);
1127 newsegment
->as
[0] = asno
;
1129 newsegment
->next
= assegment
;
1130 aspath
->segments
= newsegment
;
1136 /* Add specified AS to the leftmost of aspath. */
1138 aspath_add_seq (struct aspath
*aspath
, as_t asno
)
1140 return aspath_add_one_as (aspath
, asno
, AS_SEQUENCE
);
1143 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1144 as2's leftmost AS is same return 1. */
1146 aspath_cmp_left (struct aspath
*aspath1
, struct aspath
*aspath2
)
1148 struct assegment
*seg1
= NULL
;
1149 struct assegment
*seg2
= NULL
;
1151 if (!(aspath1
&& aspath2
))
1154 seg1
= aspath1
->segments
;
1155 seg2
= aspath2
->segments
;
1157 /* find first non-confed segments for each */
1158 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1159 || (seg1
->type
== AS_CONFED_SET
)))
1162 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1163 || (seg2
->type
== AS_CONFED_SET
)))
1168 && (seg1
->type
== AS_SEQUENCE
) && (seg2
->type
== AS_SEQUENCE
)))
1171 if (seg1
->as
[0] == seg2
->as
[0])
1177 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1178 as2's leftmost AS is same return 1. (confederation as-path
1181 aspath_cmp_left_confed (struct aspath
*aspath1
, struct aspath
*aspath2
)
1183 if (! (aspath1
&& aspath2
) )
1186 if ( !(aspath1
->segments
&& aspath2
->segments
) )
1189 if ( (aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1190 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
) )
1193 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1199 /* Delete all leading AS_CONFED_SEQUENCE/SET segments from aspath.
1200 * See RFC3065, 6.1 c1 */
1202 aspath_delete_confed_seq (struct aspath
*aspath
)
1204 struct assegment
*seg
;
1206 if (!(aspath
&& aspath
->segments
))
1209 seg
= aspath
->segments
;
1211 /* "if the first path segment of the AS_PATH is
1212 * of type AS_CONFED_SEQUENCE,"
1214 if (aspath
->segments
->type
!= AS_CONFED_SEQUENCE
)
1217 /* "... that segment and any immediately following segments
1218 * of the type AS_CONFED_SET or AS_CONFED_SEQUENCE are removed
1219 * from the AS_PATH attribute,"
1222 (seg
->type
== AS_CONFED_SEQUENCE
|| seg
->type
== AS_CONFED_SET
))
1224 aspath
->segments
= seg
->next
;
1225 assegment_free (seg
);
1226 seg
= aspath
->segments
;
1228 aspath_str_update (aspath
);
1232 /* Add new AS number to the leftmost part of the aspath as
1233 AS_CONFED_SEQUENCE. */
1235 aspath_add_confed_seq (struct aspath
*aspath
, as_t asno
)
1237 return aspath_add_one_as (aspath
, asno
, AS_CONFED_SEQUENCE
);
1240 /* Add new as value to as path structure. */
1242 aspath_as_add (struct aspath
*as
, as_t asno
)
1244 struct assegment
*seg
= as
->segments
;
1246 /* Last segment search procedure. */
1247 while (seg
&& seg
->next
)
1253 assegment_append_asns (seg
, &asno
, 1);
1256 /* Add new as segment to the as path. */
1258 aspath_segment_add (struct aspath
*as
, int type
)
1260 struct assegment
*seg
= as
->segments
;
1261 struct assegment
*new = assegment_new (type
, 0);
1263 while (seg
&& seg
->next
)
1275 return aspath_parse (NULL
, 0);
1279 aspath_empty_get (void)
1281 struct aspath
*aspath
;
1283 aspath
= aspath_new ();
1284 aspath
->str
= aspath_make_str_count (aspath
);
1291 return ashash
->count
;
1295 Theoretically, one as path can have:
1297 One BGP packet size should be less than 4096.
1298 One BGP attribute size should be less than 4096 - BGP header size.
1299 One BGP aspath size should be less than 4096 - BGP header size -
1300 BGP mandantry attribute size.
1303 /* AS path string lexical token enum. */
1309 as_token_confed_seq_start
,
1310 as_token_confed_seq_end
,
1311 as_token_confed_set_start
,
1312 as_token_confed_set_end
,
1316 /* Return next token and point for string parse. */
1318 aspath_gettoken (const char *buf
, enum as_token
*token
, u_short
*asno
)
1320 const char *p
= buf
;
1322 /* Skip seperators (space for sequences, ',' for sets). */
1323 while (isspace ((int) *p
) || *p
== ',')
1326 /* Check the end of the string and type specify characters
1333 *token
= as_token_set_start
;
1337 *token
= as_token_set_end
;
1341 *token
= as_token_confed_seq_start
;
1345 *token
= as_token_confed_seq_end
;
1349 *token
= as_token_confed_set_start
;
1353 *token
= as_token_confed_set_end
;
1358 /* Check actual AS value. */
1359 if (isdigit ((int) *p
))
1363 *token
= as_token_asval
;
1366 while (isdigit ((int) *p
))
1369 asval
+= (*p
- '0');
1376 /* There is no match then return unknown token. */
1377 *token
= as_token_unknown
;
1382 aspath_str2aspath (const char *str
)
1384 enum as_token token
= as_token_unknown
;
1387 struct aspath
*aspath
;
1390 aspath
= aspath_new ();
1392 /* We start default type as AS_SEQUENCE. */
1393 as_type
= AS_SEQUENCE
;
1396 while ((str
= aspath_gettoken (str
, &token
, &asno
)) != NULL
)
1400 case as_token_asval
:
1403 aspath_segment_add (aspath
, as_type
);
1406 aspath_as_add (aspath
, asno
);
1408 case as_token_set_start
:
1410 aspath_segment_add (aspath
, as_type
);
1413 case as_token_set_end
:
1414 as_type
= AS_SEQUENCE
;
1417 case as_token_confed_seq_start
:
1418 as_type
= AS_CONFED_SEQUENCE
;
1419 aspath_segment_add (aspath
, as_type
);
1422 case as_token_confed_seq_end
:
1423 as_type
= AS_SEQUENCE
;
1426 case as_token_confed_set_start
:
1427 as_type
= AS_CONFED_SET
;
1428 aspath_segment_add (aspath
, as_type
);
1431 case as_token_confed_set_end
:
1432 as_type
= AS_SEQUENCE
;
1435 case as_token_unknown
:
1437 aspath_free (aspath
);
1442 aspath
->str
= aspath_make_str_count (aspath
);
1447 /* Make hash value by raw aspath data. */
1449 aspath_key_make (struct aspath
*aspath
)
1451 unsigned int key
= 0;
1453 struct assegment
*seg
= aspath
->segments
;
1454 struct assegment
*prev
= NULL
;
1458 /* segment types should be part of the hash
1459 * otherwise seq(1) and set(1) will hash to same value
1461 if (!(prev
&& seg
->type
== AS_SEQUENCE
&& seg
->type
== prev
->type
))
1464 for (i
= 0; i
< seg
->length
; i
++)
1474 /* If two aspath have same value then return 1 else return 0 */
1476 aspath_cmp (void *arg1
, void *arg2
)
1478 struct assegment
*seg1
= ((struct aspath
*)arg1
)->segments
;
1479 struct assegment
*seg2
= ((struct aspath
*)arg2
)->segments
;
1481 while (seg1
|| seg2
)
1484 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
1486 if (seg1
->type
!= seg2
->type
)
1488 if (seg1
->length
!= seg2
->length
)
1490 for (i
= 0; i
< seg1
->length
; i
++)
1491 if (seg1
->as
[i
] != seg2
->as
[i
])
1499 /* AS path hash initialize. */
1503 ashash
= hash_create_size (32767, aspath_key_make
, aspath_cmp
);
1507 aspath_finish (void)
1512 stream_free (snmp_stream
);
1515 /* return and as path value */
1517 aspath_print (struct aspath
*as
)
1519 return (as
? as
->str
: NULL
);
1522 /* Printing functions */
1524 aspath_print_vty (struct vty
*vty
, const char *format
, struct aspath
*as
)
1527 vty_out (vty
, format
, as
->str
);
1531 aspath_show_all_iterator (struct hash_backet
*backet
, struct vty
*vty
)
1535 as
= (struct aspath
*) backet
->data
;
1537 vty_out (vty
, "[%p:%u] (%ld) ", backet
, backet
->key
, as
->refcnt
);
1538 vty_out (vty
, "%s%s", as
->str
, VTY_NEWLINE
);
1541 /* Print all aspath and hash information. This function is used from
1542 `show ip bgp paths' command. */
1544 aspath_print_all_vty (struct vty
*vty
)
1546 hash_iterate (ashash
,
1547 (void (*) (struct hash_backet
*, void *))
1548 aspath_show_all_iterator
,