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. */
83 assegment_data_new (int num
)
85 return (XCALLOC (MTYPE_AS_SEG_DATA
, ASSEGMENT_DATA_SIZE (num
)));
89 assegment_data_free (as_t
*asdata
)
91 XFREE (MTYPE_AS_SEG_DATA
,asdata
);
94 /* Get a new segment. Note that 0 is an allowed length,
95 * and will result in a segment with no allocated data segment.
96 * the caller should immediately assign data to the segment, as the segment
97 * otherwise is not generally valid
99 static struct assegment
*
100 assegment_new (u_char type
, u_short length
)
102 struct assegment
*new;
104 new = XCALLOC (MTYPE_AS_SEG
, sizeof (struct assegment
));
107 new->as
= assegment_data_new (length
);
109 new->length
= length
;
116 assegment_free (struct assegment
*seg
)
122 XFREE (MTYPE_AS_SEG_DATA
, seg
->as
);
123 memset (seg
, 0xfe, sizeof(struct assegment
));
124 XFREE (MTYPE_AS_SEG
, seg
);
129 /* free entire chain of segments */
131 assegment_free_all (struct assegment
*seg
)
133 struct assegment
*prev
;
139 assegment_free (prev
);
143 /* Duplicate just the given assegment and its data */
144 static struct assegment
*
145 assegment_dup (struct assegment
*seg
)
147 struct assegment
*new;
149 new = assegment_new (seg
->type
, seg
->length
);
150 memcpy (new->as
, seg
->as
, ASSEGMENT_DATA_SIZE (new->length
) );
155 /* Duplicate entire chain of assegments, return the head */
156 static struct assegment
*
157 assegment_dup_all (struct assegment
*seg
)
159 struct assegment
*new = NULL
;
160 struct assegment
*head
= NULL
;
166 new->next
= assegment_dup (seg
);
170 head
= new = assegment_dup (seg
);
177 /* prepend the as number to given segment, given num of times */
178 static struct assegment
*
179 assegment_prepend_asns (struct assegment
*seg
, as_t asnum
, int num
)
186 if (num
>= AS_SEGMENT_MAX
)
187 return seg
; /* we don't do huge prepends */
189 newas
= assegment_data_new (seg
->length
+ num
);
194 for (i
= 0; i
< num
; i
++)
197 memcpy (newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE (seg
->length
));
198 XFREE (MTYPE_AS_SEG_DATA
, seg
->as
);
204 assegment_free_all (seg
);
208 /* append given array of as numbers to the segment */
209 static struct assegment
*
210 assegment_append_asns (struct assegment
*seg
, as_t
*asnos
, int num
)
214 newas
= XREALLOC (MTYPE_AS_SEG_DATA
, seg
->as
,
215 ASSEGMENT_DATA_SIZE (seg
->length
+ num
));
220 memcpy (seg
->as
+ seg
->length
, asnos
, ASSEGMENT_DATA_SIZE(num
));
225 assegment_free_all (seg
);
230 int_cmp (const void *p1
, const void *p2
)
232 const as_t
*as1
= p1
;
233 const as_t
*as2
= p2
;
235 return (*as1
== *as2
)
236 ? 0 : ( (*as1
> *as2
) ? 1 : -1);
239 /* normalise the segment.
240 * In particular, merge runs of AS_SEQUENCEs into one segment
241 * Internally, we do not care about the wire segment length limit, and
242 * we want each distinct AS_PATHs to have the exact same internal
243 * representation - eg, so that our hashing actually works..
245 static struct assegment
*
246 assegment_normalise (struct assegment
*head
)
248 struct assegment
*seg
= head
, *pin
;
249 struct assegment
*tmp
;
258 /* Sort values SET segments, for determinism in paths to aid
259 * creation of hash values / path comparisons
260 * and because it helps other lesser implementations ;)
262 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
)
263 qsort (seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
265 /* read ahead from the current, pinned segment while the segments
266 * are packable/mergeable. Append all following packable segments
267 * to the segment we have pinned and remove these appended
270 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
))
275 /* append the next sequence to the pinned sequence */
276 pin
= assegment_append_asns (pin
, seg
->as
, seg
->length
);
278 /* bypass the next sequence */
279 pin
->next
= seg
->next
;
281 /* get rid of the now referenceless segment */
282 assegment_free (tmp
);
291 static struct aspath
*
294 struct aspath
*aspath
;
296 aspath
= XMALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
297 memset (aspath
, 0, sizeof (struct aspath
));
301 /* Free AS path structure. */
303 aspath_free (struct aspath
*aspath
)
307 if (aspath
->segments
)
308 assegment_free_all (aspath
->segments
);
310 XFREE (MTYPE_AS_STR
, aspath
->str
);
311 XFREE (MTYPE_AS_PATH
, aspath
);
314 /* Unintern aspath from AS path bucket. */
316 aspath_unintern (struct aspath
*aspath
)
323 if (aspath
->refcnt
== 0)
325 /* This aspath must exist in aspath hash table. */
326 ret
= hash_release (ashash
, aspath
);
327 assert (ret
!= NULL
);
328 aspath_free (aspath
);
332 /* Return the start or end delimiters for a particular Segment type */
333 #define AS_SEG_START 0
336 aspath_delimiter_char (u_char type
, u_char which
)
344 } aspath_delim_char
[] =
346 { AS_SET
, '{', '}' },
347 { AS_CONFED_SET
, '[', ']' },
348 { AS_CONFED_SEQUENCE
, '(', ')' },
352 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++)
354 if (aspath_delim_char
[i
].type
== type
)
356 if (which
== AS_SEG_START
)
357 return aspath_delim_char
[i
].start
;
358 else if (which
== AS_SEG_END
)
359 return aspath_delim_char
[i
].end
;
365 /* countup asns from this segment and index onward */
367 assegment_count_asns (struct assegment
*seg
, int from
)
373 count
+= seg
->length
;
376 count
+= (seg
->length
- from
);
385 aspath_count_confeds (struct aspath
*aspath
)
388 struct assegment
*seg
= aspath
->segments
;
392 if (seg
->type
== AS_CONFED_SEQUENCE
)
393 count
+= seg
->length
;
394 else if (seg
->type
== AS_CONFED_SET
)
403 aspath_count_hops (struct aspath
*aspath
)
406 struct assegment
*seg
= aspath
->segments
;
410 if (seg
->type
== AS_SEQUENCE
)
411 count
+= seg
->length
;
412 else if (seg
->type
== AS_SET
)
421 aspath_size (struct aspath
*aspath
)
424 struct assegment
*seg
= aspath
->segments
;
428 size
+= ASSEGMENT_SIZE(seg
->length
);
434 /* Convert aspath structure to string expression. */
436 aspath_make_str_count (struct aspath
*as
)
438 struct assegment
*seg
;
446 str_buf
= XMALLOC (MTYPE_AS_STR
, 1);
453 /* ASN takes 5 chars at least, plus seperator, see below.
454 * If there is one differing segment type, we need an additional
455 * 2 chars for segment delimiters, and the final '\0'.
456 * Hopefully this is large enough to avoid hitting the realloc
457 * code below for most common sequences.
459 #define ASN_STR_LEN (5 + 1)
460 str_size
= MAX (assegment_count_asns (seg
, 0) * ASN_STR_LEN
+ 2 + 1,
461 ASPATH_STR_DEFAULT_LEN
);
462 str_buf
= XMALLOC (MTYPE_AS_STR
, str_size
);
469 /* Check AS type validity. Set seperator for segment */
477 case AS_CONFED_SEQUENCE
:
481 XFREE (MTYPE_AS_STR
, str_buf
);
485 /* We might need to increase str_buf, particularly if path has
486 * differing segments types, our initial guesstimate above will
487 * have been wrong. need 5 chars for ASN, a seperator each and
488 * potentially two segment delimiters, plus a space between each
489 * segment and trailing zero.
491 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
492 if ( (len
+ SEGMENT_STR_LEN(seg
)) > str_size
)
494 str_size
= len
+ SEGMENT_STR_LEN(seg
);
495 str_buf
= XREALLOC (MTYPE_AS_STR
, str_buf
, str_size
);
498 #undef SEGMENT_STR_LEN
500 if (seg
->type
!= AS_SEQUENCE
)
501 len
+= snprintf (str_buf
+ len
, str_size
- len
,
503 aspath_delimiter_char (seg
->type
, AS_SEG_START
));
505 /* write out the ASNs, with their seperators, bar the last one*/
506 for (i
= 0; i
< seg
->length
; i
++)
508 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%u", seg
->as
[i
]);
510 if (i
< (seg
->length
- 1))
511 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c", seperator
);
514 if (seg
->type
!= AS_SEQUENCE
)
515 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c",
516 aspath_delimiter_char (seg
->type
, AS_SEG_END
));
518 len
+= snprintf (str_buf
+ len
, str_size
- len
, " ");
523 assert (len
< str_size
);
531 aspath_str_update (struct aspath
*as
)
534 XFREE (MTYPE_AS_STR
, as
->str
);
535 as
->str
= aspath_make_str_count (as
);
538 /* Intern allocated AS path. */
540 aspath_intern (struct aspath
*aspath
)
544 /* Assert this AS path structure is not interned. */
545 assert (aspath
->refcnt
== 0);
547 /* Check AS path hash. */
548 find
= hash_get (ashash
, aspath
, hash_alloc_intern
);
551 aspath_free (aspath
);
556 find
->str
= aspath_make_str_count (find
);
561 /* Duplicate aspath structure. Created same aspath structure but
562 reference count and AS path string is cleared. */
564 aspath_dup (struct aspath
*aspath
)
568 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
570 if (aspath
->segments
)
571 new->segments
= assegment_dup_all (aspath
->segments
);
573 new->segments
= NULL
;
575 new->str
= aspath_make_str_count (aspath
);
581 aspath_hash_alloc (void *arg
)
583 struct aspath
*aspath
;
585 /* New aspath strucutre is needed. */
586 aspath
= aspath_dup (arg
);
588 /* Malformed AS path value. */
591 aspath_free (aspath
);
598 /* parse as-segment byte stream in struct assegment */
599 static struct assegment
*
600 assegments_parse (struct stream
*s
, size_t length
)
602 struct assegment_header segh
;
603 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
606 /* empty aspath (ie iBGP or somesuch) */
611 if ( (STREAM_READABLE(s
) < length
)
612 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
613 || (length
% AS_VALUE_SIZE
))
616 while ( (STREAM_READABLE(s
) > AS_HEADER_SIZE
)
621 /* softly softly, get the header first on its own */
622 segh
.type
= stream_getc (s
);
623 segh
.length
= stream_getc (s
);
626 if ( ((bytes
+ ASSEGMENT_SIZE(segh
.length
)) > length
)
627 /* 1771bis 4.3b: seg length contains one or more */
628 || (segh
.length
== 0)
629 /* Paranoia in case someone changes type of segment length */
630 || ((sizeof segh
.length
> 1) && segh
.length
> AS_SEGMENT_MAX
))
633 assegment_free_all (head
);
637 /* now its safe to trust lengths */
638 seg
= assegment_new (segh
.type
, segh
.length
);
642 else /* it's the first segment */
645 for (i
= 0; i
< segh
.length
; i
++)
646 seg
->as
[i
] = stream_getw (s
);
648 bytes
+= ASSEGMENT_SIZE(segh
.length
);
653 return assegment_normalise (head
);
656 /* AS path parse function. pnt is a pointer to byte stream and length
657 is length of byte stream. If there is same AS path in the the AS
658 path hash then return it else make new AS path structure. */
660 aspath_parse (struct stream
*s
, size_t length
)
665 /* If length is odd it's malformed AS path. */
666 if (length
% AS_VALUE_SIZE
)
669 as
.segments
= assegments_parse (s
, length
);
671 /* If already same aspath exist then return it. */
672 find
= hash_get (ashash
, &as
, aspath_hash_alloc
);
674 /* aspath_hash_alloc dupes segments too. that probably could be
677 assegment_free_all (as
.segments
);
687 assegment_data_put (struct stream
*s
, as_t
*as
, int num
)
690 assert (num
<= AS_SEGMENT_MAX
);
692 for (i
= 0; i
< num
; i
++)
693 stream_putw (s
, as
[i
]);
697 assegment_header_put (struct stream
*s
, u_char type
, int length
)
700 assert (length
<= AS_SEGMENT_MAX
);
701 stream_putc (s
, type
);
702 lenp
= stream_get_endp (s
);
703 stream_putc (s
, length
);
707 /* write aspath data to stream */
709 aspath_put (struct stream
*s
, struct aspath
*as
)
711 struct assegment
*seg
= as
->segments
;
713 if (!seg
|| seg
->length
== 0)
718 while (seg
&& (ASSEGMENT_LEN (seg
) <= STREAM_WRITEABLE(s
)))
723 /* Overlength segments have to be split up */
724 while ( (seg
->length
- written
) > AS_SEGMENT_MAX
)
726 assegment_header_put (s
, seg
->type
, AS_SEGMENT_MAX
);
727 assegment_data_put (s
, seg
->as
, AS_SEGMENT_MAX
);
728 written
+= AS_SEGMENT_MAX
;
731 /* write the final segment, probably is also the first */
732 lenp
= assegment_header_put (s
, seg
->type
, seg
->length
- written
);
733 assegment_data_put (s
, (seg
->as
+ written
), seg
->length
- written
);
735 /* Sequence-type segments can be 'packed' together
736 * Case of a segment which was overlength and split up
737 * will be missed here, but that doesn't matter.
739 if (seg
->next
&& ASSEGMENTS_PACKABLE (seg
, seg
->next
))
741 /* NB: We should never normally get here given we
742 * normalise aspath data when parse them. However, better
743 * safe than sorry. We potentially could call
744 * assegment_normalise here instead, but it's cheaper and
745 * easier to do it on the fly here rather than go through
746 * the segment list twice every time we write out
750 /* Next segment's data can fit in this one */
751 assegment_data_put (s
, seg
->next
->as
, seg
->next
->length
);
753 /* update the length of the segment header */
754 stream_putc_at (s
, lenp
,
755 seg
->length
- written
+ seg
->next
->length
);
756 seg
= seg
->next
->next
; /* skip to past next */
764 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
765 * We have no way to manage the storage, so we use a static stream
766 * wrapper around aspath_put.
769 aspath_snmp_pathseg (struct aspath
*as
, size_t *varlen
)
771 #define SNMP_PATHSEG_MAX 1024
772 static struct stream
*s
= NULL
;
775 s
= stream_new (SNMP_PATHSEG_MAX
);
786 *varlen
= stream_get_endp (s
);
787 return stream_pnt(s
);
790 #define min(A,B) ((A) < (B) ? (A) : (B))
792 static struct assegment
*
793 aspath_aggregate_as_set_add (struct aspath
*aspath
, struct assegment
*asset
,
798 /* If this is first AS set member, create new as-set segment. */
801 asset
= assegment_new (AS_SET
, 1);
802 if (! aspath
->segments
)
803 aspath
->segments
= asset
;
806 struct assegment
*seg
= aspath
->segments
;
811 asset
->type
= AS_SET
;
817 /* Check this AS value already exists or not. */
818 for (i
= 0; i
< asset
->length
; i
++)
819 if (asset
->as
[i
] == as
)
823 asset
->as
= XREALLOC (MTYPE_AS_SEG_DATA
, asset
->as
,
824 asset
->length
* AS_VALUE_SIZE
);
825 asset
->as
[asset
->length
- 1] = as
;
832 /* Modify as1 using as2 for aggregation. */
834 aspath_aggregate (struct aspath
*as1
, struct aspath
*as2
)
840 struct assegment
*seg1
= as1
->segments
;
841 struct assegment
*seg2
= as2
->segments
;
842 struct aspath
*aspath
;
843 struct assegment
*asset
;
850 /* First of all check common leading sequence. */
853 /* Check segment type. */
854 if (seg1
->type
!= seg2
->type
)
857 /* Minimum segment length. */
858 minlen
= min (seg1
->length
, seg2
->length
);
860 for (match
= 0; match
< minlen
; match
++)
861 if (seg1
->as
[match
] != seg2
->as
[match
])
867 aspath
= aspath_new ();
868 aspath
->segments
= assegment_new (seg1
->type
, 0);
869 aspath
->segments
= assegment_append_asns (aspath
->segments
,
873 if (match
!= minlen
|| match
!= seg1
->length
874 || seg1
->length
!= seg2
->length
)
882 aspath
= aspath_new();
884 /* Make as-set using rest of all information. */
888 for (i
= from
; i
< seg1
->length
; i
++)
889 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg1
->as
[i
]);
898 for (i
= from
; i
< seg2
->length
; i
++)
899 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg2
->as
[i
]);
905 assegment_normalise (aspath
->segments
);
906 aspath_str_update (aspath
);
910 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
911 attribute, check the leftmost AS number in the AS_PATH attribute is
912 or not the peer's AS number. */
914 aspath_firstas_check (struct aspath
*aspath
, as_t asno
)
916 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
920 && (aspath
->segments
->type
== AS_SEQUENCE
)
921 && (aspath
->segments
->as
[0] == asno
))
927 /* AS path loop check. If aspath contains asno then return 1. */
929 aspath_loop_check (struct aspath
*aspath
, as_t asno
)
931 struct assegment
*seg
;
934 if ( (aspath
== NULL
) || (aspath
->segments
) )
937 seg
= aspath
->segments
;
943 for (i
= 0; i
< seg
->length
; i
++)
944 if (seg
->as
[i
] == asno
)
952 /* When all of AS path is private AS return 1. */
954 aspath_private_as_check (struct aspath
*aspath
)
956 struct assegment
*seg
;
958 if ( !(aspath
&& aspath
->segments
) )
961 seg
= aspath
->segments
;
967 for (i
= 0; i
< seg
->length
; i
++)
969 if ( (seg
->as
[i
] < BGP_PRIVATE_AS_MIN
)
970 || (seg
->as
[i
] > BGP_PRIVATE_AS_MAX
) )
978 /* Merge as1 to as2. as2 should be uninterned aspath. */
979 static struct aspath
*
980 aspath_merge (struct aspath
*as1
, struct aspath
*as2
)
982 struct assegment
*last
, *new;
987 last
= new = assegment_dup_all (as1
->segments
);
989 /* find the last valid segment */
990 while (last
&& last
->next
)
993 last
->next
= as2
->segments
;
995 aspath_str_update (as2
);
999 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1001 aspath_prepend (struct aspath
*as1
, struct aspath
*as2
)
1003 struct assegment
*seg1
;
1004 struct assegment
*seg2
;
1009 seg1
= as1
->segments
;
1010 seg2
= as2
->segments
;
1012 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1015 as2
->segments
= assegment_dup_all (as1
->segments
);
1016 aspath_str_update (as2
);
1020 /* If as1 is empty AS, no prepending to do. */
1024 /* find the tail as1's segment chain. */
1025 while (seg1
&& seg1
->next
)
1028 /* Compare last segment type of as1 and first segment type of as2. */
1029 if (seg1
->type
!= seg2
->type
)
1030 return aspath_merge (as1
, as2
);
1032 if (seg1
->type
== AS_SEQUENCE
)
1034 /* We have two chains of segments, as1->segments and seg2,
1035 * and we have to attach them together, merging the attaching
1036 * segments together into one.
1038 * 1. dupe as1->segments onto head of as2
1039 * 2. merge seg2's asns onto last segment of this new chain
1040 * 3. attach chain after seg2
1043 /* dupe as1 onto as2's head */
1044 seg1
= as2
->segments
= assegment_dup_all (as1
->segments
);
1046 /* refind the tail of as2, reusing seg1 */
1047 while (seg1
&& seg1
->next
)
1050 /* merge the old head, seg2, into tail, seg1 */
1051 seg1
= assegment_append_asns (seg1
, seg2
->as
, seg2
->length
);
1053 /* bypass the merged seg2, and attach any chain after it to
1054 * chain descending from as2's head
1056 seg1
->next
= seg2
->next
;
1058 /* seg2 is now referenceless and useless*/
1059 assegment_free (seg2
);
1061 /* we've now prepended as1's segment chain to as2, merging
1062 * the inbetween AS_SEQUENCE of seg2 in the process
1064 aspath_str_update (as2
);
1069 /* AS_SET merge code is needed at here. */
1070 return aspath_merge (as1
, as2
);
1072 /* XXX: Ermmm, what if as1 has multiple segments?? */
1077 /* Add specified AS to the leftmost of aspath. */
1078 static struct aspath
*
1079 aspath_add_one_as (struct aspath
*aspath
, as_t asno
, u_char type
)
1081 struct assegment
*assegment
= aspath
->segments
;
1083 /* In case of empty aspath. */
1084 if (assegment
== NULL
|| assegment
->length
== 0)
1086 aspath
->segments
= assegment_new (type
, 1);
1087 aspath
->segments
->as
[0] = asno
;
1090 assegment_free (assegment
);
1095 if (assegment
->type
== type
)
1096 aspath
->segments
= assegment_prepend_asns (aspath
->segments
, asno
, 1);
1099 /* create new segment
1100 * push it onto head of aspath's segment chain
1102 struct assegment
*newsegment
;
1104 newsegment
= assegment_new (type
, 1);
1105 newsegment
->as
[0] = asno
;
1107 newsegment
->next
= assegment
;
1108 aspath
->segments
= newsegment
;
1114 /* Add specified AS to the leftmost of aspath. */
1116 aspath_add_seq (struct aspath
*aspath
, as_t asno
)
1118 return aspath_add_one_as (aspath
, asno
, AS_SEQUENCE
);
1121 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1122 as2's leftmost AS is same return 1. */
1124 aspath_cmp_left (struct aspath
*aspath1
, struct aspath
*aspath2
)
1126 struct assegment
*seg1
= NULL
;
1127 struct assegment
*seg2
= NULL
;
1129 if (!(aspath1
&& aspath2
))
1132 seg1
= aspath1
->segments
;
1133 seg2
= aspath2
->segments
;
1135 /* find first non-confed segments for each */
1136 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1137 || (seg1
->type
== AS_CONFED_SET
)))
1140 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1141 || (seg2
->type
== AS_CONFED_SET
)))
1146 && (seg1
->type
== AS_SEQUENCE
) && (seg2
->type
== AS_SEQUENCE
)))
1149 if (seg1
->as
[0] == seg2
->as
[0])
1155 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1156 as2's leftmost AS is same return 1. (confederation as-path
1159 aspath_cmp_left_confed (struct aspath
*aspath1
, struct aspath
*aspath2
)
1161 if (! (aspath1
&& aspath2
) )
1164 if ( !(aspath1
->segments
&& aspath2
->segments
) )
1167 if ( (aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1168 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
) )
1171 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1177 /* Delete all leading AS_CONFED_SEQUENCE/SET segments from aspath.
1178 * See RFC3065, 6.1 c1 */
1180 aspath_delete_confed_seq (struct aspath
*aspath
)
1182 struct assegment
*seg
;
1184 if (!(aspath
&& aspath
->segments
))
1187 seg
= aspath
->segments
;
1189 /* "if the first path segment of the AS_PATH is
1190 * of type AS_CONFED_SEQUENCE,"
1192 if (aspath
->segments
->type
!= AS_CONFED_SEQUENCE
)
1195 /* "... that segment and any immediately following segments
1196 * of the type AS_CONFED_SET or AS_CONFED_SEQUENCE are removed
1197 * from the AS_PATH attribute,"
1200 (seg
->type
== AS_CONFED_SEQUENCE
|| seg
->type
== AS_CONFED_SET
))
1202 aspath
->segments
= seg
->next
;
1203 assegment_free (seg
);
1204 seg
= aspath
->segments
;
1206 aspath_str_update (aspath
);
1210 /* Add new AS number to the leftmost part of the aspath as
1211 AS_CONFED_SEQUENCE. */
1213 aspath_add_confed_seq (struct aspath
*aspath
, as_t asno
)
1215 return aspath_add_one_as (aspath
, asno
, AS_CONFED_SEQUENCE
);
1218 /* Add new as value to as path structure. */
1220 aspath_as_add (struct aspath
*as
, as_t asno
)
1222 struct assegment
*seg
= as
->segments
;
1224 /* Last segment search procedure. */
1225 while (seg
&& seg
->next
)
1231 assegment_append_asns (seg
, &asno
, 1);
1234 /* Add new as segment to the as path. */
1236 aspath_segment_add (struct aspath
*as
, int type
)
1238 struct assegment
*seg
= as
->segments
;
1239 struct assegment
*new = assegment_new (type
, 0);
1241 while (seg
&& seg
->next
)
1253 return aspath_parse (NULL
, 0);
1257 aspath_empty_get (void)
1259 struct aspath
*aspath
;
1261 aspath
= aspath_new ();
1262 aspath
->str
= aspath_make_str_count (aspath
);
1269 return ashash
->count
;
1273 Theoretically, one as path can have:
1275 One BGP packet size should be less than 4096.
1276 One BGP attribute size should be less than 4096 - BGP header size.
1277 One BGP aspath size should be less than 4096 - BGP header size -
1278 BGP mandantry attribute size.
1281 /* AS path string lexical token enum. */
1287 as_token_confed_seq_start
,
1288 as_token_confed_seq_end
,
1289 as_token_confed_set_start
,
1290 as_token_confed_set_end
,
1294 /* Return next token and point for string parse. */
1296 aspath_gettoken (const char *buf
, enum as_token
*token
, u_short
*asno
)
1298 const char *p
= buf
;
1300 /* Skip seperators (space for sequences, ',' for sets). */
1301 while (isspace ((int) *p
) || *p
== ',')
1304 /* Check the end of the string and type specify characters
1312 *token
= as_token_set_start
;
1317 *token
= as_token_set_end
;
1322 *token
= as_token_confed_seq_start
;
1327 *token
= as_token_confed_seq_end
;
1332 *token
= as_token_confed_set_start
;
1337 *token
= as_token_confed_set_end
;
1343 /* Check actual AS value. */
1344 if (isdigit ((int) *p
))
1348 *token
= as_token_asval
;
1351 while (isdigit ((int) *p
))
1354 asval
+= (*p
- '0');
1361 /* There is no match then return unknown token. */
1362 *token
= as_token_unknown
;
1367 aspath_str2aspath (const char *str
)
1369 enum as_token token
;
1372 struct aspath
*aspath
;
1375 aspath
= aspath_new ();
1377 /* We start default type as AS_SEQUENCE. */
1378 as_type
= AS_SEQUENCE
;
1381 while ((str
= aspath_gettoken (str
, &token
, &asno
)) != NULL
)
1385 case as_token_asval
:
1388 aspath_segment_add (aspath
, as_type
);
1391 aspath_as_add (aspath
, asno
);
1393 case as_token_set_start
:
1395 aspath_segment_add (aspath
, as_type
);
1398 case as_token_set_end
:
1399 as_type
= AS_SEQUENCE
;
1402 case as_token_confed_seq_start
:
1403 as_type
= AS_CONFED_SEQUENCE
;
1404 aspath_segment_add (aspath
, as_type
);
1407 case as_token_confed_seq_end
:
1408 as_type
= AS_SEQUENCE
;
1411 case as_token_confed_set_start
:
1412 as_type
= AS_CONFED_SET
;
1413 aspath_segment_add (aspath
, as_type
);
1416 case as_token_confed_set_end
:
1417 as_type
= AS_SEQUENCE
;
1420 case as_token_unknown
:
1422 aspath_free (aspath
);
1428 aspath
->str
= aspath_make_str_count (aspath
);
1433 /* Make hash value by raw aspath data. */
1435 aspath_key_make (struct aspath
*aspath
)
1437 unsigned int key
= 0;
1439 struct assegment
*seg
= aspath
->segments
;
1440 struct assegment
*prev
= NULL
;
1444 /* segment types should be part of the hash
1445 * otherwise seq(1) and set(1) will hash to same value
1447 if (!(prev
&& seg
->type
== AS_SEQUENCE
&& seg
->type
== prev
->type
))
1450 for (i
= 0; i
< seg
->length
; i
++)
1460 /* If two aspath have same value then return 1 else return 0 */
1462 aspath_cmp (void *arg1
, void *arg2
)
1464 struct assegment
*seg1
= ((struct aspath
*)arg1
)->segments
;
1465 struct assegment
*seg2
= ((struct aspath
*)arg2
)->segments
;
1467 while (seg1
|| seg2
)
1470 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
1472 if (seg1
->type
!= seg2
->type
)
1474 if (seg1
->length
!= seg2
->length
)
1476 for (i
= 0; i
< seg1
->length
; i
++)
1477 if (seg1
->as
[i
] != seg2
->as
[i
])
1485 /* AS path hash initialize. */
1489 ashash
= hash_create_size (32767, aspath_key_make
, aspath_cmp
);
1492 /* return and as path value */
1494 aspath_print (struct aspath
*as
)
1496 return (as
? as
->str
: NULL
);
1499 /* Printing functions */
1501 aspath_print_vty (struct vty
*vty
, struct aspath
*as
)
1503 vty_out (vty
, "%s", as
->str
);
1507 aspath_show_all_iterator (struct hash_backet
*backet
, struct vty
*vty
)
1511 as
= (struct aspath
*) backet
->data
;
1513 vty_out (vty
, "[%p:%u] (%ld) ", backet
, backet
->key
, as
->refcnt
);
1514 vty_out (vty
, "%s%s", as
->str
, VTY_NEWLINE
);
1517 /* Print all aspath and hash information. This function is used from
1518 `show ip bgp paths' command. */
1520 aspath_print_all_vty (struct vty
*vty
)
1522 hash_iterate (ashash
,
1523 (void (*) (struct hash_backet
*, void *))
1524 aspath_show_all_iterator
,