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(uint8_t type
, unsigned 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));
218 memcpy(seg
->as
+ seg
->length
, asnos
,
219 ASSEGMENT_DATA_SIZE(num
, 1));
224 static int int_cmp(const void *p1
, const void *p2
)
226 const as_t
*as1
= p1
;
227 const as_t
*as2
= p2
;
229 return (*as1
== *as2
) ? 0 : ((*as1
> *as2
) ? 1 : -1);
232 /* normalise the segment.
233 * In particular, merge runs of AS_SEQUENCEs into one segment
234 * Internally, we do not care about the wire segment length limit, and
235 * we want each distinct AS_PATHs to have the exact same internal
236 * representation - eg, so that our hashing actually works..
238 static struct assegment
*assegment_normalise(struct assegment
*head
)
240 struct assegment
*seg
= head
, *pin
;
241 struct assegment
*tmp
;
249 /* Sort values SET segments, for determinism in paths to aid
250 * creation of hash values / path comparisons
251 * and because it helps other lesser implementations ;)
253 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
) {
257 qsort(seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
260 for (i
= 1; i
< seg
->length
; i
++) {
261 if (seg
->as
[tail
] == seg
->as
[i
])
266 seg
->as
[tail
] = seg
->as
[i
];
268 /* seg->length can be 0.. */
270 seg
->length
= tail
+ 1;
273 /* read ahead from the current, pinned segment while the
275 * are packable/mergeable. Append all following packable
277 * to the segment we have pinned and remove these appended
280 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
)) {
284 /* append the next sequence to the pinned sequence */
285 pin
= assegment_append_asns(pin
, seg
->as
, seg
->length
);
287 /* bypass the next sequence */
288 pin
->next
= seg
->next
;
290 /* get rid of the now referenceless segment */
299 static struct aspath
*aspath_new(void)
301 return XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
304 /* Free AS path structure. */
305 void aspath_free(struct aspath
*aspath
)
309 if (aspath
->segments
)
310 assegment_free_all(aspath
->segments
);
312 XFREE(MTYPE_AS_STR
, aspath
->str
);
315 json_object_free(aspath
->json
);
319 XFREE(MTYPE_AS_PATH
, aspath
);
322 /* Unintern aspath from AS path bucket. */
323 void aspath_unintern(struct aspath
**aspath
)
326 struct aspath
*asp
= *aspath
;
331 if (asp
->refcnt
== 0) {
332 /* This aspath must exist in aspath hash table. */
333 ret
= hash_release(ashash
, asp
);
340 /* Return the start or end delimiters for a particular Segment type */
341 #define AS_SEG_START 0
343 static char aspath_delimiter_char(uint8_t type
, uint8_t which
)
350 } aspath_delim_char
[] = {{AS_SET
, '{', '}'},
351 {AS_CONFED_SET
, '[', ']'},
352 {AS_CONFED_SEQUENCE
, '(', ')'},
355 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++) {
356 if (aspath_delim_char
[i
].type
== type
) {
357 if (which
== AS_SEG_START
)
358 return aspath_delim_char
[i
].start
;
359 else if (which
== AS_SEG_END
)
360 return aspath_delim_char
[i
].end
;
366 /* countup asns from this segment and index onward */
367 static int assegment_count_asns(struct assegment
*seg
, int from
)
372 count
+= seg
->length
;
374 count
+= (seg
->length
- from
);
382 unsigned int aspath_count_confeds(struct aspath
*aspath
)
385 struct assegment
*seg
= aspath
->segments
;
388 if (seg
->type
== AS_CONFED_SEQUENCE
)
389 count
+= seg
->length
;
390 else if (seg
->type
== AS_CONFED_SET
)
398 unsigned int aspath_count_hops(const struct aspath
*aspath
)
401 struct assegment
*seg
= aspath
->segments
;
404 if (seg
->type
== AS_SEQUENCE
)
405 count
+= seg
->length
;
406 else if (seg
->type
== AS_SET
)
414 /* Estimate size aspath /might/ take if encoded into an
417 * This is a quick estimate, not definitive! aspath_put()
418 * may return a different number!!
420 unsigned int aspath_size(struct aspath
*aspath
)
423 struct assegment
*seg
= aspath
->segments
;
426 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
432 /* Return highest public ASN in path */
433 as_t
aspath_highest(struct aspath
*aspath
)
435 struct assegment
*seg
= aspath
->segments
;
440 for (i
= 0; i
< seg
->length
; i
++)
441 if (seg
->as
[i
] > highest
442 && !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
443 highest
= seg
->as
[i
];
449 /* Return the left-most ASN in path */
450 as_t
aspath_leftmost(struct aspath
*aspath
)
452 struct assegment
*seg
= aspath
->segments
;
455 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
456 leftmost
= seg
->as
[0];
461 /* Return 1 if there are any 4-byte ASes in the path */
462 unsigned int aspath_has_as4(struct aspath
*aspath
)
464 struct assegment
*seg
= aspath
->segments
;
468 for (i
= 0; i
< seg
->length
; i
++)
469 if (seg
->as
[i
] > BGP_AS_MAX
)
476 /* Convert aspath structure to string expression. */
477 static void aspath_make_str_count(struct aspath
*as
, bool make_json
)
479 struct assegment
*seg
;
483 json_object
*jaspath_segments
= NULL
;
484 json_object
*jseg
= NULL
;
485 json_object
*jseg_list
= NULL
;
488 as
->json
= json_object_new_object();
489 jaspath_segments
= json_object_new_array();
495 json_object_string_add(as
->json
, "string", "Local");
496 json_object_object_add(as
->json
, "segments",
498 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
);
546 /* We might need to increase str_buf, particularly if path has
547 * differing segments types, our initial guesstimate above will
548 * have been wrong. Need 10 chars for ASN, a seperator each and
549 * potentially two segment delimiters, plus a space between each
550 * segment and trailing zero.
552 * This definitely didn't work with the value of 5 bytes and
555 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
556 if ((len
+ SEGMENT_STR_LEN(seg
)) > str_size
) {
557 str_size
= len
+ SEGMENT_STR_LEN(seg
);
558 str_buf
= XREALLOC(MTYPE_AS_STR
, str_buf
, str_size
);
561 #undef SEGMENT_STR_LEN
563 if (seg
->type
!= AS_SEQUENCE
)
565 str_buf
+ len
, str_size
- len
, "%c",
566 aspath_delimiter_char(seg
->type
, AS_SEG_START
));
569 jseg_list
= json_object_new_array();
571 /* write out the ASNs, with their seperators, bar the last one*/
572 for (i
= 0; i
< seg
->length
; i
++) {
574 json_object_array_add(
576 json_object_new_int(seg
->as
[i
]));
578 len
+= snprintf(str_buf
+ len
, str_size
- len
, "%u",
581 if (i
< (seg
->length
- 1))
582 len
+= snprintf(str_buf
+ len
, str_size
- len
,
587 jseg
= json_object_new_object();
588 json_object_string_add(
590 aspath_segment_type_str
[seg
->type
]);
591 json_object_object_add(jseg
, "list", jseg_list
);
592 json_object_array_add(jaspath_segments
, jseg
);
595 if (seg
->type
!= AS_SEQUENCE
)
597 str_buf
+ len
, str_size
- len
, "%c",
598 aspath_delimiter_char(seg
->type
, AS_SEG_END
));
600 len
+= snprintf(str_buf
+ len
, str_size
- len
, " ");
605 assert(len
< str_size
);
612 json_object_string_add(as
->json
, "string", str_buf
);
613 json_object_object_add(as
->json
, "segments", jaspath_segments
);
614 json_object_int_add(as
->json
, "length", aspath_count_hops(as
));
620 void aspath_str_update(struct aspath
*as
, bool make_json
)
623 XFREE(MTYPE_AS_STR
, as
->str
);
626 json_object_free(as
->json
);
630 aspath_make_str_count(as
, make_json
);
633 /* Intern allocated AS path. */
634 struct aspath
*aspath_intern(struct aspath
*aspath
)
638 /* Assert this AS path structure is not interned and has the string
639 representation built. */
640 assert(aspath
->refcnt
== 0);
643 /* Check AS path hash. */
644 find
= hash_get(ashash
, aspath
, hash_alloc_intern
);
653 /* Duplicate aspath structure. Created same aspath structure but
654 reference count and AS path string is cleared. */
655 struct aspath
*aspath_dup(struct aspath
*aspath
)
657 unsigned short buflen
= aspath
->str_len
+ 1;
660 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
663 if (aspath
->segments
)
664 new->segments
= assegment_dup_all(aspath
->segments
);
669 new->str
= XMALLOC(MTYPE_AS_STR
, buflen
);
670 new->str_len
= aspath
->str_len
;
672 /* copy the string data */
673 if (aspath
->str_len
> 0)
674 memcpy(new->str
, aspath
->str
, buflen
);
681 static void *aspath_hash_alloc(void *arg
)
683 const struct aspath
*aspath
= arg
;
686 /* Malformed AS path value. */
689 /* New aspath structure is needed. */
690 new = XMALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
692 /* Reuse segments and string representation */
694 new->segments
= aspath
->segments
;
695 new->str
= aspath
->str
;
696 new->str_len
= aspath
->str_len
;
697 new->json
= aspath
->json
;
702 /* parse as-segment byte stream in struct assegment */
703 static int assegments_parse(struct stream
*s
, size_t length
,
704 struct assegment
**result
, int use32bit
)
706 struct assegment_header segh
;
707 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
710 /* empty aspath (ie iBGP or somesuch) */
714 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
716 "[AS4SEG] Parse aspath segment: got total byte length %lu",
717 (unsigned long)length
);
719 if ((STREAM_READABLE(s
) < length
)
720 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
721 || (length
% AS16_VALUE_SIZE
))
724 while (bytes
< length
) {
728 if ((length
- bytes
) <= AS_HEADER_SIZE
) {
730 assegment_free_all(head
);
734 /* softly softly, get the header first on its own */
735 segh
.type
= stream_getc(s
);
736 segh
.length
= stream_getc(s
);
738 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
740 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
742 "[AS4SEG] Parse aspath segment: got type %d, length %d",
743 segh
.type
, segh
.length
);
746 if (((bytes
+ seg_size
) > length
)
747 /* 1771bis 4.3b: seg length contains one or more */
748 || (segh
.length
== 0)
749 /* Paranoia in case someone changes type of segment length.
750 * Shift both values by 0x10 to make the comparison operate
751 * on more, than 8 bits (otherwise it's a warning, bug
754 || ((sizeof segh
.length
> 1)
755 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
))) {
757 assegment_free_all(head
);
764 case AS_CONFED_SEQUENCE
:
769 assegment_free_all(head
);
773 /* now its safe to trust lengths */
774 seg
= assegment_new(segh
.type
, segh
.length
);
778 else /* it's the first segment */
781 for (i
= 0; i
< segh
.length
; i
++)
783 (use32bit
) ? stream_getl(s
) : stream_getw(s
);
787 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
789 "[AS4SEG] Parse aspath segment: Bytes now: %lu",
790 (unsigned long)bytes
);
795 *result
= assegment_normalise(head
);
799 /* AS path parse function. pnt is a pointer to byte stream and length
800 is length of byte stream. If there is same AS path in the the AS
801 path hash then return it else make new AS path structure.
803 On error NULL is returned.
805 struct aspath
*aspath_parse(struct stream
*s
, size_t length
, int use32bit
)
810 /* If length is odd it's malformed AS path. */
811 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
812 * otherwise its malformed when length is larger than 2 and (length-2)
813 * is not dividable by 4.
814 * But... this time we're lazy
816 if (length
% AS16_VALUE_SIZE
)
819 memset(&as
, 0, sizeof(struct aspath
));
820 if (assegments_parse(s
, length
, &as
.segments
, use32bit
) < 0)
823 /* If already same aspath exist then return it. */
824 find
= hash_get(ashash
, &as
, aspath_hash_alloc
);
826 /* bug! should not happen, let the daemon crash below */
829 /* if the aspath was already hashed free temporary memory. */
831 assegment_free_all(as
.segments
);
832 /* aspath_key_make() always updates the string */
833 XFREE(MTYPE_AS_STR
, as
.str
);
835 json_object_free(as
.json
);
845 static void assegment_data_put(struct stream
*s
, as_t
*as
, int num
,
849 assert(num
<= AS_SEGMENT_MAX
);
851 for (i
= 0; i
< num
; i
++)
853 stream_putl(s
, as
[i
]);
855 if (as
[i
] <= BGP_AS_MAX
)
856 stream_putw(s
, as
[i
]);
858 stream_putw(s
, BGP_AS_TRANS
);
862 static size_t assegment_header_put(struct stream
*s
, uint8_t type
, int length
)
865 assert(length
<= AS_SEGMENT_MAX
);
866 stream_putc(s
, type
);
867 lenp
= stream_get_endp(s
);
868 stream_putc(s
, length
);
872 /* write aspath data to stream */
873 size_t aspath_put(struct stream
*s
, struct aspath
*as
, int use32bit
)
875 struct assegment
*seg
= as
->segments
;
878 if (!seg
|| seg
->length
== 0)
883 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
884 * At the moment, we would write out a partial aspath, and our
886 * will complain and drop the session :-/
888 * The general assumption here is that many things tested will
889 * never happen. And, in real live, up to now, they have not.
891 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
)
892 <= STREAM_WRITEABLE(s
))) {
893 struct assegment
*next
= seg
->next
;
898 /* Overlength segments have to be split up */
899 while ((seg
->length
- written
) > AS_SEGMENT_MAX
) {
900 assegment_header_put(s
, seg
->type
,
902 assegment_data_put(s
, (seg
->as
+ written
), AS_SEGMENT_MAX
,
904 written
+= AS_SEGMENT_MAX
;
905 bytes
+= ASSEGMENT_SIZE(AS_SEGMENT_MAX
,
909 /* write the final segment, probably is also the first
911 lenp
= assegment_header_put(s
, seg
->type
,
912 seg
->length
- written
);
913 assegment_data_put(s
, (seg
->as
+ written
),
914 seg
->length
- written
, use32bit
);
916 /* Sequence-type segments can be 'packed' together
917 * Case of a segment which was overlength and split up
918 * will be missed here, but that doesn't matter.
920 while (next
&& ASSEGMENTS_PACKABLE(seg
, next
)) {
921 /* NB: We should never normally get here given
923 * normalise aspath data when parse them.
925 * safe than sorry. We potentially could call
926 * assegment_normalise here instead, but it's
928 * easier to do it on the fly here rather than
930 * the segment list twice every time we write
935 /* Next segment's data can fit in this one */
936 assegment_data_put(s
, next
->as
, next
->length
,
939 /* update the length of the segment header */
940 stream_putc_at(s
, lenp
,
941 seg
->length
- written
943 asns_packed
+= next
->length
;
948 bytes
+= ASSEGMENT_SIZE(
949 seg
->length
- written
+ asns_packed
, use32bit
);
956 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
957 * We have no way to manage the storage, so we use a static stream
958 * wrapper around aspath_put.
960 uint8_t *aspath_snmp_pathseg(struct aspath
*as
, size_t *varlen
)
962 #define SNMP_PATHSEG_MAX 1024
965 snmp_stream
= stream_new(SNMP_PATHSEG_MAX
);
967 stream_reset(snmp_stream
);
973 aspath_put(snmp_stream
, as
, 0); /* use 16 bit for now here */
975 *varlen
= stream_get_endp(snmp_stream
);
976 return stream_pnt(snmp_stream
);
979 #define min(A,B) ((A) < (B) ? (A) : (B))
981 static struct assegment
*aspath_aggregate_as_set_add(struct aspath
*aspath
,
982 struct assegment
*asset
,
987 /* If this is first AS set member, create new as-set segment. */
989 asset
= assegment_new(AS_SET
, 1);
990 if (!aspath
->segments
)
991 aspath
->segments
= asset
;
993 struct assegment
*seg
= aspath
->segments
;
998 asset
->type
= AS_SET
;
1002 /* Check this AS value already exists or not. */
1003 for (i
= 0; i
< asset
->length
; i
++)
1004 if (asset
->as
[i
] == as
)
1008 asset
->as
= XREALLOC(MTYPE_AS_SEG_DATA
, asset
->as
,
1009 asset
->length
* AS_VALUE_SIZE
);
1010 asset
->as
[asset
->length
- 1] = as
;
1017 /* Modify as1 using as2 for aggregation. */
1018 struct aspath
*aspath_aggregate(struct aspath
*as1
, struct aspath
*as2
)
1024 struct assegment
*seg1
= as1
->segments
;
1025 struct assegment
*seg2
= as2
->segments
;
1026 struct aspath
*aspath
= NULL
;
1027 struct assegment
*asset
= NULL
;
1028 struct assegment
*prevseg
= NULL
;
1030 /* First of all check common leading sequence. */
1031 while (seg1
&& seg2
) {
1032 /* Check segment type. */
1033 if (seg1
->type
!= seg2
->type
)
1036 /* Minimum segment length. */
1037 minlen
= min(seg1
->length
, seg2
->length
);
1039 for (match
= 0; match
< minlen
; match
++)
1040 if (seg1
->as
[match
] != seg2
->as
[match
])
1044 struct assegment
*seg
= assegment_new(seg1
->type
, 0);
1046 seg
= assegment_append_asns(seg
, seg1
->as
, match
);
1049 aspath
= aspath_new();
1050 aspath
->segments
= seg
;
1052 prevseg
->next
= seg
;
1057 if (match
!= minlen
|| match
!= seg1
->length
1058 || seg1
->length
!= seg2
->length
)
1060 /* We are moving on to the next segment to reset match */
1069 aspath
= aspath_new();
1071 /* Make as-set using rest of all information. */
1074 for (i
= from
; i
< seg1
->length
; i
++)
1075 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1084 for (i
= from
; i
< seg2
->length
; i
++)
1085 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1092 assegment_normalise(aspath
->segments
);
1093 aspath_str_update(aspath
, false);
1097 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1098 attribute, check the leftmost AS number in the AS_PATH attribute is
1099 or not the peer's AS number. */
1100 int aspath_firstas_check(struct aspath
*aspath
, as_t asno
)
1102 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1105 if (aspath
->segments
&& (aspath
->segments
->type
== AS_SEQUENCE
)
1106 && (aspath
->segments
->as
[0] == asno
))
1112 unsigned int aspath_get_first_as(struct aspath
*aspath
)
1114 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1117 return aspath
->segments
->as
[0];
1120 unsigned int aspath_get_last_as(struct aspath
*aspath
)
1123 unsigned int last_as
= 0;
1124 const struct assegment
*seg
;
1126 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1129 seg
= aspath
->segments
;
1132 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1133 for (i
= 0; i
< seg
->length
; i
++)
1134 last_as
= seg
->as
[i
];
1141 /* AS path loop check. If aspath contains asno then return >= 1. */
1142 int aspath_loop_check(struct aspath
*aspath
, as_t asno
)
1144 struct assegment
*seg
;
1147 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1150 seg
= aspath
->segments
;
1155 for (i
= 0; i
< seg
->length
; i
++)
1156 if (seg
->as
[i
] == asno
)
1164 /* When all of AS path is private AS return 1. */
1165 int aspath_private_as_check(struct aspath
*aspath
)
1167 struct assegment
*seg
;
1169 if (!(aspath
&& aspath
->segments
))
1172 seg
= aspath
->segments
;
1177 for (i
= 0; i
< seg
->length
; i
++) {
1178 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1186 /* Return True if the entire ASPATH consist of the specified ASN */
1187 int aspath_single_asn_check(struct aspath
*aspath
, as_t asn
)
1189 struct assegment
*seg
;
1191 if (!(aspath
&& aspath
->segments
))
1194 seg
= aspath
->segments
;
1199 for (i
= 0; i
< seg
->length
; i
++) {
1200 if (seg
->as
[i
] != asn
)
1208 /* Replace all instances of the target ASN with our own ASN */
1209 struct aspath
*aspath_replace_specific_asn(struct aspath
*aspath
,
1210 as_t target_asn
, as_t our_asn
)
1213 struct assegment
*seg
;
1215 new = aspath_dup(aspath
);
1216 seg
= new->segments
;
1221 for (i
= 0; i
< seg
->length
; i
++) {
1222 if (seg
->as
[i
] == target_asn
)
1223 seg
->as
[i
] = our_asn
;
1228 aspath_str_update(new, false);
1232 /* Replace all private ASNs with our own ASN */
1233 struct aspath
*aspath_replace_private_asns(struct aspath
*aspath
, as_t asn
)
1236 struct assegment
*seg
;
1238 new = aspath_dup(aspath
);
1239 seg
= new->segments
;
1244 for (i
= 0; i
< seg
->length
; i
++) {
1245 if (BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1251 aspath_str_update(new, false);
1255 /* Remove all private ASNs */
1256 struct aspath
*aspath_remove_private_asns(struct aspath
*aspath
)
1259 struct assegment
*seg
;
1260 struct assegment
*new_seg
;
1261 struct assegment
*last_new_seg
;
1266 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
1270 last_new_seg
= NULL
;
1271 seg
= aspath
->segments
;
1275 for (i
= 0; i
< seg
->length
; i
++) {
1277 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1283 // The entire segment is private so skip it
1289 // The entire segment is public so copy it
1290 else if (public == seg
->length
) {
1291 new_seg
= assegment_dup(seg
);
1294 // The segment is a mix of public and private ASNs. Copy as many
1296 // there are public ASNs then come back and fill in only the
1299 new_seg
= assegment_new(seg
->type
, public);
1301 for (i
= 0; i
< seg
->length
; i
++) {
1303 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1304 new_seg
->as
[j
] = seg
->as
[i
];
1310 // This is the first segment so set the aspath segments pointer
1313 new->segments
= new_seg
;
1315 last_new_seg
->next
= new_seg
;
1317 last_new_seg
= new_seg
;
1321 aspath_str_update(new, false);
1325 /* AS path confed check. If aspath contains confed set or sequence then return
1327 int aspath_confed_check(struct aspath
*aspath
)
1329 struct assegment
*seg
;
1331 if (!(aspath
&& aspath
->segments
))
1334 seg
= aspath
->segments
;
1337 if (seg
->type
== AS_CONFED_SET
1338 || seg
->type
== AS_CONFED_SEQUENCE
)
1345 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1346 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1347 int aspath_left_confed_check(struct aspath
*aspath
)
1350 if (!(aspath
&& aspath
->segments
))
1353 if ((aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1354 || (aspath
->segments
->type
== AS_CONFED_SET
))
1360 /* Merge as1 to as2. as2 should be uninterned aspath. */
1361 static struct aspath
*aspath_merge(struct aspath
*as1
, struct aspath
*as2
)
1363 struct assegment
*last
, *new;
1368 last
= new = assegment_dup_all(as1
->segments
);
1370 /* find the last valid segment */
1371 while (last
&& last
->next
)
1374 last
->next
= as2
->segments
;
1375 as2
->segments
= new;
1376 aspath_str_update(as2
, false);
1380 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1381 struct aspath
*aspath_prepend(struct aspath
*as1
, struct aspath
*as2
)
1383 struct assegment
*seg1
;
1384 struct assegment
*seg2
;
1389 seg1
= as1
->segments
;
1390 seg2
= as2
->segments
;
1392 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1394 as2
->segments
= assegment_dup_all(as1
->segments
);
1395 aspath_str_update(as2
, false);
1399 /* If as1 is empty AS, no prepending to do. */
1403 /* find the tail as1's segment chain. */
1404 while (seg1
&& seg1
->next
)
1407 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1408 if (seg1
->type
== AS_SEQUENCE
&& seg2
->type
== AS_CONFED_SEQUENCE
)
1409 as2
= aspath_delete_confed_seq(as2
);
1411 /* Compare last segment type of as1 and first segment type of as2. */
1412 if (seg1
->type
!= seg2
->type
)
1413 return aspath_merge(as1
, as2
);
1415 if (seg1
->type
== AS_SEQUENCE
) {
1416 /* We have two chains of segments, as1->segments and seg2,
1417 * and we have to attach them together, merging the attaching
1418 * segments together into one.
1420 * 1. dupe as1->segments onto head of as2
1421 * 2. merge seg2's asns onto last segment of this new chain
1422 * 3. attach chain after seg2
1425 /* dupe as1 onto as2's head */
1426 seg1
= as2
->segments
= assegment_dup_all(as1
->segments
);
1428 /* refind the tail of as2, reusing seg1 */
1429 while (seg1
&& seg1
->next
)
1432 /* merge the old head, seg2, into tail, seg1 */
1433 seg1
= assegment_append_asns(seg1
, seg2
->as
, seg2
->length
);
1435 /* bypass the merged seg2, and attach any chain after it to
1436 * chain descending from as2's head
1438 seg1
->next
= seg2
->next
;
1440 /* seg2 is now referenceless and useless*/
1441 assegment_free(seg2
);
1443 /* we've now prepended as1's segment chain to as2, merging
1444 * the inbetween AS_SEQUENCE of seg2 in the process
1446 aspath_str_update(as2
, false);
1449 /* AS_SET merge code is needed at here. */
1450 return aspath_merge(as1
, as2
);
1452 /* XXX: Ermmm, what if as1 has multiple segments?? */
1457 /* Iterate over AS_PATH segments and wipe all occurences of the
1458 * listed AS numbers. Hence some segments may lose some or even
1459 * all data on the way, the operation is implemented as a smarter
1460 * version of aspath_dup(), which allocates memory to hold the new
1461 * data, not the original. The new AS path is returned.
1463 struct aspath
*aspath_filter_exclude(struct aspath
*source
,
1464 struct aspath
*exclude_list
)
1466 struct assegment
*srcseg
, *exclseg
, *lastseg
;
1467 struct aspath
*newpath
;
1469 newpath
= aspath_new();
1472 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
) {
1473 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1474 struct assegment
*newseg
;
1476 /* Find out, how much ASns are we going to pick from this
1478 * We can't perform filtering right inline, because the size of
1479 * the new segment isn't known at the moment yet.
1481 for (i
= 0; i
< srcseg
->length
; i
++) {
1483 for (exclseg
= exclude_list
->segments
;
1484 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1485 for (y
= 0; y
< exclseg
->length
; y
++)
1486 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1488 // There's no sense in testing
1489 // the rest of exclusion list,
1496 /* newlen is now the number of ASns to copy */
1500 /* Actual copying. Allocate memory and iterate once more,
1501 * performing filtering. */
1502 newseg
= assegment_new(srcseg
->type
, newlen
);
1503 for (i
= 0; i
< srcseg
->length
; i
++) {
1505 for (exclseg
= exclude_list
->segments
;
1506 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1507 for (y
= 0; y
< exclseg
->length
; y
++)
1508 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1514 newseg
->as
[done
++] = srcseg
->as
[i
];
1516 /* At his point newlen must be equal to done, and both must be
1518 * the filtered segment to the gross result. */
1520 newpath
->segments
= newseg
;
1522 lastseg
->next
= newseg
;
1525 aspath_str_update(newpath
, false);
1526 /* We are happy returning even an empty AS_PATH, because the
1528 * might expect this very behaviour. There's a mean to avoid this, if
1530 * by having a match rule against certain AS_PATH regexps in the
1533 aspath_free(source
);
1537 /* Add specified AS to the leftmost of aspath. */
1538 static struct aspath
*aspath_add_asns(struct aspath
*aspath
, as_t asno
,
1539 uint8_t type
, unsigned num
)
1541 struct assegment
*assegment
= aspath
->segments
;
1544 if (assegment
&& assegment
->type
== type
) {
1545 /* extend existing segment */
1547 assegment_prepend_asns(aspath
->segments
, asno
, num
);
1549 /* prepend with new segment */
1550 struct assegment
*newsegment
= assegment_new(type
, num
);
1551 for (i
= 0; i
< num
; i
++)
1552 newsegment
->as
[i
] = asno
;
1554 /* insert potentially replacing empty segment */
1555 if (assegment
&& assegment
->length
== 0) {
1556 newsegment
->next
= assegment
->next
;
1557 assegment_free(assegment
);
1559 newsegment
->next
= assegment
;
1560 aspath
->segments
= newsegment
;
1563 aspath_str_update(aspath
, false);
1567 /* Add specified AS to the leftmost of aspath num times. */
1568 struct aspath
*aspath_add_seq_n(struct aspath
*aspath
, as_t asno
, unsigned num
)
1570 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, num
);
1573 /* Add specified AS to the leftmost of aspath. */
1574 struct aspath
*aspath_add_seq(struct aspath
*aspath
, as_t asno
)
1576 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, 1);
1579 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1580 as2's leftmost AS is same return 1. */
1581 int aspath_cmp_left(const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1583 const struct assegment
*seg1
;
1584 const struct assegment
*seg2
;
1586 if (!(aspath1
&& aspath2
))
1589 seg1
= aspath1
->segments
;
1590 seg2
= aspath2
->segments
;
1592 /* If both paths are originated in this AS then we do want to compare
1597 /* find first non-confed segments for each */
1598 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1599 || (seg1
->type
== AS_CONFED_SET
)))
1602 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1603 || (seg2
->type
== AS_CONFED_SET
)))
1607 if (!(seg1
&& seg2
&& (seg1
->type
== AS_SEQUENCE
)
1608 && (seg2
->type
== AS_SEQUENCE
)))
1611 if (seg1
->as
[0] == seg2
->as
[0])
1617 /* Truncate an aspath after a number of hops, and put the hops remaining
1618 * at the front of another aspath. Needed for AS4 compat.
1620 * Returned aspath is a /new/ aspath, which should either by free'd or
1621 * interned by the caller, as desired.
1623 struct aspath
*aspath_reconcile_as4(struct aspath
*aspath
,
1624 struct aspath
*as4path
)
1626 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1627 struct aspath
*newpath
= NULL
, *mergedpath
;
1628 int hops
, cpasns
= 0;
1630 if (!aspath
|| !as4path
)
1633 seg
= aspath
->segments
;
1635 /* CONFEDs should get reconciled too.. */
1636 hops
= (aspath_count_hops(aspath
) + aspath_count_confeds(aspath
))
1637 - aspath_count_hops(as4path
);
1640 if (BGP_DEBUG(as4
, AS4
))
1642 "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1643 /* Something's gone wrong. The RFC says we should now ignore
1645 * which is daft behaviour - it contains vital loop-detection
1646 * information which must have been removed from AS_PATH.
1648 hops
= aspath_count_hops(aspath
);
1652 newpath
= aspath_dup(as4path
);
1653 aspath_str_update(newpath
, false);
1657 if (BGP_DEBUG(as4
, AS4
))
1659 "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1660 aspath
->str
, as4path
->str
);
1662 while (seg
&& hops
> 0) {
1663 switch (seg
->type
) {
1667 cpasns
= seg
->length
;
1669 case AS_CONFED_SEQUENCE
:
1670 /* Should never split a confed-sequence, if hop-count
1671 * suggests we must then something's gone wrong
1674 * Most important goal is to preserve AS_PATHs prime
1676 * as loop-detector, so we fudge the numbers so that the
1678 * confed-sequence is merged in.
1680 if (hops
< seg
->length
) {
1681 if (BGP_DEBUG(as4
, AS4
))
1683 "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1684 " across 2/4 ASN boundary somewhere, broken..");
1689 cpasns
= MIN(seg
->length
, hops
);
1690 hops
-= seg
->length
;
1693 assert(cpasns
<= seg
->length
);
1695 newseg
= assegment_new(seg
->type
, 0);
1696 newseg
= assegment_append_asns(newseg
, seg
->as
, cpasns
);
1699 newpath
= aspath_new();
1700 newpath
->segments
= newseg
;
1702 prevseg
->next
= newseg
;
1708 /* We may be able to join some segments here, and we must
1709 * do this because... we want normalised aspaths in out hash
1710 * and we do not want to stumble in aspath_put.
1712 mergedpath
= aspath_merge(newpath
, aspath_dup(as4path
));
1713 aspath_free(newpath
);
1714 mergedpath
->segments
= assegment_normalise(mergedpath
->segments
);
1715 aspath_str_update(mergedpath
, false);
1717 if (BGP_DEBUG(as4
, AS4
))
1718 zlog_debug("[AS4] result of synthesizing is %s",
1724 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1725 as2's leftmost AS is same return 1. (confederation as-path
1727 int aspath_cmp_left_confed(const struct aspath
*aspath1
,
1728 const struct aspath
*aspath2
)
1730 if (!(aspath1
&& aspath2
))
1733 if (!(aspath1
->segments
&& aspath2
->segments
))
1736 if ((aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1737 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
))
1740 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1746 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1747 * RFC 5065 section 4.1.c.1
1749 * 1) if any path segments of the AS_PATH are of the type
1750 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1751 * removed from the AS_PATH attribute, leaving the sanitized
1752 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1754 struct aspath
*aspath_delete_confed_seq(struct aspath
*aspath
)
1756 struct assegment
*seg
, *prev
, *next
;
1757 char removed_confed_segment
;
1759 if (!(aspath
&& aspath
->segments
))
1762 seg
= aspath
->segments
;
1763 removed_confed_segment
= 0;
1770 if (seg
->type
== AS_CONFED_SEQUENCE
1771 || seg
->type
== AS_CONFED_SET
) {
1772 /* This is the first segment in the aspath */
1773 if (aspath
->segments
== seg
)
1774 aspath
->segments
= seg
->next
;
1776 prev
->next
= seg
->next
;
1778 assegment_free(seg
);
1779 removed_confed_segment
= 1;
1786 if (removed_confed_segment
)
1787 aspath_str_update(aspath
, false);
1792 /* Add new AS number to the leftmost part of the aspath as
1793 AS_CONFED_SEQUENCE. */
1794 struct aspath
*aspath_add_confed_seq(struct aspath
*aspath
, as_t asno
)
1796 return aspath_add_asns(aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1799 /* Add new as value to as path structure. */
1800 static void aspath_as_add(struct aspath
*as
, as_t asno
)
1802 struct assegment
*seg
= as
->segments
;
1807 /* Last segment search procedure. */
1811 assegment_append_asns(seg
, &asno
, 1);
1814 /* Add new as segment to the as path. */
1815 static void aspath_segment_add(struct aspath
*as
, int type
)
1817 struct assegment
*seg
= as
->segments
;
1818 struct assegment
*new = assegment_new(type
, 0);
1828 struct aspath
*aspath_empty(void)
1830 return aspath_parse(NULL
, 0, 1); /* 32Bit ;-) */
1833 struct aspath
*aspath_empty_get(void)
1835 struct aspath
*aspath
;
1837 aspath
= aspath_new();
1838 aspath_make_str_count(aspath
, false);
1842 unsigned long aspath_count(void)
1844 return ashash
->count
;
1848 Theoretically, one as path can have:
1850 One BGP packet size should be less than 4096.
1851 One BGP attribute size should be less than 4096 - BGP header size.
1852 One BGP aspath size should be less than 4096 - BGP header size -
1853 BGP mandantry attribute size.
1856 /* AS path string lexical token enum. */
1861 as_token_confed_seq_start
,
1862 as_token_confed_seq_end
,
1863 as_token_confed_set_start
,
1864 as_token_confed_set_end
,
1868 /* Return next token and point for string parse. */
1869 static const char *aspath_gettoken(const char *buf
, enum as_token
*token
,
1870 unsigned long *asno
)
1872 const char *p
= buf
;
1874 /* Skip seperators (space for sequences, ',' for sets). */
1875 while (isspace((int)*p
) || *p
== ',')
1878 /* Check the end of the string and type specify characters
1884 *token
= as_token_set_start
;
1888 *token
= as_token_set_end
;
1892 *token
= as_token_confed_seq_start
;
1896 *token
= as_token_confed_seq_end
;
1900 *token
= as_token_confed_set_start
;
1904 *token
= as_token_confed_set_end
;
1909 /* Check actual AS value. */
1910 if (isdigit((int)*p
)) {
1913 *token
= as_token_asval
;
1917 while (isdigit((int)*p
)) {
1919 asval
+= (*p
- '0');
1926 /* There is no match then return unknown token. */
1927 *token
= as_token_unknown
;
1932 struct aspath
*aspath_str2aspath(const char *str
)
1934 enum as_token token
= as_token_unknown
;
1935 unsigned short as_type
;
1936 unsigned long asno
= 0;
1937 struct aspath
*aspath
;
1940 aspath
= aspath_new();
1942 /* We start default type as AS_SEQUENCE. */
1943 as_type
= AS_SEQUENCE
;
1946 while ((str
= aspath_gettoken(str
, &token
, &asno
)) != NULL
) {
1948 case as_token_asval
:
1950 aspath_segment_add(aspath
, as_type
);
1953 aspath_as_add(aspath
, asno
);
1955 case as_token_set_start
:
1957 aspath_segment_add(aspath
, as_type
);
1960 case as_token_set_end
:
1961 as_type
= AS_SEQUENCE
;
1964 case as_token_confed_seq_start
:
1965 as_type
= AS_CONFED_SEQUENCE
;
1966 aspath_segment_add(aspath
, as_type
);
1969 case as_token_confed_seq_end
:
1970 as_type
= AS_SEQUENCE
;
1973 case as_token_confed_set_start
:
1974 as_type
= AS_CONFED_SET
;
1975 aspath_segment_add(aspath
, as_type
);
1978 case as_token_confed_set_end
:
1979 as_type
= AS_SEQUENCE
;
1982 case as_token_unknown
:
1984 aspath_free(aspath
);
1989 aspath_make_str_count(aspath
, false);
1994 /* Make hash value by raw aspath data. */
1995 unsigned int aspath_key_make(void *p
)
1997 struct aspath
*aspath
= (struct aspath
*)p
;
1998 unsigned int key
= 0;
2001 aspath_str_update(aspath
, false);
2003 key
= jhash(aspath
->str
, aspath
->str_len
, 2334325);
2008 /* If two aspath have same value then return 1 else return 0 */
2009 int aspath_cmp(const void *arg1
, const void *arg2
)
2011 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2012 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2014 while (seg1
|| seg2
) {
2016 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2018 if (seg1
->type
!= seg2
->type
)
2020 if (seg1
->length
!= seg2
->length
)
2022 for (i
= 0; i
< seg1
->length
; i
++)
2023 if (seg1
->as
[i
] != seg2
->as
[i
])
2031 /* AS path hash initialize. */
2032 void aspath_init(void)
2034 ashash
= hash_create_size(32768, aspath_key_make
, aspath_cmp
,
2038 void aspath_finish(void)
2040 hash_clean(ashash
, (void (*)(void *))aspath_free
);
2045 stream_free(snmp_stream
);
2048 /* return and as path value */
2049 const char *aspath_print(struct aspath
*as
)
2051 return (as
? as
->str
: NULL
);
2054 /* Printing functions */
2055 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
2056 * AS_PATH wasn't empty.
2058 void aspath_print_vty(struct vty
*vty
, const char *format
, struct aspath
*as
,
2062 vty_out(vty
, format
, as
->str
);
2063 if (as
->str_len
&& strlen(suffix
))
2064 vty_out(vty
, "%s", suffix
);
2067 static void aspath_show_all_iterator(struct hash_backet
*backet
,
2072 as
= (struct aspath
*)backet
->data
;
2074 vty_out(vty
, "[%p:%u] (%ld) ", (void *)backet
, backet
->key
, as
->refcnt
);
2075 vty_out(vty
, "%s\n", as
->str
);
2078 /* Print all aspath and hash information. This function is used from
2079 `show [ip] bgp paths' command. */
2080 void aspath_print_all_vty(struct vty
*vty
)
2082 hash_iterate(ashash
, (void (*)(struct hash_backet
*,
2083 void *))aspath_show_all_iterator
,