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
36 #include "bgpd/bgpd.h"
37 #include "bgpd/bgp_aspath.h"
38 #include "bgpd/bgp_debug.h"
39 #include "bgpd/bgp_attr.h"
41 /* Attr. Flags and Attr. Type Code. */
42 #define AS_HEADER_SIZE 2
44 /* Now FOUR octets are used for AS value. */
45 #define AS_VALUE_SIZE sizeof (as_t)
46 /* This is the old one */
47 #define AS16_VALUE_SIZE sizeof (as16_t)
49 /* Maximum protocol segment length value */
50 #define AS_SEGMENT_MAX 255
52 /* The following length and size macros relate specifically to Quagga's
53 * internal representation of AS-Segments, not per se to the on-wire
54 * sizes and lengths. At present (200508) they sort of match, however
55 * the ONLY functions which should now about the on-wire syntax are
56 * aspath_put, assegment_put and assegment_parse.
58 * aspath_put returns bytes written, the only definitive record of
59 * size of wire-format attribute..
62 /* Calculated size in bytes of ASN segment data to hold N ASN's */
63 #define ASSEGMENT_DATA_SIZE(N,S) \
64 ((N) * ( (S) ? AS_VALUE_SIZE : AS16_VALUE_SIZE) )
66 /* Calculated size of segment struct to hold N ASN's */
67 #define ASSEGMENT_SIZE(N,S) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N,S))
69 /* AS segment octet length. */
70 #define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S)
72 /* AS_SEQUENCE segments can be packed together */
73 /* Can the types of X and Y be considered for packing? */
74 #define ASSEGMENT_TYPES_PACKABLE(X,Y) \
75 ( ((X)->type == (Y)->type) \
76 && ((X)->type == AS_SEQUENCE))
77 /* Types and length of X,Y suitable for packing? */
78 #define ASSEGMENTS_PACKABLE(X,Y) \
79 ( ASSEGMENT_TYPES_PACKABLE( (X), (Y)) \
80 && ( ((X)->length + (Y)->length) <= AS_SEGMENT_MAX ) )
82 /* As segment header - the on-wire representation
83 * NOT the internal representation!
85 struct assegment_header
91 /* Hash for aspath. This is the top level structure of AS path. */
92 static struct hash
*ashash
;
94 /* Stream for SNMP. See aspath_snmp_pathseg */
95 static struct stream
*snmp_stream
;
97 /* Callers are required to initialize the memory */
99 assegment_data_new (int num
)
101 return (XMALLOC (MTYPE_AS_SEG_DATA
, ASSEGMENT_DATA_SIZE (num
, 1)));
105 assegment_data_free (as_t
*asdata
)
107 XFREE (MTYPE_AS_SEG_DATA
, asdata
);
110 const char *aspath_segment_type_str
[] = {
114 "as-confed-sequence",
118 /* Get a new segment. Note that 0 is an allowed length,
119 * and will result in a segment with no allocated data segment.
120 * the caller should immediately assign data to the segment, as the segment
121 * otherwise is not generally valid
123 static struct assegment
*
124 assegment_new (u_char type
, u_short length
)
126 struct assegment
*new;
128 new = XCALLOC (MTYPE_AS_SEG
, sizeof (struct assegment
));
131 new->as
= assegment_data_new (length
);
133 new->length
= length
;
140 assegment_free (struct assegment
*seg
)
146 assegment_data_free (seg
->as
);
147 memset (seg
, 0xfe, sizeof(struct assegment
));
148 XFREE (MTYPE_AS_SEG
, seg
);
153 /* free entire chain of segments */
155 assegment_free_all (struct assegment
*seg
)
157 struct assegment
*prev
;
163 assegment_free (prev
);
167 /* Duplicate just the given assegment and its data */
168 static struct assegment
*
169 assegment_dup (struct assegment
*seg
)
171 struct assegment
*new;
173 new = assegment_new (seg
->type
, seg
->length
);
174 memcpy (new->as
, seg
->as
, ASSEGMENT_DATA_SIZE (new->length
, 1) );
179 /* Duplicate entire chain of assegments, return the head */
180 static struct assegment
*
181 assegment_dup_all (struct assegment
*seg
)
183 struct assegment
*new = NULL
;
184 struct assegment
*head
= NULL
;
190 new->next
= assegment_dup (seg
);
194 head
= new = assegment_dup (seg
);
201 /* prepend the as number to given segment, given num of times */
202 static struct assegment
*
203 assegment_prepend_asns (struct assegment
*seg
, as_t asnum
, int num
)
211 if (num
>= AS_SEGMENT_MAX
)
212 return seg
; /* we don't do huge prepends */
214 if ((newas
= assegment_data_new (seg
->length
+ num
)) == NULL
)
217 for (i
= 0; i
< num
; i
++)
220 memcpy (newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE (seg
->length
, 1));
221 assegment_data_free (seg
->as
);
228 /* append given array of as numbers to the segment */
229 static struct assegment
*
230 assegment_append_asns (struct assegment
*seg
, as_t
*asnos
, int num
)
234 newas
= XREALLOC (MTYPE_AS_SEG_DATA
, seg
->as
,
235 ASSEGMENT_DATA_SIZE (seg
->length
+ num
, 1));
240 memcpy (seg
->as
+ seg
->length
, asnos
, ASSEGMENT_DATA_SIZE(num
, 1));
245 assegment_free_all (seg
);
250 int_cmp (const void *p1
, const void *p2
)
252 const as_t
*as1
= p1
;
253 const as_t
*as2
= p2
;
255 return (*as1
== *as2
)
256 ? 0 : ( (*as1
> *as2
) ? 1 : -1);
259 /* normalise the segment.
260 * In particular, merge runs of AS_SEQUENCEs into one segment
261 * Internally, we do not care about the wire segment length limit, and
262 * we want each distinct AS_PATHs to have the exact same internal
263 * representation - eg, so that our hashing actually works..
265 static struct assegment
*
266 assegment_normalise (struct assegment
*head
)
268 struct assegment
*seg
= head
, *pin
;
269 struct assegment
*tmp
;
278 /* Sort values SET segments, for determinism in paths to aid
279 * creation of hash values / path comparisons
280 * and because it helps other lesser implementations ;)
282 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
)
287 qsort (seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
290 for (i
=1; i
< seg
->length
; i
++)
292 if (seg
->as
[tail
] == seg
->as
[i
])
297 seg
->as
[tail
] = seg
->as
[i
];
299 /* seg->length can be 0.. */
301 seg
->length
= tail
+ 1;
304 /* read ahead from the current, pinned segment while the segments
305 * are packable/mergeable. Append all following packable segments
306 * to the segment we have pinned and remove these appended
309 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
))
314 /* append the next sequence to the pinned sequence */
315 pin
= assegment_append_asns (pin
, seg
->as
, seg
->length
);
317 /* bypass the next sequence */
318 pin
->next
= seg
->next
;
320 /* get rid of the now referenceless segment */
321 assegment_free (tmp
);
330 static struct aspath
*
333 return XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
336 /* Free AS path structure. */
338 aspath_free (struct aspath
*aspath
)
342 if (aspath
->segments
)
343 assegment_free_all (aspath
->segments
);
345 XFREE (MTYPE_AS_STR
, aspath
->str
);
349 json_object_free(aspath
->json
);
353 XFREE (MTYPE_AS_PATH
, aspath
);
356 /* Unintern aspath from AS path bucket. */
358 aspath_unintern (struct aspath
**aspath
)
361 struct aspath
*asp
= *aspath
;
366 if (asp
->refcnt
== 0)
368 /* This aspath must exist in aspath hash table. */
369 ret
= hash_release (ashash
, asp
);
370 assert (ret
!= NULL
);
376 /* Return the start or end delimiters for a particular Segment type */
377 #define AS_SEG_START 0
380 aspath_delimiter_char (u_char type
, u_char which
)
388 } aspath_delim_char
[] =
390 { AS_SET
, '{', '}' },
391 { AS_CONFED_SET
, '[', ']' },
392 { AS_CONFED_SEQUENCE
, '(', ')' },
396 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++)
398 if (aspath_delim_char
[i
].type
== type
)
400 if (which
== AS_SEG_START
)
401 return aspath_delim_char
[i
].start
;
402 else if (which
== AS_SEG_END
)
403 return aspath_delim_char
[i
].end
;
409 /* countup asns from this segment and index onward */
411 assegment_count_asns (struct assegment
*seg
, int from
)
417 count
+= seg
->length
;
420 count
+= (seg
->length
- from
);
429 aspath_count_confeds (struct aspath
*aspath
)
432 struct assegment
*seg
= aspath
->segments
;
436 if (seg
->type
== AS_CONFED_SEQUENCE
)
437 count
+= seg
->length
;
438 else if (seg
->type
== AS_CONFED_SET
)
447 aspath_count_hops (const struct aspath
*aspath
)
450 struct assegment
*seg
= aspath
->segments
;
454 if (seg
->type
== AS_SEQUENCE
)
455 count
+= seg
->length
;
456 else if (seg
->type
== AS_SET
)
464 /* Estimate size aspath /might/ take if encoded into an
467 * This is a quick estimate, not definitive! aspath_put()
468 * may return a different number!!
471 aspath_size (struct aspath
*aspath
)
474 struct assegment
*seg
= aspath
->segments
;
478 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
484 /* Return highest public ASN in path */
486 aspath_highest (struct aspath
*aspath
)
488 struct assegment
*seg
= aspath
->segments
;
494 for (i
= 0; i
< seg
->length
; i
++)
495 if (seg
->as
[i
] > highest
&& !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
496 highest
= seg
->as
[i
];
502 /* Return the left-most ASN in path */
504 aspath_leftmost (struct aspath
*aspath
)
506 struct assegment
*seg
= aspath
->segments
;
509 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
510 leftmost
= seg
->as
[0];
515 /* Return 1 if there are any 4-byte ASes in the path */
517 aspath_has_as4 (struct aspath
*aspath
)
519 struct assegment
*seg
= aspath
->segments
;
524 for (i
= 0; i
< seg
->length
; i
++)
525 if (seg
->as
[i
] > BGP_AS_MAX
)
532 /* Convert aspath structure to string expression. */
534 aspath_make_str_count (struct aspath
*as
)
536 struct assegment
*seg
;
540 json_object
*jaspath_segments
= NULL
;
541 json_object
*jseg
= NULL
;
542 json_object
*jseg_list
= NULL
;
544 as
->json
= json_object_new_object();
545 jaspath_segments
= json_object_new_array();
550 json_object_string_add(as
->json
, "string", "Local");
551 json_object_object_add(as
->json
, "segments", jaspath_segments
);
552 json_object_int_add(as
->json
, "length", 0);
553 as
->str
= XMALLOC (MTYPE_AS_STR
, 1);
561 /* ASN takes 5 to 10 chars plus seperator, see below.
562 * If there is one differing segment type, we need an additional
563 * 2 chars for segment delimiters, and the final '\0'.
564 * Hopefully this is large enough to avoid hitting the realloc
565 * code below for most common sequences.
567 * This was changed to 10 after the well-known BGP assertion, which
568 * had hit some parts of the Internet in May of 2009.
570 #define ASN_STR_LEN (10 + 1)
571 str_size
= MAX (assegment_count_asns (seg
, 0) * ASN_STR_LEN
+ 2 + 1,
572 ASPATH_STR_DEFAULT_LEN
);
573 str_buf
= XMALLOC (MTYPE_AS_STR
, str_size
);
580 /* Check AS type validity. Set seperator for segment */
588 case AS_CONFED_SEQUENCE
:
592 XFREE (MTYPE_AS_STR
, str_buf
);
595 json_object_free(as
->json
);
600 /* We might need to increase str_buf, particularly if path has
601 * differing segments types, our initial guesstimate above will
602 * have been wrong. Need 10 chars for ASN, a seperator each and
603 * potentially two segment delimiters, plus a space between each
604 * segment and trailing zero.
606 * This definitely didn't work with the value of 5 bytes and
609 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
610 if ( (len
+ SEGMENT_STR_LEN(seg
)) > str_size
)
612 str_size
= len
+ SEGMENT_STR_LEN(seg
);
613 str_buf
= XREALLOC (MTYPE_AS_STR
, str_buf
, str_size
);
616 #undef SEGMENT_STR_LEN
618 if (seg
->type
!= AS_SEQUENCE
)
619 len
+= snprintf (str_buf
+ len
, str_size
- len
,
621 aspath_delimiter_char (seg
->type
, AS_SEG_START
));
623 jseg_list
= json_object_new_array();
625 /* write out the ASNs, with their seperators, bar the last one*/
626 for (i
= 0; i
< seg
->length
; i
++)
628 json_object_array_add(jseg_list
, json_object_new_int(seg
->as
[i
]));
630 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%u", seg
->as
[i
]);
632 if (i
< (seg
->length
- 1))
633 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c", seperator
);
636 jseg
= json_object_new_object();
637 json_object_string_add(jseg
, "type", aspath_segment_type_str
[seg
->type
]);
638 json_object_object_add(jseg
, "list", jseg_list
);
639 json_object_array_add(jaspath_segments
, jseg
);
641 if (seg
->type
!= AS_SEQUENCE
)
642 len
+= snprintf (str_buf
+ len
, str_size
- len
, "%c",
643 aspath_delimiter_char (seg
->type
, AS_SEG_END
));
645 len
+= snprintf (str_buf
+ len
, str_size
- len
, " ");
650 assert (len
< str_size
);
656 json_object_string_add(as
->json
, "string", str_buf
);
657 json_object_object_add(as
->json
, "segments", jaspath_segments
);
658 json_object_int_add(as
->json
, "length", aspath_count_hops (as
));
663 aspath_str_update (struct aspath
*as
)
666 XFREE (MTYPE_AS_STR
, as
->str
);
670 json_object_free(as
->json
);
674 aspath_make_str_count (as
);
677 /* Intern allocated AS path. */
679 aspath_intern (struct aspath
*aspath
)
683 /* Assert this AS path structure is not interned and has the string
684 representation built. */
685 assert (aspath
->refcnt
== 0);
686 assert (aspath
->str
);
688 /* Check AS path hash. */
689 find
= hash_get (ashash
, aspath
, hash_alloc_intern
);
691 aspath_free (aspath
);
698 /* Duplicate aspath structure. Created same aspath structure but
699 reference count and AS path string is cleared. */
701 aspath_dup (struct aspath
*aspath
)
703 unsigned short buflen
= aspath
->str_len
+ 1;
706 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
709 if (aspath
->segments
)
710 new->segments
= assegment_dup_all (aspath
->segments
);
715 new->str
= XMALLOC (MTYPE_AS_STR
, buflen
);
716 new->str_len
= aspath
->str_len
;
718 /* copy the string data */
719 if (aspath
->str_len
> 0)
720 memcpy (new->str
, aspath
->str
, buflen
);
728 aspath_hash_alloc (void *arg
)
730 const struct aspath
*aspath
= arg
;
733 /* Malformed AS path value. */
734 assert (aspath
->str
);
736 /* New aspath structure is needed. */
737 new = XMALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
739 /* Reuse segments and string representation */
741 new->segments
= aspath
->segments
;
742 new->str
= aspath
->str
;
743 new->str_len
= aspath
->str_len
;
744 new->json
= aspath
->json
;
749 /* parse as-segment byte stream in struct assegment */
751 assegments_parse (struct stream
*s
, size_t length
,
752 struct assegment
**result
, int use32bit
)
754 struct assegment_header segh
;
755 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
758 /* empty aspath (ie iBGP or somesuch) */
762 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
763 zlog_debug ("[AS4SEG] Parse aspath segment: got total byte length %lu",
764 (unsigned long) length
);
766 if ((STREAM_READABLE(s
) < length
)
767 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
768 || (length
% AS16_VALUE_SIZE
))
771 while (bytes
< length
)
776 if ((length
- bytes
) <= AS_HEADER_SIZE
)
779 assegment_free_all (head
);
783 /* softly softly, get the header first on its own */
784 segh
.type
= stream_getc (s
);
785 segh
.length
= stream_getc (s
);
787 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
789 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
790 zlog_debug ("[AS4SEG] Parse aspath segment: got type %d, length %d",
791 segh
.type
, segh
.length
);
794 if ( ((bytes
+ seg_size
) > length
)
795 /* 1771bis 4.3b: seg length contains one or more */
796 || (segh
.length
== 0)
797 /* Paranoia in case someone changes type of segment length.
798 * Shift both values by 0x10 to make the comparison operate
799 * on more, than 8 bits (otherwise it's a warning, bug #564).
801 || ((sizeof segh
.length
> 1)
802 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
)))
805 assegment_free_all (head
);
813 case AS_CONFED_SEQUENCE
:
818 assegment_free_all (head
);
822 /* now its safe to trust lengths */
823 seg
= assegment_new (segh
.type
, segh
.length
);
827 else /* it's the first segment */
830 for (i
= 0; i
< segh
.length
; i
++)
831 seg
->as
[i
] = (use32bit
) ? stream_getl (s
) : stream_getw (s
);
835 if (BGP_DEBUG (as4
, AS4_SEGMENT
))
836 zlog_debug ("[AS4SEG] Parse aspath segment: Bytes now: %lu",
837 (unsigned long) bytes
);
842 *result
= assegment_normalise (head
);
846 /* AS path parse function. pnt is a pointer to byte stream and length
847 is length of byte stream. If there is same AS path in the the AS
848 path hash then return it else make new AS path structure.
850 On error NULL is returned.
853 aspath_parse (struct stream
*s
, size_t length
, int use32bit
)
858 /* If length is odd it's malformed AS path. */
859 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
860 * otherwise its malformed when length is larger than 2 and (length-2)
861 * is not dividable by 4.
862 * But... this time we're lazy
864 if (length
% AS16_VALUE_SIZE
)
867 memset (&as
, 0, sizeof (struct aspath
));
868 if (assegments_parse (s
, length
, &as
.segments
, use32bit
) < 0)
871 /* If already same aspath exist then return it. */
872 find
= hash_get (ashash
, &as
, aspath_hash_alloc
);
874 /* bug! should not happen, let the daemon crash below */
877 /* if the aspath was already hashed free temporary memory. */
880 assegment_free_all (as
.segments
);
881 /* aspath_key_make() always updates the string */
882 XFREE (MTYPE_AS_STR
, as
.str
);
885 json_object_free(as
.json
);
896 assegment_data_put (struct stream
*s
, as_t
*as
, int num
, int use32bit
)
899 assert (num
<= AS_SEGMENT_MAX
);
901 for (i
= 0; i
< num
; i
++)
903 stream_putl (s
, as
[i
]);
906 if ( as
[i
] <= BGP_AS_MAX
)
907 stream_putw(s
, as
[i
]);
909 stream_putw(s
, BGP_AS_TRANS
);
914 assegment_header_put (struct stream
*s
, u_char type
, int length
)
917 assert (length
<= AS_SEGMENT_MAX
);
918 stream_putc (s
, type
);
919 lenp
= stream_get_endp (s
);
920 stream_putc (s
, length
);
924 /* write aspath data to stream */
926 aspath_put (struct stream
*s
, struct aspath
*as
, int use32bit
)
928 struct assegment
*seg
= as
->segments
;
931 if (!seg
|| seg
->length
== 0)
937 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
938 * At the moment, we would write out a partial aspath, and our peer
939 * will complain and drop the session :-/
941 * The general assumption here is that many things tested will
942 * never happen. And, in real live, up to now, they have not.
944 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
) <= STREAM_WRITEABLE(s
)))
946 struct assegment
*next
= seg
->next
;
951 /* Overlength segments have to be split up */
952 while ( (seg
->length
- written
) > AS_SEGMENT_MAX
)
954 assegment_header_put (s
, seg
->type
, AS_SEGMENT_MAX
);
955 assegment_data_put (s
, seg
->as
, AS_SEGMENT_MAX
, use32bit
);
956 written
+= AS_SEGMENT_MAX
;
957 bytes
+= ASSEGMENT_SIZE (written
, use32bit
);
960 /* write the final segment, probably is also the first */
961 lenp
= assegment_header_put (s
, seg
->type
, seg
->length
- written
);
962 assegment_data_put (s
, (seg
->as
+ written
), seg
->length
- written
,
965 /* Sequence-type segments can be 'packed' together
966 * Case of a segment which was overlength and split up
967 * will be missed here, but that doesn't matter.
969 while (next
&& ASSEGMENTS_PACKABLE (seg
, next
))
971 /* NB: We should never normally get here given we
972 * normalise aspath data when parse them. However, better
973 * safe than sorry. We potentially could call
974 * assegment_normalise here instead, but it's cheaper and
975 * easier to do it on the fly here rather than go through
976 * the segment list twice every time we write out
980 /* Next segment's data can fit in this one */
981 assegment_data_put (s
, next
->as
, next
->length
, use32bit
);
983 /* update the length of the segment header */
984 stream_putc_at (s
, lenp
, seg
->length
- written
+ next
->length
);
985 asns_packed
+= next
->length
;
990 bytes
+= ASSEGMENT_SIZE (seg
->length
- written
+ asns_packed
,
998 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
999 * We have no way to manage the storage, so we use a static stream
1000 * wrapper around aspath_put.
1003 aspath_snmp_pathseg (struct aspath
*as
, size_t *varlen
)
1005 #define SNMP_PATHSEG_MAX 1024
1008 snmp_stream
= stream_new (SNMP_PATHSEG_MAX
);
1010 stream_reset (snmp_stream
);
1017 aspath_put (snmp_stream
, as
, 0); /* use 16 bit for now here */
1019 *varlen
= stream_get_endp (snmp_stream
);
1020 return stream_pnt(snmp_stream
);
1023 #define min(A,B) ((A) < (B) ? (A) : (B))
1025 static struct assegment
*
1026 aspath_aggregate_as_set_add (struct aspath
*aspath
, struct assegment
*asset
,
1031 /* If this is first AS set member, create new as-set segment. */
1034 asset
= assegment_new (AS_SET
, 1);
1035 if (! aspath
->segments
)
1036 aspath
->segments
= asset
;
1039 struct assegment
*seg
= aspath
->segments
;
1044 asset
->type
= AS_SET
;
1050 /* Check this AS value already exists or not. */
1051 for (i
= 0; i
< asset
->length
; i
++)
1052 if (asset
->as
[i
] == as
)
1056 asset
->as
= XREALLOC (MTYPE_AS_SEG_DATA
, asset
->as
,
1057 asset
->length
* AS_VALUE_SIZE
);
1058 asset
->as
[asset
->length
- 1] = as
;
1065 /* Modify as1 using as2 for aggregation. */
1067 aspath_aggregate (struct aspath
*as1
, struct aspath
*as2
)
1073 struct assegment
*seg1
= as1
->segments
;
1074 struct assegment
*seg2
= as2
->segments
;
1075 struct aspath
*aspath
= NULL
;
1076 struct assegment
*asset
= NULL
;
1077 struct assegment
*prevseg
= NULL
;
1079 /* First of all check common leading sequence. */
1080 while (seg1
&& seg2
)
1082 /* Check segment type. */
1083 if (seg1
->type
!= seg2
->type
)
1086 /* Minimum segment length. */
1087 minlen
= min (seg1
->length
, seg2
->length
);
1089 for (match
= 0; match
< minlen
; match
++)
1090 if (seg1
->as
[match
] != seg2
->as
[match
])
1095 struct assegment
*seg
= assegment_new (seg1
->type
, 0);
1097 seg
= assegment_append_asns (seg
, seg1
->as
, match
);
1101 aspath
= aspath_new ();
1102 aspath
->segments
= seg
;
1105 prevseg
->next
= seg
;
1110 if (match
!= minlen
|| match
!= seg1
->length
1111 || seg1
->length
!= seg2
->length
)
1113 /* We are moving on to the next segment to reset match */
1122 aspath
= aspath_new();
1124 /* Make as-set using rest of all information. */
1128 for (i
= from
; i
< seg1
->length
; i
++)
1129 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg1
->as
[i
]);
1138 for (i
= from
; i
< seg2
->length
; i
++)
1139 asset
= aspath_aggregate_as_set_add (aspath
, asset
, seg2
->as
[i
]);
1145 assegment_normalise (aspath
->segments
);
1146 aspath_str_update (aspath
);
1150 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1151 attribute, check the leftmost AS number in the AS_PATH attribute is
1152 or not the peer's AS number. */
1154 aspath_firstas_check (struct aspath
*aspath
, as_t asno
)
1156 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
1159 if (aspath
->segments
1160 && (aspath
->segments
->type
== AS_SEQUENCE
)
1161 && (aspath
->segments
->as
[0] == asno
))
1168 aspath_get_first_as (struct aspath
*aspath
)
1170 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1173 return aspath
->segments
->as
[0];
1177 aspath_get_last_as (struct aspath
*aspath
)
1180 unsigned int last_as
= 0;
1181 const struct assegment
*seg
;
1183 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1186 seg
= aspath
->segments
;
1190 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1191 for (i
= 0; i
< seg
->length
; i
++)
1192 last_as
= seg
->as
[i
];
1199 /* AS path loop check. If aspath contains asno then return >= 1. */
1201 aspath_loop_check (struct aspath
*aspath
, as_t asno
)
1203 struct assegment
*seg
;
1206 if ( (aspath
== NULL
) || (aspath
->segments
== NULL
) )
1209 seg
= aspath
->segments
;
1215 for (i
= 0; i
< seg
->length
; i
++)
1216 if (seg
->as
[i
] == asno
)
1224 /* When all of AS path is private AS return 1. */
1226 aspath_private_as_check (struct aspath
*aspath
)
1228 struct assegment
*seg
;
1230 if ( !(aspath
&& aspath
->segments
) )
1233 seg
= aspath
->segments
;
1239 for (i
= 0; i
< seg
->length
; i
++)
1241 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1249 /* Return True if the entire ASPATH consist of the specified ASN */
1251 aspath_single_asn_check (struct aspath
*aspath
, as_t asn
)
1253 struct assegment
*seg
;
1255 if ( !(aspath
&& aspath
->segments
) )
1258 seg
= aspath
->segments
;
1264 for (i
= 0; i
< seg
->length
; i
++)
1266 if (seg
->as
[i
] != asn
)
1274 /* Replace all instances of the target ASN with our own ASN */
1276 aspath_replace_specific_asn (struct aspath
*aspath
, as_t target_asn
,
1280 struct assegment
*seg
;
1282 new = aspath_dup(aspath
);
1283 seg
= new->segments
;
1289 for (i
= 0; i
< seg
->length
; i
++)
1291 if (seg
->as
[i
] == target_asn
)
1292 seg
->as
[i
] = our_asn
;
1297 aspath_str_update(new);
1301 /* Replace all private ASNs with our own ASN */
1303 aspath_replace_private_asns (struct aspath
*aspath
, as_t asn
)
1306 struct assegment
*seg
;
1308 new = aspath_dup(aspath
);
1309 seg
= new->segments
;
1315 for (i
= 0; i
< seg
->length
; i
++)
1317 if (BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1323 aspath_str_update(new);
1327 /* Remove all private ASNs */
1329 aspath_remove_private_asns (struct aspath
*aspath
)
1332 struct assegment
*seg
;
1333 struct assegment
*new_seg
;
1334 struct assegment
*last_new_seg
;
1339 new = XCALLOC (MTYPE_AS_PATH
, sizeof (struct aspath
));
1343 last_new_seg
= NULL
;
1344 seg
= aspath
->segments
;
1348 for (i
= 0; i
< seg
->length
; i
++)
1351 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1357 // The entire segment is private so skip it
1364 // The entire segment is public so copy it
1365 else if (public == seg
->length
)
1367 new_seg
= assegment_dup (seg
);
1370 // The segment is a mix of public and private ASNs. Copy as many spots as
1371 // there are public ASNs then come back and fill in only the public ASNs.
1374 new_seg
= assegment_new (seg
->type
, public);
1376 for (i
= 0; i
< seg
->length
; i
++)
1379 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1381 new_seg
->as
[j
] = seg
->as
[i
];
1387 // This is the first segment so set the aspath segments pointer to this one
1389 new->segments
= new_seg
;
1391 last_new_seg
->next
= new_seg
;
1393 last_new_seg
= new_seg
;
1397 aspath_str_update(new);
1401 /* AS path confed check. If aspath contains confed set or sequence then return 1. */
1403 aspath_confed_check (struct aspath
*aspath
)
1405 struct assegment
*seg
;
1407 if ( !(aspath
&& aspath
->segments
) )
1410 seg
= aspath
->segments
;
1414 if (seg
->type
== AS_CONFED_SET
|| seg
->type
== AS_CONFED_SEQUENCE
)
1421 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1422 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1424 aspath_left_confed_check (struct aspath
*aspath
)
1427 if ( !(aspath
&& aspath
->segments
) )
1430 if ( (aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1431 || (aspath
->segments
->type
== AS_CONFED_SET
) )
1437 /* Merge as1 to as2. as2 should be uninterned aspath. */
1438 static struct aspath
*
1439 aspath_merge (struct aspath
*as1
, struct aspath
*as2
)
1441 struct assegment
*last
, *new;
1446 last
= new = assegment_dup_all (as1
->segments
);
1448 /* find the last valid segment */
1449 while (last
&& last
->next
)
1452 last
->next
= as2
->segments
;
1453 as2
->segments
= new;
1454 aspath_str_update (as2
);
1458 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1460 aspath_prepend (struct aspath
*as1
, struct aspath
*as2
)
1462 struct assegment
*seg1
;
1463 struct assegment
*seg2
;
1468 seg1
= as1
->segments
;
1469 seg2
= as2
->segments
;
1471 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1474 as2
->segments
= assegment_dup_all (as1
->segments
);
1475 aspath_str_update (as2
);
1479 /* If as1 is empty AS, no prepending to do. */
1483 /* find the tail as1's segment chain. */
1484 while (seg1
&& seg1
->next
)
1487 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1488 if (seg1
->type
== AS_SEQUENCE
&& seg2
->type
== AS_CONFED_SEQUENCE
)
1489 as2
= aspath_delete_confed_seq (as2
);
1491 /* Compare last segment type of as1 and first segment type of as2. */
1492 if (seg1
->type
!= seg2
->type
)
1493 return aspath_merge (as1
, as2
);
1495 if (seg1
->type
== AS_SEQUENCE
)
1497 /* We have two chains of segments, as1->segments and seg2,
1498 * and we have to attach them together, merging the attaching
1499 * segments together into one.
1501 * 1. dupe as1->segments onto head of as2
1502 * 2. merge seg2's asns onto last segment of this new chain
1503 * 3. attach chain after seg2
1506 /* dupe as1 onto as2's head */
1507 seg1
= as2
->segments
= assegment_dup_all (as1
->segments
);
1509 /* refind the tail of as2, reusing seg1 */
1510 while (seg1
&& seg1
->next
)
1513 /* merge the old head, seg2, into tail, seg1 */
1514 seg1
= assegment_append_asns (seg1
, seg2
->as
, seg2
->length
);
1516 /* bypass the merged seg2, and attach any chain after it to
1517 * chain descending from as2's head
1519 seg1
->next
= seg2
->next
;
1521 /* seg2 is now referenceless and useless*/
1522 assegment_free (seg2
);
1524 /* we've now prepended as1's segment chain to as2, merging
1525 * the inbetween AS_SEQUENCE of seg2 in the process
1527 aspath_str_update (as2
);
1532 /* AS_SET merge code is needed at here. */
1533 return aspath_merge (as1
, as2
);
1535 /* XXX: Ermmm, what if as1 has multiple segments?? */
1540 /* Iterate over AS_PATH segments and wipe all occurences of the
1541 * listed AS numbers. Hence some segments may lose some or even
1542 * all data on the way, the operation is implemented as a smarter
1543 * version of aspath_dup(), which allocates memory to hold the new
1544 * data, not the original. The new AS path is returned.
1547 aspath_filter_exclude (struct aspath
* source
, struct aspath
* exclude_list
)
1549 struct assegment
* srcseg
, * exclseg
, * lastseg
;
1550 struct aspath
* newpath
;
1552 newpath
= aspath_new();
1555 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
)
1557 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1558 struct assegment
* newseg
;
1560 /* Find out, how much ASns are we going to pick from this segment.
1561 * We can't perform filtering right inline, because the size of
1562 * the new segment isn't known at the moment yet.
1564 for (i
= 0; i
< srcseg
->length
; i
++)
1567 for (exclseg
= exclude_list
->segments
; exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1568 for (y
= 0; y
< exclseg
->length
; y
++)
1569 if (srcseg
->as
[i
] == exclseg
->as
[y
])
1572 // There's no sense in testing the rest of exclusion list, bail out.
1578 /* newlen is now the number of ASns to copy */
1582 /* Actual copying. Allocate memory and iterate once more, performing filtering. */
1583 newseg
= assegment_new (srcseg
->type
, newlen
);
1584 for (i
= 0; i
< srcseg
->length
; i
++)
1587 for (exclseg
= exclude_list
->segments
; exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1588 for (y
= 0; y
< exclseg
->length
; y
++)
1589 if (srcseg
->as
[i
] == exclseg
->as
[y
])
1596 newseg
->as
[done
++] = srcseg
->as
[i
];
1598 /* At his point newlen must be equal to done, and both must be positive. Append
1599 * the filtered segment to the gross result. */
1601 newpath
->segments
= newseg
;
1603 lastseg
->next
= newseg
;
1606 aspath_str_update (newpath
);
1607 /* We are happy returning even an empty AS_PATH, because the administrator
1608 * might expect this very behaviour. There's a mean to avoid this, if necessary,
1609 * by having a match rule against certain AS_PATH regexps in the route-map index.
1611 aspath_free (source
);
1615 /* Add specified AS to the leftmost of aspath. */
1616 static struct aspath
*
1617 aspath_add_asns (struct aspath
*aspath
, as_t asno
, u_char type
, unsigned num
)
1619 struct assegment
*assegment
= aspath
->segments
;
1622 if (assegment
&& assegment
->type
== type
)
1624 /* extend existing segment */
1625 aspath
->segments
= assegment_prepend_asns (aspath
->segments
, asno
, num
);
1629 /* prepend with new segment */
1630 struct assegment
*newsegment
= assegment_new (type
, num
);
1631 for (i
= 0; i
< num
; i
++)
1632 newsegment
->as
[i
] = asno
;
1634 /* insert potentially replacing empty segment */
1635 if (assegment
&& assegment
->length
== 0)
1637 newsegment
->next
= assegment
->next
;
1638 assegment_free (assegment
);
1641 newsegment
->next
= assegment
;
1642 aspath
->segments
= newsegment
;
1645 aspath_str_update (aspath
);
1649 /* Add specified AS to the leftmost of aspath num times. */
1651 aspath_add_seq_n (struct aspath
*aspath
, as_t asno
, unsigned num
)
1653 return aspath_add_asns (aspath
, asno
, AS_SEQUENCE
, num
);
1656 /* Add specified AS to the leftmost of aspath. */
1658 aspath_add_seq (struct aspath
*aspath
, as_t asno
)
1660 return aspath_add_asns (aspath
, asno
, AS_SEQUENCE
, 1);
1663 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1664 as2's leftmost AS is same return 1. */
1666 aspath_cmp_left (const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1668 const struct assegment
*seg1
;
1669 const struct assegment
*seg2
;
1671 if (!(aspath1
&& aspath2
))
1674 seg1
= aspath1
->segments
;
1675 seg2
= aspath2
->segments
;
1677 /* If both paths are originated in this AS then we do want to compare MED */
1681 /* find first non-confed segments for each */
1682 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1683 || (seg1
->type
== AS_CONFED_SET
)))
1686 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1687 || (seg2
->type
== AS_CONFED_SET
)))
1692 && (seg1
->type
== AS_SEQUENCE
) && (seg2
->type
== AS_SEQUENCE
)))
1695 if (seg1
->as
[0] == seg2
->as
[0])
1701 /* Truncate an aspath after a number of hops, and put the hops remaining
1702 * at the front of another aspath. Needed for AS4 compat.
1704 * Returned aspath is a /new/ aspath, which should either by free'd or
1705 * interned by the caller, as desired.
1708 aspath_reconcile_as4 ( struct aspath
*aspath
, struct aspath
*as4path
)
1710 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1711 struct aspath
*newpath
= NULL
, *mergedpath
;
1712 int hops
, cpasns
= 0;
1717 seg
= aspath
->segments
;
1719 /* CONFEDs should get reconciled too.. */
1720 hops
= (aspath_count_hops (aspath
) + aspath_count_confeds (aspath
))
1721 - aspath_count_hops (as4path
);
1725 if (BGP_DEBUG (as4
, AS4
))
1726 zlog_warn ("[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1727 /* Something's gone wrong. The RFC says we should now ignore AS4_PATH,
1728 * which is daft behaviour - it contains vital loop-detection
1729 * information which must have been removed from AS_PATH.
1731 hops
= aspath_count_hops (aspath
);
1736 newpath
= aspath_dup (as4path
);
1737 aspath_str_update(newpath
);
1741 if ( BGP_DEBUG(as4
, AS4
))
1742 zlog_debug("[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1743 aspath
->str
, as4path
->str
);
1745 while (seg
&& hops
> 0)
1752 cpasns
= seg
->length
;
1754 case AS_CONFED_SEQUENCE
:
1755 /* Should never split a confed-sequence, if hop-count
1756 * suggests we must then something's gone wrong somewhere.
1758 * Most important goal is to preserve AS_PATHs prime function
1759 * as loop-detector, so we fudge the numbers so that the entire
1760 * confed-sequence is merged in.
1762 if (hops
< seg
->length
)
1764 if (BGP_DEBUG (as4
, AS4
))
1765 zlog_debug ("[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1766 " across 2/4 ASN boundary somewhere, broken..");
1770 cpasns
= MIN(seg
->length
, hops
);
1771 hops
-= seg
->length
;
1774 assert (cpasns
<= seg
->length
);
1776 newseg
= assegment_new (seg
->type
, 0);
1777 newseg
= assegment_append_asns (newseg
, seg
->as
, cpasns
);
1781 newpath
= aspath_new ();
1782 newpath
->segments
= newseg
;
1785 prevseg
->next
= newseg
;
1791 /* We may be able to join some segments here, and we must
1792 * do this because... we want normalised aspaths in out hash
1793 * and we do not want to stumble in aspath_put.
1795 mergedpath
= aspath_merge (newpath
, aspath_dup(as4path
));
1796 aspath_free (newpath
);
1797 mergedpath
->segments
= assegment_normalise (mergedpath
->segments
);
1798 aspath_str_update (mergedpath
);
1800 if ( BGP_DEBUG(as4
, AS4
))
1801 zlog_debug ("[AS4] result of synthesizing is %s",
1807 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1808 as2's leftmost AS is same return 1. (confederation as-path
1811 aspath_cmp_left_confed (const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1813 if (! (aspath1
&& aspath2
) )
1816 if ( !(aspath1
->segments
&& aspath2
->segments
) )
1819 if ( (aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1820 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
) )
1823 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1829 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1830 * RFC 5065 section 4.1.c.1
1832 * 1) if any path segments of the AS_PATH are of the type
1833 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1834 * removed from the AS_PATH attribute, leaving the sanitized
1835 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1838 aspath_delete_confed_seq (struct aspath
*aspath
)
1840 struct assegment
*seg
, *prev
, *next
;
1841 char removed_confed_segment
;
1843 if (!(aspath
&& aspath
->segments
))
1846 seg
= aspath
->segments
;
1847 removed_confed_segment
= 0;
1855 if (seg
->type
== AS_CONFED_SEQUENCE
|| seg
->type
== AS_CONFED_SET
)
1857 /* This is the first segment in the aspath */
1858 if (aspath
->segments
== seg
)
1859 aspath
->segments
= seg
->next
;
1861 prev
->next
= seg
->next
;
1863 assegment_free (seg
);
1864 removed_confed_segment
= 1;
1872 if (removed_confed_segment
)
1873 aspath_str_update (aspath
);
1878 /* Add new AS number to the leftmost part of the aspath as
1879 AS_CONFED_SEQUENCE. */
1881 aspath_add_confed_seq (struct aspath
*aspath
, as_t asno
)
1883 return aspath_add_asns (aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1886 /* Add new as value to as path structure. */
1888 aspath_as_add (struct aspath
*as
, as_t asno
)
1890 struct assegment
*seg
= as
->segments
;
1895 /* Last segment search procedure. */
1899 assegment_append_asns (seg
, &asno
, 1);
1902 /* Add new as segment to the as path. */
1904 aspath_segment_add (struct aspath
*as
, int type
)
1906 struct assegment
*seg
= as
->segments
;
1907 struct assegment
*new = assegment_new (type
, 0);
1922 return aspath_parse (NULL
, 0, 1); /* 32Bit ;-) */
1926 aspath_empty_get (void)
1928 struct aspath
*aspath
;
1930 aspath
= aspath_new ();
1931 aspath_make_str_count (aspath
);
1938 return ashash
->count
;
1942 Theoretically, one as path can have:
1944 One BGP packet size should be less than 4096.
1945 One BGP attribute size should be less than 4096 - BGP header size.
1946 One BGP aspath size should be less than 4096 - BGP header size -
1947 BGP mandantry attribute size.
1950 /* AS path string lexical token enum. */
1956 as_token_confed_seq_start
,
1957 as_token_confed_seq_end
,
1958 as_token_confed_set_start
,
1959 as_token_confed_set_end
,
1963 /* Return next token and point for string parse. */
1965 aspath_gettoken (const char *buf
, enum as_token
*token
, u_long
*asno
)
1967 const char *p
= buf
;
1969 /* Skip seperators (space for sequences, ',' for sets). */
1970 while (isspace ((int) *p
) || *p
== ',')
1973 /* Check the end of the string and type specify characters
1980 *token
= as_token_set_start
;
1984 *token
= as_token_set_end
;
1988 *token
= as_token_confed_seq_start
;
1992 *token
= as_token_confed_seq_end
;
1996 *token
= as_token_confed_set_start
;
2000 *token
= as_token_confed_set_end
;
2005 /* Check actual AS value. */
2006 if (isdigit ((int) *p
))
2010 *token
= as_token_asval
;
2014 while (isdigit ((int) *p
))
2017 asval
+= (*p
- '0');
2024 /* There is no match then return unknown token. */
2025 *token
= as_token_unknown
;
2030 aspath_str2aspath (const char *str
)
2032 enum as_token token
= as_token_unknown
;
2035 struct aspath
*aspath
;
2038 aspath
= aspath_new ();
2040 /* We start default type as AS_SEQUENCE. */
2041 as_type
= AS_SEQUENCE
;
2044 while ((str
= aspath_gettoken (str
, &token
, &asno
)) != NULL
)
2048 case as_token_asval
:
2051 aspath_segment_add (aspath
, as_type
);
2054 aspath_as_add (aspath
, asno
);
2056 case as_token_set_start
:
2058 aspath_segment_add (aspath
, as_type
);
2061 case as_token_set_end
:
2062 as_type
= AS_SEQUENCE
;
2065 case as_token_confed_seq_start
:
2066 as_type
= AS_CONFED_SEQUENCE
;
2067 aspath_segment_add (aspath
, as_type
);
2070 case as_token_confed_seq_end
:
2071 as_type
= AS_SEQUENCE
;
2074 case as_token_confed_set_start
:
2075 as_type
= AS_CONFED_SET
;
2076 aspath_segment_add (aspath
, as_type
);
2079 case as_token_confed_set_end
:
2080 as_type
= AS_SEQUENCE
;
2083 case as_token_unknown
:
2085 aspath_free (aspath
);
2090 aspath_make_str_count (aspath
);
2095 /* Make hash value by raw aspath data. */
2097 aspath_key_make (void *p
)
2099 struct aspath
*aspath
= (struct aspath
*) p
;
2100 unsigned int key
= 0;
2103 aspath_str_update (aspath
);
2105 key
= jhash (aspath
->str
, aspath
->str_len
, 2334325);
2110 /* If two aspath have same value then return 1 else return 0 */
2112 aspath_cmp (const void *arg1
, const void *arg2
)
2114 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2115 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2117 while (seg1
|| seg2
)
2120 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2122 if (seg1
->type
!= seg2
->type
)
2124 if (seg1
->length
!= seg2
->length
)
2126 for (i
= 0; i
< seg1
->length
; i
++)
2127 if (seg1
->as
[i
] != seg2
->as
[i
])
2135 /* AS path hash initialize. */
2139 ashash
= hash_create_size (32768, aspath_key_make
, aspath_cmp
);
2143 aspath_finish (void)
2145 hash_clean (ashash
, (void (*)(void *))aspath_free
);
2150 stream_free (snmp_stream
);
2153 /* return and as path value */
2155 aspath_print (struct aspath
*as
)
2157 return (as
? as
->str
: NULL
);
2160 /* Printing functions */
2161 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
2162 * AS_PATH wasn't empty.
2165 aspath_print_vty (struct vty
*vty
, const char *format
, struct aspath
*as
, const char * suffix
)
2168 vty_out (vty
, format
, as
->str
);
2169 if (as
->str_len
&& strlen (suffix
))
2170 vty_out (vty
, "%s", suffix
);
2174 aspath_show_all_iterator (struct hash_backet
*backet
, struct vty
*vty
)
2178 as
= (struct aspath
*) backet
->data
;
2180 vty_out (vty
, "[%p:%u] (%ld) ", (void *)backet
, backet
->key
, as
->refcnt
);
2181 vty_out (vty
, "%s%s", as
->str
, VTY_NEWLINE
);
2184 /* Print all aspath and hash information. This function is used from
2185 `show ip bgp paths' command. */
2187 aspath_print_all_vty (struct vty
*vty
)
2189 hash_iterate (ashash
,
2190 (void (*) (struct hash_backet
*, void *))
2191 aspath_show_all_iterator
,