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 along
18 * with this program; see the file COPYING; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
34 #include "bgpd/bgpd.h"
35 #include "bgpd/bgp_aspath.h"
36 #include "bgpd/bgp_debug.h"
37 #include "bgpd/bgp_attr.h"
39 /* Attr. Flags and Attr. Type Code. */
40 #define AS_HEADER_SIZE 2
42 /* Now FOUR octets are used for AS value. */
43 #define AS_VALUE_SIZE sizeof (as_t)
44 /* This is the old one */
45 #define AS16_VALUE_SIZE sizeof (as16_t)
47 /* Maximum protocol segment length value */
48 #define AS_SEGMENT_MAX 255
50 /* The following length and size macros relate specifically to Quagga's
51 * internal representation of AS-Segments, not per se to the on-wire
52 * sizes and lengths. At present (200508) they sort of match, however
53 * the ONLY functions which should now about the on-wire syntax are
54 * aspath_put, assegment_put and assegment_parse.
56 * aspath_put returns bytes written, the only definitive record of
57 * size of wire-format attribute..
60 /* Calculated size in bytes of ASN segment data to hold N ASN's */
61 #define ASSEGMENT_DATA_SIZE(N, S) \
62 ((N) * ((S) ? AS_VALUE_SIZE : AS16_VALUE_SIZE))
64 /* Calculated size of segment struct to hold N ASN's */
65 #define ASSEGMENT_SIZE(N,S) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N,S))
67 /* AS segment octet length. */
68 #define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S)
70 /* AS_SEQUENCE segments can be packed together */
71 /* Can the types of X and Y be considered for packing? */
72 #define ASSEGMENT_TYPES_PACKABLE(X, Y) \
73 (((X)->type == (Y)->type) && ((X)->type == AS_SEQUENCE))
74 /* Types and length of X,Y suitable for packing? */
75 #define ASSEGMENTS_PACKABLE(X, Y) \
76 (ASSEGMENT_TYPES_PACKABLE((X), (Y)) \
77 && (((X)->length + (Y)->length) <= AS_SEGMENT_MAX))
79 /* As segment header - the on-wire representation
80 * NOT the internal representation!
82 struct assegment_header
{
87 /* Hash for aspath. This is the top level structure of AS path. */
88 static struct hash
*ashash
;
90 /* Stream for SNMP. See aspath_snmp_pathseg */
91 static struct stream
*snmp_stream
;
93 /* Callers are required to initialize the memory */
94 static as_t
*assegment_data_new(int num
)
96 return (XMALLOC(MTYPE_AS_SEG_DATA
, ASSEGMENT_DATA_SIZE(num
, 1)));
99 static void assegment_data_free(as_t
*asdata
)
101 XFREE(MTYPE_AS_SEG_DATA
, asdata
);
104 const char *aspath_segment_type_str
[] = {"as-invalid", "as-set", "as-sequence",
105 "as-confed-sequence", "as-confed-set"};
107 /* Get a new segment. Note that 0 is an allowed length,
108 * and will result in a segment with no allocated data segment.
109 * the caller should immediately assign data to the segment, as the segment
110 * otherwise is not generally valid
112 static struct assegment
*assegment_new(u_char type
, u_short length
)
114 struct assegment
*new;
116 new = XCALLOC(MTYPE_AS_SEG
, sizeof(struct assegment
));
119 new->as
= assegment_data_new(length
);
121 new->length
= length
;
127 static void assegment_free(struct assegment
*seg
)
133 assegment_data_free(seg
->as
);
134 memset(seg
, 0xfe, sizeof(struct assegment
));
135 XFREE(MTYPE_AS_SEG
, seg
);
140 /* free entire chain of segments */
141 static void assegment_free_all(struct assegment
*seg
)
143 struct assegment
*prev
;
148 assegment_free(prev
);
152 /* Duplicate just the given assegment and its data */
153 static struct assegment
*assegment_dup(struct assegment
*seg
)
155 struct assegment
*new;
157 new = assegment_new(seg
->type
, seg
->length
);
158 memcpy(new->as
, seg
->as
, ASSEGMENT_DATA_SIZE(new->length
, 1));
163 /* Duplicate entire chain of assegments, return the head */
164 static struct assegment
*assegment_dup_all(struct assegment
*seg
)
166 struct assegment
*new = NULL
;
167 struct assegment
*head
= NULL
;
171 new->next
= assegment_dup(seg
);
174 head
= new = assegment_dup(seg
);
181 /* prepend the as number to given segment, given num of times */
182 static struct assegment
*assegment_prepend_asns(struct assegment
*seg
,
191 if (num
>= AS_SEGMENT_MAX
)
192 return seg
; /* we don't do huge prepends */
194 if ((newas
= assegment_data_new(seg
->length
+ num
)) == NULL
)
197 for (i
= 0; i
< num
; i
++)
200 memcpy(newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE(seg
->length
, 1));
201 assegment_data_free(seg
->as
);
208 /* append given array of as numbers to the segment */
209 static struct assegment
*assegment_append_asns(struct assegment
*seg
,
210 as_t
*asnos
, int num
)
214 newas
= XREALLOC(MTYPE_AS_SEG_DATA
, seg
->as
,
215 ASSEGMENT_DATA_SIZE(seg
->length
+ num
, 1));
219 memcpy(seg
->as
+ seg
->length
, asnos
,
220 ASSEGMENT_DATA_SIZE(num
, 1));
225 assegment_free_all(seg
);
229 static int int_cmp(const void *p1
, const void *p2
)
231 const as_t
*as1
= p1
;
232 const as_t
*as2
= p2
;
234 return (*as1
== *as2
) ? 0 : ((*as1
> *as2
) ? 1 : -1);
237 /* normalise the segment.
238 * In particular, merge runs of AS_SEQUENCEs into one segment
239 * Internally, we do not care about the wire segment length limit, and
240 * we want each distinct AS_PATHs to have the exact same internal
241 * representation - eg, so that our hashing actually works..
243 static struct assegment
*assegment_normalise(struct assegment
*head
)
245 struct assegment
*seg
= head
, *pin
;
246 struct assegment
*tmp
;
254 /* Sort values SET segments, for determinism in paths to aid
255 * creation of hash values / path comparisons
256 * and because it helps other lesser implementations ;)
258 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
) {
262 qsort(seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
265 for (i
= 1; i
< seg
->length
; i
++) {
266 if (seg
->as
[tail
] == seg
->as
[i
])
271 seg
->as
[tail
] = seg
->as
[i
];
273 /* seg->length can be 0.. */
275 seg
->length
= tail
+ 1;
278 /* read ahead from the current, pinned segment while the
280 * are packable/mergeable. Append all following packable
282 * to the segment we have pinned and remove these appended
285 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
)) {
289 /* append the next sequence to the pinned sequence */
290 pin
= assegment_append_asns(pin
, seg
->as
, seg
->length
);
292 /* bypass the next sequence */
293 pin
->next
= seg
->next
;
295 /* get rid of the now referenceless segment */
304 static struct aspath
*aspath_new(void)
306 return XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
309 /* Free AS path structure. */
310 void aspath_free(struct aspath
*aspath
)
314 if (aspath
->segments
)
315 assegment_free_all(aspath
->segments
);
317 XFREE(MTYPE_AS_STR
, aspath
->str
);
320 json_object_free(aspath
->json
);
324 XFREE(MTYPE_AS_PATH
, aspath
);
327 /* Unintern aspath from AS path bucket. */
328 void aspath_unintern(struct aspath
**aspath
)
331 struct aspath
*asp
= *aspath
;
336 if (asp
->refcnt
== 0) {
337 /* This aspath must exist in aspath hash table. */
338 ret
= hash_release(ashash
, asp
);
345 /* Return the start or end delimiters for a particular Segment type */
346 #define AS_SEG_START 0
348 static char aspath_delimiter_char(u_char type
, u_char which
)
355 } aspath_delim_char
[] = {{AS_SET
, '{', '}'},
356 {AS_CONFED_SET
, '[', ']'},
357 {AS_CONFED_SEQUENCE
, '(', ')'},
360 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++) {
361 if (aspath_delim_char
[i
].type
== type
) {
362 if (which
== AS_SEG_START
)
363 return aspath_delim_char
[i
].start
;
364 else if (which
== AS_SEG_END
)
365 return aspath_delim_char
[i
].end
;
371 /* countup asns from this segment and index onward */
372 static int assegment_count_asns(struct assegment
*seg
, int from
)
377 count
+= seg
->length
;
379 count
+= (seg
->length
- from
);
387 unsigned int aspath_count_confeds(struct aspath
*aspath
)
390 struct assegment
*seg
= aspath
->segments
;
393 if (seg
->type
== AS_CONFED_SEQUENCE
)
394 count
+= seg
->length
;
395 else if (seg
->type
== AS_CONFED_SET
)
403 unsigned int aspath_count_hops(const struct aspath
*aspath
)
406 struct assegment
*seg
= aspath
->segments
;
409 if (seg
->type
== AS_SEQUENCE
)
410 count
+= seg
->length
;
411 else if (seg
->type
== AS_SET
)
419 /* Estimate size aspath /might/ take if encoded into an
422 * This is a quick estimate, not definitive! aspath_put()
423 * may return a different number!!
425 unsigned int aspath_size(struct aspath
*aspath
)
428 struct assegment
*seg
= aspath
->segments
;
431 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
437 /* Return highest public ASN in path */
438 as_t
aspath_highest(struct aspath
*aspath
)
440 struct assegment
*seg
= aspath
->segments
;
445 for (i
= 0; i
< seg
->length
; i
++)
446 if (seg
->as
[i
] > highest
447 && !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
448 highest
= seg
->as
[i
];
454 /* Return the left-most ASN in path */
455 as_t
aspath_leftmost(struct aspath
*aspath
)
457 struct assegment
*seg
= aspath
->segments
;
460 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
461 leftmost
= seg
->as
[0];
466 /* Return 1 if there are any 4-byte ASes in the path */
467 unsigned int aspath_has_as4(struct aspath
*aspath
)
469 struct assegment
*seg
= aspath
->segments
;
473 for (i
= 0; i
< seg
->length
; i
++)
474 if (seg
->as
[i
] > BGP_AS_MAX
)
481 /* Convert aspath structure to string expression. */
482 static void aspath_make_str_count(struct aspath
*as
)
484 struct assegment
*seg
;
488 json_object
*jaspath_segments
= NULL
;
489 json_object
*jseg
= NULL
;
490 json_object
*jseg_list
= NULL
;
492 as
->json
= json_object_new_object();
493 jaspath_segments
= json_object_new_array();
497 json_object_string_add(as
->json
, "string", "Local");
498 json_object_object_add(as
->json
, "segments", jaspath_segments
);
499 json_object_int_add(as
->json
, "length", 0);
500 as
->str
= XMALLOC(MTYPE_AS_STR
, 1);
508 /* ASN takes 5 to 10 chars plus seperator, see below.
509 * If there is one differing segment type, we need an additional
510 * 2 chars for segment delimiters, and the final '\0'.
511 * Hopefully this is large enough to avoid hitting the realloc
512 * code below for most common sequences.
514 * This was changed to 10 after the well-known BGP assertion, which
515 * had hit some parts of the Internet in May of 2009.
517 #define ASN_STR_LEN (10 + 1)
518 str_size
= MAX(assegment_count_asns(seg
, 0) * ASN_STR_LEN
+ 2 + 1,
519 ASPATH_STR_DEFAULT_LEN
);
520 str_buf
= XMALLOC(MTYPE_AS_STR
, str_size
);
526 /* Check AS type validity. Set seperator for segment */
533 case AS_CONFED_SEQUENCE
:
537 XFREE(MTYPE_AS_STR
, str_buf
);
540 json_object_free(as
->json
);
545 /* We might need to increase str_buf, particularly if path has
546 * differing segments types, our initial guesstimate above will
547 * have been wrong. Need 10 chars for ASN, a seperator each and
548 * potentially two segment delimiters, plus a space between each
549 * segment and trailing zero.
551 * This definitely didn't work with the value of 5 bytes and
554 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
555 if ((len
+ SEGMENT_STR_LEN(seg
)) > str_size
) {
556 str_size
= len
+ SEGMENT_STR_LEN(seg
);
557 str_buf
= XREALLOC(MTYPE_AS_STR
, str_buf
, str_size
);
560 #undef SEGMENT_STR_LEN
562 if (seg
->type
!= AS_SEQUENCE
)
564 str_buf
+ len
, str_size
- len
, "%c",
565 aspath_delimiter_char(seg
->type
, AS_SEG_START
));
567 jseg_list
= json_object_new_array();
569 /* write out the ASNs, with their seperators, bar the last one*/
570 for (i
= 0; i
< seg
->length
; i
++) {
571 json_object_array_add(jseg_list
,
572 json_object_new_int(seg
->as
[i
]));
574 len
+= snprintf(str_buf
+ len
, str_size
- len
, "%u",
577 if (i
< (seg
->length
- 1))
578 len
+= snprintf(str_buf
+ len
, str_size
- len
,
582 jseg
= json_object_new_object();
583 json_object_string_add(jseg
, "type",
584 aspath_segment_type_str
[seg
->type
]);
585 json_object_object_add(jseg
, "list", jseg_list
);
586 json_object_array_add(jaspath_segments
, jseg
);
588 if (seg
->type
!= AS_SEQUENCE
)
590 str_buf
+ len
, str_size
- len
, "%c",
591 aspath_delimiter_char(seg
->type
, AS_SEG_END
));
593 len
+= snprintf(str_buf
+ len
, str_size
- len
, " ");
598 assert(len
< str_size
);
604 json_object_string_add(as
->json
, "string", str_buf
);
605 json_object_object_add(as
->json
, "segments", jaspath_segments
);
606 json_object_int_add(as
->json
, "length", aspath_count_hops(as
));
610 static void aspath_str_update(struct aspath
*as
)
613 XFREE(MTYPE_AS_STR
, as
->str
);
616 json_object_free(as
->json
);
620 aspath_make_str_count(as
);
623 /* Intern allocated AS path. */
624 struct aspath
*aspath_intern(struct aspath
*aspath
)
628 /* Assert this AS path structure is not interned and has the string
629 representation built. */
630 assert(aspath
->refcnt
== 0);
633 /* Check AS path hash. */
634 find
= hash_get(ashash
, aspath
, hash_alloc_intern
);
643 /* Duplicate aspath structure. Created same aspath structure but
644 reference count and AS path string is cleared. */
645 struct aspath
*aspath_dup(struct aspath
*aspath
)
647 unsigned short buflen
= aspath
->str_len
+ 1;
650 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
653 if (aspath
->segments
)
654 new->segments
= assegment_dup_all(aspath
->segments
);
659 new->str
= XMALLOC(MTYPE_AS_STR
, buflen
);
660 new->str_len
= aspath
->str_len
;
662 /* copy the string data */
663 if (aspath
->str_len
> 0)
664 memcpy(new->str
, aspath
->str
, buflen
);
671 static void *aspath_hash_alloc(void *arg
)
673 const struct aspath
*aspath
= arg
;
676 /* Malformed AS path value. */
679 /* New aspath structure is needed. */
680 new = XMALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
682 /* Reuse segments and string representation */
684 new->segments
= aspath
->segments
;
685 new->str
= aspath
->str
;
686 new->str_len
= aspath
->str_len
;
687 new->json
= aspath
->json
;
692 /* parse as-segment byte stream in struct assegment */
693 static int assegments_parse(struct stream
*s
, size_t length
,
694 struct assegment
**result
, int use32bit
)
696 struct assegment_header segh
;
697 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
700 /* empty aspath (ie iBGP or somesuch) */
704 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
706 "[AS4SEG] Parse aspath segment: got total byte length %lu",
707 (unsigned long)length
);
709 if ((STREAM_READABLE(s
) < length
)
710 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
711 || (length
% AS16_VALUE_SIZE
))
714 while (bytes
< length
) {
718 if ((length
- bytes
) <= AS_HEADER_SIZE
) {
720 assegment_free_all(head
);
724 /* softly softly, get the header first on its own */
725 segh
.type
= stream_getc(s
);
726 segh
.length
= stream_getc(s
);
728 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
730 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
732 "[AS4SEG] Parse aspath segment: got type %d, length %d",
733 segh
.type
, segh
.length
);
736 if (((bytes
+ seg_size
) > length
)
737 /* 1771bis 4.3b: seg length contains one or more */
738 || (segh
.length
== 0)
739 /* Paranoia in case someone changes type of segment length.
740 * Shift both values by 0x10 to make the comparison operate
741 * on more, than 8 bits (otherwise it's a warning, bug
744 || ((sizeof segh
.length
> 1)
745 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
))) {
747 assegment_free_all(head
);
754 case AS_CONFED_SEQUENCE
:
759 assegment_free_all(head
);
763 /* now its safe to trust lengths */
764 seg
= assegment_new(segh
.type
, segh
.length
);
768 else /* it's the first segment */
771 for (i
= 0; i
< segh
.length
; i
++)
773 (use32bit
) ? stream_getl(s
) : stream_getw(s
);
777 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
779 "[AS4SEG] Parse aspath segment: Bytes now: %lu",
780 (unsigned long)bytes
);
785 *result
= assegment_normalise(head
);
789 /* AS path parse function. pnt is a pointer to byte stream and length
790 is length of byte stream. If there is same AS path in the the AS
791 path hash then return it else make new AS path structure.
793 On error NULL is returned.
795 struct aspath
*aspath_parse(struct stream
*s
, size_t length
, int use32bit
)
800 /* If length is odd it's malformed AS path. */
801 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
802 * otherwise its malformed when length is larger than 2 and (length-2)
803 * is not dividable by 4.
804 * But... this time we're lazy
806 if (length
% AS16_VALUE_SIZE
)
809 memset(&as
, 0, sizeof(struct aspath
));
810 if (assegments_parse(s
, length
, &as
.segments
, use32bit
) < 0)
813 /* If already same aspath exist then return it. */
814 find
= hash_get(ashash
, &as
, aspath_hash_alloc
);
816 /* bug! should not happen, let the daemon crash below */
819 /* if the aspath was already hashed free temporary memory. */
821 assegment_free_all(as
.segments
);
822 /* aspath_key_make() always updates the string */
823 XFREE(MTYPE_AS_STR
, as
.str
);
825 json_object_free(as
.json
);
835 static void assegment_data_put(struct stream
*s
, as_t
*as
, int num
,
839 assert(num
<= AS_SEGMENT_MAX
);
841 for (i
= 0; i
< num
; i
++)
843 stream_putl(s
, as
[i
]);
845 if (as
[i
] <= BGP_AS_MAX
)
846 stream_putw(s
, as
[i
]);
848 stream_putw(s
, BGP_AS_TRANS
);
852 static size_t assegment_header_put(struct stream
*s
, u_char type
, int length
)
855 assert(length
<= AS_SEGMENT_MAX
);
856 stream_putc(s
, type
);
857 lenp
= stream_get_endp(s
);
858 stream_putc(s
, length
);
862 /* write aspath data to stream */
863 size_t aspath_put(struct stream
*s
, struct aspath
*as
, int use32bit
)
865 struct assegment
*seg
= as
->segments
;
868 if (!seg
|| seg
->length
== 0)
873 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
874 * At the moment, we would write out a partial aspath, and our
876 * will complain and drop the session :-/
878 * The general assumption here is that many things tested will
879 * never happen. And, in real live, up to now, they have not.
882 && (ASSEGMENT_LEN(seg
, use32bit
)
883 <= STREAM_WRITEABLE(s
))) {
884 struct assegment
*next
= seg
->next
;
889 /* Overlength segments have to be split up */
890 while ((seg
->length
- written
) > AS_SEGMENT_MAX
) {
891 assegment_header_put(s
, seg
->type
,
893 assegment_data_put(s
, seg
->as
, AS_SEGMENT_MAX
,
895 written
+= AS_SEGMENT_MAX
;
896 bytes
+= ASSEGMENT_SIZE(written
, use32bit
);
899 /* write the final segment, probably is also the first
901 lenp
= assegment_header_put(s
, seg
->type
,
902 seg
->length
- written
);
903 assegment_data_put(s
, (seg
->as
+ written
),
904 seg
->length
- written
, use32bit
);
906 /* Sequence-type segments can be 'packed' together
907 * Case of a segment which was overlength and split up
908 * will be missed here, but that doesn't matter.
910 while (next
&& ASSEGMENTS_PACKABLE(seg
, next
)) {
911 /* NB: We should never normally get here given
913 * normalise aspath data when parse them.
915 * safe than sorry. We potentially could call
916 * assegment_normalise here instead, but it's
918 * easier to do it on the fly here rather than
920 * the segment list twice every time we write
925 /* Next segment's data can fit in this one */
926 assegment_data_put(s
, next
->as
, next
->length
,
929 /* update the length of the segment header */
930 stream_putc_at(s
, lenp
,
931 seg
->length
- written
933 asns_packed
+= next
->length
;
938 bytes
+= ASSEGMENT_SIZE(
939 seg
->length
- written
+ asns_packed
, use32bit
);
946 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
947 * We have no way to manage the storage, so we use a static stream
948 * wrapper around aspath_put.
950 u_char
*aspath_snmp_pathseg(struct aspath
*as
, size_t *varlen
)
952 #define SNMP_PATHSEG_MAX 1024
955 snmp_stream
= stream_new(SNMP_PATHSEG_MAX
);
957 stream_reset(snmp_stream
);
963 aspath_put(snmp_stream
, as
, 0); /* use 16 bit for now here */
965 *varlen
= stream_get_endp(snmp_stream
);
966 return stream_pnt(snmp_stream
);
969 #define min(A,B) ((A) < (B) ? (A) : (B))
971 static struct assegment
*aspath_aggregate_as_set_add(struct aspath
*aspath
,
972 struct assegment
*asset
,
977 /* If this is first AS set member, create new as-set segment. */
979 asset
= assegment_new(AS_SET
, 1);
980 if (!aspath
->segments
)
981 aspath
->segments
= asset
;
983 struct assegment
*seg
= aspath
->segments
;
988 asset
->type
= AS_SET
;
992 /* Check this AS value already exists or not. */
993 for (i
= 0; i
< asset
->length
; i
++)
994 if (asset
->as
[i
] == as
)
998 asset
->as
= XREALLOC(MTYPE_AS_SEG_DATA
, asset
->as
,
999 asset
->length
* AS_VALUE_SIZE
);
1000 asset
->as
[asset
->length
- 1] = as
;
1007 /* Modify as1 using as2 for aggregation. */
1008 struct aspath
*aspath_aggregate(struct aspath
*as1
, struct aspath
*as2
)
1014 struct assegment
*seg1
= as1
->segments
;
1015 struct assegment
*seg2
= as2
->segments
;
1016 struct aspath
*aspath
= NULL
;
1017 struct assegment
*asset
= NULL
;
1018 struct assegment
*prevseg
= NULL
;
1020 /* First of all check common leading sequence. */
1021 while (seg1
&& seg2
) {
1022 /* Check segment type. */
1023 if (seg1
->type
!= seg2
->type
)
1026 /* Minimum segment length. */
1027 minlen
= min(seg1
->length
, seg2
->length
);
1029 for (match
= 0; match
< minlen
; match
++)
1030 if (seg1
->as
[match
] != seg2
->as
[match
])
1034 struct assegment
*seg
= assegment_new(seg1
->type
, 0);
1036 seg
= assegment_append_asns(seg
, seg1
->as
, match
);
1039 aspath
= aspath_new();
1040 aspath
->segments
= seg
;
1042 prevseg
->next
= seg
;
1047 if (match
!= minlen
|| match
!= seg1
->length
1048 || seg1
->length
!= seg2
->length
)
1050 /* We are moving on to the next segment to reset match */
1059 aspath
= aspath_new();
1061 /* Make as-set using rest of all information. */
1064 for (i
= from
; i
< seg1
->length
; i
++)
1065 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1074 for (i
= from
; i
< seg2
->length
; i
++)
1075 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1082 assegment_normalise(aspath
->segments
);
1083 aspath_str_update(aspath
);
1087 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1088 attribute, check the leftmost AS number in the AS_PATH attribute is
1089 or not the peer's AS number. */
1090 int aspath_firstas_check(struct aspath
*aspath
, as_t asno
)
1092 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1095 if (aspath
->segments
&& (aspath
->segments
->type
== AS_SEQUENCE
)
1096 && (aspath
->segments
->as
[0] == asno
))
1102 unsigned int aspath_get_first_as(struct aspath
*aspath
)
1104 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1107 return aspath
->segments
->as
[0];
1110 unsigned int aspath_get_last_as(struct aspath
*aspath
)
1113 unsigned int last_as
= 0;
1114 const struct assegment
*seg
;
1116 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1119 seg
= aspath
->segments
;
1122 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1123 for (i
= 0; i
< seg
->length
; i
++)
1124 last_as
= seg
->as
[i
];
1131 /* AS path loop check. If aspath contains asno then return >= 1. */
1132 int aspath_loop_check(struct aspath
*aspath
, as_t asno
)
1134 struct assegment
*seg
;
1137 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1140 seg
= aspath
->segments
;
1145 for (i
= 0; i
< seg
->length
; i
++)
1146 if (seg
->as
[i
] == asno
)
1154 /* When all of AS path is private AS return 1. */
1155 int aspath_private_as_check(struct aspath
*aspath
)
1157 struct assegment
*seg
;
1159 if (!(aspath
&& aspath
->segments
))
1162 seg
= aspath
->segments
;
1167 for (i
= 0; i
< seg
->length
; i
++) {
1168 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1176 /* Return True if the entire ASPATH consist of the specified ASN */
1177 int aspath_single_asn_check(struct aspath
*aspath
, as_t asn
)
1179 struct assegment
*seg
;
1181 if (!(aspath
&& aspath
->segments
))
1184 seg
= aspath
->segments
;
1189 for (i
= 0; i
< seg
->length
; i
++) {
1190 if (seg
->as
[i
] != asn
)
1198 /* Replace all instances of the target ASN with our own ASN */
1199 struct aspath
*aspath_replace_specific_asn(struct aspath
*aspath
,
1200 as_t target_asn
, as_t our_asn
)
1203 struct assegment
*seg
;
1205 new = aspath_dup(aspath
);
1206 seg
= new->segments
;
1211 for (i
= 0; i
< seg
->length
; i
++) {
1212 if (seg
->as
[i
] == target_asn
)
1213 seg
->as
[i
] = our_asn
;
1218 aspath_str_update(new);
1222 /* Replace all private ASNs with our own ASN */
1223 struct aspath
*aspath_replace_private_asns(struct aspath
*aspath
, as_t asn
)
1226 struct assegment
*seg
;
1228 new = aspath_dup(aspath
);
1229 seg
= new->segments
;
1234 for (i
= 0; i
< seg
->length
; i
++) {
1235 if (BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1241 aspath_str_update(new);
1245 /* Remove all private ASNs */
1246 struct aspath
*aspath_remove_private_asns(struct aspath
*aspath
)
1249 struct assegment
*seg
;
1250 struct assegment
*new_seg
;
1251 struct assegment
*last_new_seg
;
1256 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
1260 last_new_seg
= NULL
;
1261 seg
= aspath
->segments
;
1265 for (i
= 0; i
< seg
->length
; i
++) {
1267 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1273 // The entire segment is private so skip it
1279 // The entire segment is public so copy it
1280 else if (public == seg
->length
) {
1281 new_seg
= assegment_dup(seg
);
1284 // The segment is a mix of public and private ASNs. Copy as many
1286 // there are public ASNs then come back and fill in only the
1289 new_seg
= assegment_new(seg
->type
, public);
1291 for (i
= 0; i
< seg
->length
; i
++) {
1293 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1294 new_seg
->as
[j
] = seg
->as
[i
];
1300 // This is the first segment so set the aspath segments pointer
1303 new->segments
= new_seg
;
1305 last_new_seg
->next
= new_seg
;
1307 last_new_seg
= new_seg
;
1311 aspath_str_update(new);
1315 /* AS path confed check. If aspath contains confed set or sequence then return
1317 int aspath_confed_check(struct aspath
*aspath
)
1319 struct assegment
*seg
;
1321 if (!(aspath
&& aspath
->segments
))
1324 seg
= aspath
->segments
;
1327 if (seg
->type
== AS_CONFED_SET
1328 || seg
->type
== AS_CONFED_SEQUENCE
)
1335 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1336 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1337 int aspath_left_confed_check(struct aspath
*aspath
)
1340 if (!(aspath
&& aspath
->segments
))
1343 if ((aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1344 || (aspath
->segments
->type
== AS_CONFED_SET
))
1350 /* Merge as1 to as2. as2 should be uninterned aspath. */
1351 static struct aspath
*aspath_merge(struct aspath
*as1
, struct aspath
*as2
)
1353 struct assegment
*last
, *new;
1358 last
= new = assegment_dup_all(as1
->segments
);
1360 /* find the last valid segment */
1361 while (last
&& last
->next
)
1364 last
->next
= as2
->segments
;
1365 as2
->segments
= new;
1366 aspath_str_update(as2
);
1370 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1371 struct aspath
*aspath_prepend(struct aspath
*as1
, struct aspath
*as2
)
1373 struct assegment
*seg1
;
1374 struct assegment
*seg2
;
1379 seg1
= as1
->segments
;
1380 seg2
= as2
->segments
;
1382 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1384 as2
->segments
= assegment_dup_all(as1
->segments
);
1385 aspath_str_update(as2
);
1389 /* If as1 is empty AS, no prepending to do. */
1393 /* find the tail as1's segment chain. */
1394 while (seg1
&& seg1
->next
)
1397 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1398 if (seg1
->type
== AS_SEQUENCE
&& seg2
->type
== AS_CONFED_SEQUENCE
)
1399 as2
= aspath_delete_confed_seq(as2
);
1401 /* Compare last segment type of as1 and first segment type of as2. */
1402 if (seg1
->type
!= seg2
->type
)
1403 return aspath_merge(as1
, as2
);
1405 if (seg1
->type
== AS_SEQUENCE
) {
1406 /* We have two chains of segments, as1->segments and seg2,
1407 * and we have to attach them together, merging the attaching
1408 * segments together into one.
1410 * 1. dupe as1->segments onto head of as2
1411 * 2. merge seg2's asns onto last segment of this new chain
1412 * 3. attach chain after seg2
1415 /* dupe as1 onto as2's head */
1416 seg1
= as2
->segments
= assegment_dup_all(as1
->segments
);
1418 /* refind the tail of as2, reusing seg1 */
1419 while (seg1
&& seg1
->next
)
1422 /* merge the old head, seg2, into tail, seg1 */
1423 seg1
= assegment_append_asns(seg1
, seg2
->as
, seg2
->length
);
1425 /* bypass the merged seg2, and attach any chain after it to
1426 * chain descending from as2's head
1428 seg1
->next
= seg2
->next
;
1430 /* seg2 is now referenceless and useless*/
1431 assegment_free(seg2
);
1433 /* we've now prepended as1's segment chain to as2, merging
1434 * the inbetween AS_SEQUENCE of seg2 in the process
1436 aspath_str_update(as2
);
1439 /* AS_SET merge code is needed at here. */
1440 return aspath_merge(as1
, as2
);
1442 /* XXX: Ermmm, what if as1 has multiple segments?? */
1447 /* Iterate over AS_PATH segments and wipe all occurences of the
1448 * listed AS numbers. Hence some segments may lose some or even
1449 * all data on the way, the operation is implemented as a smarter
1450 * version of aspath_dup(), which allocates memory to hold the new
1451 * data, not the original. The new AS path is returned.
1453 struct aspath
*aspath_filter_exclude(struct aspath
*source
,
1454 struct aspath
*exclude_list
)
1456 struct assegment
*srcseg
, *exclseg
, *lastseg
;
1457 struct aspath
*newpath
;
1459 newpath
= aspath_new();
1462 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
) {
1463 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1464 struct assegment
*newseg
;
1466 /* Find out, how much ASns are we going to pick from this
1468 * We can't perform filtering right inline, because the size of
1469 * the new segment isn't known at the moment yet.
1471 for (i
= 0; i
< srcseg
->length
; i
++) {
1473 for (exclseg
= exclude_list
->segments
;
1474 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1475 for (y
= 0; y
< exclseg
->length
; y
++)
1476 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1478 // There's no sense in testing
1479 // the rest of exclusion list,
1486 /* newlen is now the number of ASns to copy */
1490 /* Actual copying. Allocate memory and iterate once more,
1491 * performing filtering. */
1492 newseg
= assegment_new(srcseg
->type
, newlen
);
1493 for (i
= 0; i
< srcseg
->length
; i
++) {
1495 for (exclseg
= exclude_list
->segments
;
1496 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1497 for (y
= 0; y
< exclseg
->length
; y
++)
1498 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1504 newseg
->as
[done
++] = srcseg
->as
[i
];
1506 /* At his point newlen must be equal to done, and both must be
1508 * the filtered segment to the gross result. */
1510 newpath
->segments
= newseg
;
1512 lastseg
->next
= newseg
;
1515 aspath_str_update(newpath
);
1516 /* We are happy returning even an empty AS_PATH, because the
1518 * might expect this very behaviour. There's a mean to avoid this, if
1520 * by having a match rule against certain AS_PATH regexps in the
1523 aspath_free(source
);
1527 /* Add specified AS to the leftmost of aspath. */
1528 static struct aspath
*aspath_add_asns(struct aspath
*aspath
, as_t asno
,
1529 u_char type
, unsigned num
)
1531 struct assegment
*assegment
= aspath
->segments
;
1534 if (assegment
&& assegment
->type
== type
) {
1535 /* extend existing segment */
1537 assegment_prepend_asns(aspath
->segments
, asno
, num
);
1539 /* prepend with new segment */
1540 struct assegment
*newsegment
= assegment_new(type
, num
);
1541 for (i
= 0; i
< num
; i
++)
1542 newsegment
->as
[i
] = asno
;
1544 /* insert potentially replacing empty segment */
1545 if (assegment
&& assegment
->length
== 0) {
1546 newsegment
->next
= assegment
->next
;
1547 assegment_free(assegment
);
1549 newsegment
->next
= assegment
;
1550 aspath
->segments
= newsegment
;
1553 aspath_str_update(aspath
);
1557 /* Add specified AS to the leftmost of aspath num times. */
1558 struct aspath
*aspath_add_seq_n(struct aspath
*aspath
, as_t asno
, unsigned num
)
1560 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, num
);
1563 /* Add specified AS to the leftmost of aspath. */
1564 struct aspath
*aspath_add_seq(struct aspath
*aspath
, as_t asno
)
1566 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, 1);
1569 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1570 as2's leftmost AS is same return 1. */
1571 int aspath_cmp_left(const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1573 const struct assegment
*seg1
;
1574 const struct assegment
*seg2
;
1576 if (!(aspath1
&& aspath2
))
1579 seg1
= aspath1
->segments
;
1580 seg2
= aspath2
->segments
;
1582 /* If both paths are originated in this AS then we do want to compare
1587 /* find first non-confed segments for each */
1589 && ((seg1
->type
== AS_CONFED_SEQUENCE
)
1590 || (seg1
->type
== AS_CONFED_SET
)))
1594 && ((seg2
->type
== AS_CONFED_SEQUENCE
)
1595 || (seg2
->type
== AS_CONFED_SET
)))
1599 if (!(seg1
&& seg2
&& (seg1
->type
== AS_SEQUENCE
)
1600 && (seg2
->type
== AS_SEQUENCE
)))
1603 if (seg1
->as
[0] == seg2
->as
[0])
1609 /* Truncate an aspath after a number of hops, and put the hops remaining
1610 * at the front of another aspath. Needed for AS4 compat.
1612 * Returned aspath is a /new/ aspath, which should either by free'd or
1613 * interned by the caller, as desired.
1615 struct aspath
*aspath_reconcile_as4(struct aspath
*aspath
,
1616 struct aspath
*as4path
)
1618 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1619 struct aspath
*newpath
= NULL
, *mergedpath
;
1620 int hops
, cpasns
= 0;
1625 seg
= aspath
->segments
;
1627 /* CONFEDs should get reconciled too.. */
1628 hops
= (aspath_count_hops(aspath
) + aspath_count_confeds(aspath
))
1629 - aspath_count_hops(as4path
);
1632 if (BGP_DEBUG(as4
, AS4
))
1634 "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1635 /* Something's gone wrong. The RFC says we should now ignore
1637 * which is daft behaviour - it contains vital loop-detection
1638 * information which must have been removed from AS_PATH.
1640 hops
= aspath_count_hops(aspath
);
1644 newpath
= aspath_dup(as4path
);
1645 aspath_str_update(newpath
);
1649 if (BGP_DEBUG(as4
, AS4
))
1651 "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1652 aspath
->str
, as4path
->str
);
1654 while (seg
&& hops
> 0) {
1655 switch (seg
->type
) {
1659 cpasns
= seg
->length
;
1661 case AS_CONFED_SEQUENCE
:
1662 /* Should never split a confed-sequence, if hop-count
1663 * suggests we must then something's gone wrong
1666 * Most important goal is to preserve AS_PATHs prime
1668 * as loop-detector, so we fudge the numbers so that the
1670 * confed-sequence is merged in.
1672 if (hops
< seg
->length
) {
1673 if (BGP_DEBUG(as4
, AS4
))
1675 "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1676 " across 2/4 ASN boundary somewhere, broken..");
1681 cpasns
= MIN(seg
->length
, hops
);
1682 hops
-= seg
->length
;
1685 assert(cpasns
<= seg
->length
);
1687 newseg
= assegment_new(seg
->type
, 0);
1688 newseg
= assegment_append_asns(newseg
, seg
->as
, cpasns
);
1691 newpath
= aspath_new();
1692 newpath
->segments
= newseg
;
1694 prevseg
->next
= newseg
;
1700 /* We may be able to join some segments here, and we must
1701 * do this because... we want normalised aspaths in out hash
1702 * and we do not want to stumble in aspath_put.
1704 mergedpath
= aspath_merge(newpath
, aspath_dup(as4path
));
1705 aspath_free(newpath
);
1706 mergedpath
->segments
= assegment_normalise(mergedpath
->segments
);
1707 aspath_str_update(mergedpath
);
1709 if (BGP_DEBUG(as4
, AS4
))
1710 zlog_debug("[AS4] result of synthesizing is %s",
1716 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1717 as2's leftmost AS is same return 1. (confederation as-path
1719 int aspath_cmp_left_confed(const struct aspath
*aspath1
,
1720 const struct aspath
*aspath2
)
1722 if (!(aspath1
&& aspath2
))
1725 if (!(aspath1
->segments
&& aspath2
->segments
))
1728 if ((aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1729 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
))
1732 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1738 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1739 * RFC 5065 section 4.1.c.1
1741 * 1) if any path segments of the AS_PATH are of the type
1742 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1743 * removed from the AS_PATH attribute, leaving the sanitized
1744 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1746 struct aspath
*aspath_delete_confed_seq(struct aspath
*aspath
)
1748 struct assegment
*seg
, *prev
, *next
;
1749 char removed_confed_segment
;
1751 if (!(aspath
&& aspath
->segments
))
1754 seg
= aspath
->segments
;
1755 removed_confed_segment
= 0;
1762 if (seg
->type
== AS_CONFED_SEQUENCE
1763 || seg
->type
== AS_CONFED_SET
) {
1764 /* This is the first segment in the aspath */
1765 if (aspath
->segments
== seg
)
1766 aspath
->segments
= seg
->next
;
1768 prev
->next
= seg
->next
;
1770 assegment_free(seg
);
1771 removed_confed_segment
= 1;
1778 if (removed_confed_segment
)
1779 aspath_str_update(aspath
);
1784 /* Add new AS number to the leftmost part of the aspath as
1785 AS_CONFED_SEQUENCE. */
1786 struct aspath
*aspath_add_confed_seq(struct aspath
*aspath
, as_t asno
)
1788 return aspath_add_asns(aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1791 /* Add new as value to as path structure. */
1792 static void aspath_as_add(struct aspath
*as
, as_t asno
)
1794 struct assegment
*seg
= as
->segments
;
1799 /* Last segment search procedure. */
1803 assegment_append_asns(seg
, &asno
, 1);
1806 /* Add new as segment to the as path. */
1807 static void aspath_segment_add(struct aspath
*as
, int type
)
1809 struct assegment
*seg
= as
->segments
;
1810 struct assegment
*new = assegment_new(type
, 0);
1820 struct aspath
*aspath_empty(void)
1822 return aspath_parse(NULL
, 0, 1); /* 32Bit ;-) */
1825 struct aspath
*aspath_empty_get(void)
1827 struct aspath
*aspath
;
1829 aspath
= aspath_new();
1830 aspath_make_str_count(aspath
);
1834 unsigned long aspath_count(void)
1836 return ashash
->count
;
1840 Theoretically, one as path can have:
1842 One BGP packet size should be less than 4096.
1843 One BGP attribute size should be less than 4096 - BGP header size.
1844 One BGP aspath size should be less than 4096 - BGP header size -
1845 BGP mandantry attribute size.
1848 /* AS path string lexical token enum. */
1853 as_token_confed_seq_start
,
1854 as_token_confed_seq_end
,
1855 as_token_confed_set_start
,
1856 as_token_confed_set_end
,
1860 /* Return next token and point for string parse. */
1861 static const char *aspath_gettoken(const char *buf
, enum as_token
*token
,
1864 const char *p
= buf
;
1866 /* Skip seperators (space for sequences, ',' for sets). */
1867 while (isspace((int)*p
) || *p
== ',')
1870 /* Check the end of the string and type specify characters
1876 *token
= as_token_set_start
;
1880 *token
= as_token_set_end
;
1884 *token
= as_token_confed_seq_start
;
1888 *token
= as_token_confed_seq_end
;
1892 *token
= as_token_confed_set_start
;
1896 *token
= as_token_confed_set_end
;
1901 /* Check actual AS value. */
1902 if (isdigit((int)*p
)) {
1905 *token
= as_token_asval
;
1909 while (isdigit((int)*p
)) {
1911 asval
+= (*p
- '0');
1918 /* There is no match then return unknown token. */
1919 *token
= as_token_unknown
;
1923 struct aspath
*aspath_str2aspath(const char *str
)
1925 enum as_token token
= as_token_unknown
;
1928 struct aspath
*aspath
;
1931 aspath
= aspath_new();
1933 /* We start default type as AS_SEQUENCE. */
1934 as_type
= AS_SEQUENCE
;
1937 while ((str
= aspath_gettoken(str
, &token
, &asno
)) != NULL
) {
1939 case as_token_asval
:
1941 aspath_segment_add(aspath
, as_type
);
1944 aspath_as_add(aspath
, asno
);
1946 case as_token_set_start
:
1948 aspath_segment_add(aspath
, as_type
);
1951 case as_token_set_end
:
1952 as_type
= AS_SEQUENCE
;
1955 case as_token_confed_seq_start
:
1956 as_type
= AS_CONFED_SEQUENCE
;
1957 aspath_segment_add(aspath
, as_type
);
1960 case as_token_confed_seq_end
:
1961 as_type
= AS_SEQUENCE
;
1964 case as_token_confed_set_start
:
1965 as_type
= AS_CONFED_SET
;
1966 aspath_segment_add(aspath
, as_type
);
1969 case as_token_confed_set_end
:
1970 as_type
= AS_SEQUENCE
;
1973 case as_token_unknown
:
1975 aspath_free(aspath
);
1980 aspath_make_str_count(aspath
);
1985 /* Make hash value by raw aspath data. */
1986 unsigned int aspath_key_make(void *p
)
1988 struct aspath
*aspath
= (struct aspath
*)p
;
1989 unsigned int key
= 0;
1992 aspath_str_update(aspath
);
1994 key
= jhash(aspath
->str
, aspath
->str_len
, 2334325);
1999 /* If two aspath have same value then return 1 else return 0 */
2000 int aspath_cmp(const void *arg1
, const void *arg2
)
2002 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2003 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2005 while (seg1
|| seg2
) {
2007 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2009 if (seg1
->type
!= seg2
->type
)
2011 if (seg1
->length
!= seg2
->length
)
2013 for (i
= 0; i
< seg1
->length
; i
++)
2014 if (seg1
->as
[i
] != seg2
->as
[i
])
2022 /* AS path hash initialize. */
2023 void aspath_init(void)
2025 ashash
= hash_create_size(32768, aspath_key_make
, aspath_cmp
, NULL
);
2028 void aspath_finish(void)
2030 hash_clean(ashash
, (void (*)(void *))aspath_free
);
2035 stream_free(snmp_stream
);
2038 /* return and as path value */
2039 const char *aspath_print(struct aspath
*as
)
2041 return (as
? as
->str
: NULL
);
2044 /* Printing functions */
2045 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
2046 * AS_PATH wasn't empty.
2048 void aspath_print_vty(struct vty
*vty
, const char *format
, struct aspath
*as
,
2052 vty_out(vty
, format
, as
->str
);
2053 if (as
->str_len
&& strlen(suffix
))
2054 vty_out(vty
, "%s", suffix
);
2057 static void aspath_show_all_iterator(struct hash_backet
*backet
,
2062 as
= (struct aspath
*)backet
->data
;
2064 vty_out(vty
, "[%p:%u] (%ld) ", (void *)backet
, backet
->key
, as
->refcnt
);
2065 vty_out(vty
, "%s\n", as
->str
);
2068 /* Print all aspath and hash information. This function is used from
2069 `show [ip] bgp paths' command. */
2070 void aspath_print_all_vty(struct vty
*vty
)
2072 hash_iterate(ashash
,
2073 (void (*)(struct hash_backet
*,
2074 void *))aspath_show_all_iterator
,