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));
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(uint8_t type
, uint8_t 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
, bool make_json
)
484 struct assegment
*seg
;
488 json_object
*jaspath_segments
= NULL
;
489 json_object
*jseg
= NULL
;
490 json_object
*jseg_list
= NULL
;
493 as
->json
= json_object_new_object();
494 jaspath_segments
= json_object_new_array();
500 json_object_string_add(as
->json
, "string", "Local");
501 json_object_object_add(as
->json
, "segments",
503 json_object_int_add(as
->json
, "length", 0);
505 as
->str
= XMALLOC(MTYPE_AS_STR
, 1);
513 /* ASN takes 5 to 10 chars plus seperator, see below.
514 * If there is one differing segment type, we need an additional
515 * 2 chars for segment delimiters, and the final '\0'.
516 * Hopefully this is large enough to avoid hitting the realloc
517 * code below for most common sequences.
519 * This was changed to 10 after the well-known BGP assertion, which
520 * had hit some parts of the Internet in May of 2009.
522 #define ASN_STR_LEN (10 + 1)
523 str_size
= MAX(assegment_count_asns(seg
, 0) * ASN_STR_LEN
+ 2 + 1,
524 ASPATH_STR_DEFAULT_LEN
);
525 str_buf
= XMALLOC(MTYPE_AS_STR
, str_size
);
531 /* Check AS type validity. Set seperator for segment */
538 case AS_CONFED_SEQUENCE
:
542 XFREE(MTYPE_AS_STR
, str_buf
);
545 json_object_free(as
->json
);
551 /* We might need to increase str_buf, particularly if path has
552 * differing segments types, our initial guesstimate above will
553 * have been wrong. Need 10 chars for ASN, a seperator each and
554 * potentially two segment delimiters, plus a space between each
555 * segment and trailing zero.
557 * This definitely didn't work with the value of 5 bytes and
560 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
561 if ((len
+ SEGMENT_STR_LEN(seg
)) > str_size
) {
562 str_size
= len
+ SEGMENT_STR_LEN(seg
);
563 str_buf
= XREALLOC(MTYPE_AS_STR
, str_buf
, str_size
);
566 #undef SEGMENT_STR_LEN
568 if (seg
->type
!= AS_SEQUENCE
)
570 str_buf
+ len
, str_size
- len
, "%c",
571 aspath_delimiter_char(seg
->type
, AS_SEG_START
));
574 jseg_list
= json_object_new_array();
576 /* write out the ASNs, with their seperators, bar the last one*/
577 for (i
= 0; i
< seg
->length
; i
++) {
579 json_object_array_add(
581 json_object_new_int(seg
->as
[i
]));
583 len
+= snprintf(str_buf
+ len
, str_size
- len
, "%u",
586 if (i
< (seg
->length
- 1))
587 len
+= snprintf(str_buf
+ len
, str_size
- len
,
592 jseg
= json_object_new_object();
593 json_object_string_add(
595 aspath_segment_type_str
[seg
->type
]);
596 json_object_object_add(jseg
, "list", jseg_list
);
597 json_object_array_add(jaspath_segments
, jseg
);
600 if (seg
->type
!= AS_SEQUENCE
)
602 str_buf
+ len
, str_size
- len
, "%c",
603 aspath_delimiter_char(seg
->type
, AS_SEG_END
));
605 len
+= snprintf(str_buf
+ len
, str_size
- len
, " ");
610 assert(len
< str_size
);
617 json_object_string_add(as
->json
, "string", str_buf
);
618 json_object_object_add(as
->json
, "segments", jaspath_segments
);
619 json_object_int_add(as
->json
, "length", aspath_count_hops(as
));
625 void aspath_str_update(struct aspath
*as
, bool make_json
)
628 XFREE(MTYPE_AS_STR
, as
->str
);
631 json_object_free(as
->json
);
635 aspath_make_str_count(as
, make_json
);
638 /* Intern allocated AS path. */
639 struct aspath
*aspath_intern(struct aspath
*aspath
)
643 /* Assert this AS path structure is not interned and has the string
644 representation built. */
645 assert(aspath
->refcnt
== 0);
648 /* Check AS path hash. */
649 find
= hash_get(ashash
, aspath
, hash_alloc_intern
);
658 /* Duplicate aspath structure. Created same aspath structure but
659 reference count and AS path string is cleared. */
660 struct aspath
*aspath_dup(struct aspath
*aspath
)
662 unsigned short buflen
= aspath
->str_len
+ 1;
665 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
668 if (aspath
->segments
)
669 new->segments
= assegment_dup_all(aspath
->segments
);
674 new->str
= XMALLOC(MTYPE_AS_STR
, buflen
);
675 new->str_len
= aspath
->str_len
;
677 /* copy the string data */
678 if (aspath
->str_len
> 0)
679 memcpy(new->str
, aspath
->str
, buflen
);
686 static void *aspath_hash_alloc(void *arg
)
688 const struct aspath
*aspath
= arg
;
691 /* Malformed AS path value. */
694 /* New aspath structure is needed. */
695 new = XMALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
697 /* Reuse segments and string representation */
699 new->segments
= aspath
->segments
;
700 new->str
= aspath
->str
;
701 new->str_len
= aspath
->str_len
;
702 new->json
= aspath
->json
;
707 /* parse as-segment byte stream in struct assegment */
708 static int assegments_parse(struct stream
*s
, size_t length
,
709 struct assegment
**result
, int use32bit
)
711 struct assegment_header segh
;
712 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
715 /* empty aspath (ie iBGP or somesuch) */
719 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
721 "[AS4SEG] Parse aspath segment: got total byte length %lu",
722 (unsigned long)length
);
724 if ((STREAM_READABLE(s
) < length
)
725 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
726 || (length
% AS16_VALUE_SIZE
))
729 while (bytes
< length
) {
733 if ((length
- bytes
) <= AS_HEADER_SIZE
) {
735 assegment_free_all(head
);
739 /* softly softly, get the header first on its own */
740 segh
.type
= stream_getc(s
);
741 segh
.length
= stream_getc(s
);
743 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
745 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
747 "[AS4SEG] Parse aspath segment: got type %d, length %d",
748 segh
.type
, segh
.length
);
751 if (((bytes
+ seg_size
) > length
)
752 /* 1771bis 4.3b: seg length contains one or more */
753 || (segh
.length
== 0)
754 /* Paranoia in case someone changes type of segment length.
755 * Shift both values by 0x10 to make the comparison operate
756 * on more, than 8 bits (otherwise it's a warning, bug
759 || ((sizeof segh
.length
> 1)
760 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
))) {
762 assegment_free_all(head
);
769 case AS_CONFED_SEQUENCE
:
774 assegment_free_all(head
);
778 /* now its safe to trust lengths */
779 seg
= assegment_new(segh
.type
, segh
.length
);
783 else /* it's the first segment */
786 for (i
= 0; i
< segh
.length
; i
++)
788 (use32bit
) ? stream_getl(s
) : stream_getw(s
);
792 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
794 "[AS4SEG] Parse aspath segment: Bytes now: %lu",
795 (unsigned long)bytes
);
800 *result
= assegment_normalise(head
);
804 /* AS path parse function. pnt is a pointer to byte stream and length
805 is length of byte stream. If there is same AS path in the the AS
806 path hash then return it else make new AS path structure.
808 On error NULL is returned.
810 struct aspath
*aspath_parse(struct stream
*s
, size_t length
, int use32bit
)
815 /* If length is odd it's malformed AS path. */
816 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
817 * otherwise its malformed when length is larger than 2 and (length-2)
818 * is not dividable by 4.
819 * But... this time we're lazy
821 if (length
% AS16_VALUE_SIZE
)
824 memset(&as
, 0, sizeof(struct aspath
));
825 if (assegments_parse(s
, length
, &as
.segments
, use32bit
) < 0)
828 /* If already same aspath exist then return it. */
829 find
= hash_get(ashash
, &as
, aspath_hash_alloc
);
831 /* bug! should not happen, let the daemon crash below */
834 /* if the aspath was already hashed free temporary memory. */
836 assegment_free_all(as
.segments
);
837 /* aspath_key_make() always updates the string */
838 XFREE(MTYPE_AS_STR
, as
.str
);
840 json_object_free(as
.json
);
850 static void assegment_data_put(struct stream
*s
, as_t
*as
, int num
,
854 assert(num
<= AS_SEGMENT_MAX
);
856 for (i
= 0; i
< num
; i
++)
858 stream_putl(s
, as
[i
]);
860 if (as
[i
] <= BGP_AS_MAX
)
861 stream_putw(s
, as
[i
]);
863 stream_putw(s
, BGP_AS_TRANS
);
867 static size_t assegment_header_put(struct stream
*s
, uint8_t type
, int length
)
870 assert(length
<= AS_SEGMENT_MAX
);
871 stream_putc(s
, type
);
872 lenp
= stream_get_endp(s
);
873 stream_putc(s
, length
);
877 /* write aspath data to stream */
878 size_t aspath_put(struct stream
*s
, struct aspath
*as
, int use32bit
)
880 struct assegment
*seg
= as
->segments
;
883 if (!seg
|| seg
->length
== 0)
888 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
889 * At the moment, we would write out a partial aspath, and our
891 * will complain and drop the session :-/
893 * The general assumption here is that many things tested will
894 * never happen. And, in real live, up to now, they have not.
896 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
)
897 <= STREAM_WRITEABLE(s
))) {
898 struct assegment
*next
= seg
->next
;
903 /* Overlength segments have to be split up */
904 while ((seg
->length
- written
) > AS_SEGMENT_MAX
) {
905 assegment_header_put(s
, seg
->type
,
907 assegment_data_put(s
, seg
->as
, AS_SEGMENT_MAX
,
909 written
+= AS_SEGMENT_MAX
;
910 bytes
+= ASSEGMENT_SIZE(AS_SEGMENT_MAX
,
914 /* write the final segment, probably is also the first
916 lenp
= assegment_header_put(s
, seg
->type
,
917 seg
->length
- written
);
918 assegment_data_put(s
, (seg
->as
+ written
),
919 seg
->length
- written
, use32bit
);
921 /* Sequence-type segments can be 'packed' together
922 * Case of a segment which was overlength and split up
923 * will be missed here, but that doesn't matter.
925 while (next
&& ASSEGMENTS_PACKABLE(seg
, next
)) {
926 /* NB: We should never normally get here given
928 * normalise aspath data when parse them.
930 * safe than sorry. We potentially could call
931 * assegment_normalise here instead, but it's
933 * easier to do it on the fly here rather than
935 * the segment list twice every time we write
940 /* Next segment's data can fit in this one */
941 assegment_data_put(s
, next
->as
, next
->length
,
944 /* update the length of the segment header */
945 stream_putc_at(s
, lenp
,
946 seg
->length
- written
948 asns_packed
+= next
->length
;
953 bytes
+= ASSEGMENT_SIZE(
954 seg
->length
- written
+ asns_packed
, use32bit
);
961 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
962 * We have no way to manage the storage, so we use a static stream
963 * wrapper around aspath_put.
965 uint8_t *aspath_snmp_pathseg(struct aspath
*as
, size_t *varlen
)
967 #define SNMP_PATHSEG_MAX 1024
970 snmp_stream
= stream_new(SNMP_PATHSEG_MAX
);
972 stream_reset(snmp_stream
);
978 aspath_put(snmp_stream
, as
, 0); /* use 16 bit for now here */
980 *varlen
= stream_get_endp(snmp_stream
);
981 return stream_pnt(snmp_stream
);
984 #define min(A,B) ((A) < (B) ? (A) : (B))
986 static struct assegment
*aspath_aggregate_as_set_add(struct aspath
*aspath
,
987 struct assegment
*asset
,
992 /* If this is first AS set member, create new as-set segment. */
994 asset
= assegment_new(AS_SET
, 1);
995 if (!aspath
->segments
)
996 aspath
->segments
= asset
;
998 struct assegment
*seg
= aspath
->segments
;
1003 asset
->type
= AS_SET
;
1007 /* Check this AS value already exists or not. */
1008 for (i
= 0; i
< asset
->length
; i
++)
1009 if (asset
->as
[i
] == as
)
1013 asset
->as
= XREALLOC(MTYPE_AS_SEG_DATA
, asset
->as
,
1014 asset
->length
* AS_VALUE_SIZE
);
1015 asset
->as
[asset
->length
- 1] = as
;
1022 /* Modify as1 using as2 for aggregation. */
1023 struct aspath
*aspath_aggregate(struct aspath
*as1
, struct aspath
*as2
)
1029 struct assegment
*seg1
= as1
->segments
;
1030 struct assegment
*seg2
= as2
->segments
;
1031 struct aspath
*aspath
= NULL
;
1032 struct assegment
*asset
= NULL
;
1033 struct assegment
*prevseg
= NULL
;
1035 /* First of all check common leading sequence. */
1036 while (seg1
&& seg2
) {
1037 /* Check segment type. */
1038 if (seg1
->type
!= seg2
->type
)
1041 /* Minimum segment length. */
1042 minlen
= min(seg1
->length
, seg2
->length
);
1044 for (match
= 0; match
< minlen
; match
++)
1045 if (seg1
->as
[match
] != seg2
->as
[match
])
1049 struct assegment
*seg
= assegment_new(seg1
->type
, 0);
1051 seg
= assegment_append_asns(seg
, seg1
->as
, match
);
1054 aspath
= aspath_new();
1055 aspath
->segments
= seg
;
1057 prevseg
->next
= seg
;
1062 if (match
!= minlen
|| match
!= seg1
->length
1063 || seg1
->length
!= seg2
->length
)
1065 /* We are moving on to the next segment to reset match */
1074 aspath
= aspath_new();
1076 /* Make as-set using rest of all information. */
1079 for (i
= from
; i
< seg1
->length
; i
++)
1080 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1089 for (i
= from
; i
< seg2
->length
; i
++)
1090 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1097 assegment_normalise(aspath
->segments
);
1098 aspath_str_update(aspath
, false);
1102 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1103 attribute, check the leftmost AS number in the AS_PATH attribute is
1104 or not the peer's AS number. */
1105 int aspath_firstas_check(struct aspath
*aspath
, as_t asno
)
1107 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1110 if (aspath
->segments
&& (aspath
->segments
->type
== AS_SEQUENCE
)
1111 && (aspath
->segments
->as
[0] == asno
))
1117 unsigned int aspath_get_first_as(struct aspath
*aspath
)
1119 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1122 return aspath
->segments
->as
[0];
1125 unsigned int aspath_get_last_as(struct aspath
*aspath
)
1128 unsigned int last_as
= 0;
1129 const struct assegment
*seg
;
1131 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1134 seg
= aspath
->segments
;
1137 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1138 for (i
= 0; i
< seg
->length
; i
++)
1139 last_as
= seg
->as
[i
];
1146 /* AS path loop check. If aspath contains asno then return >= 1. */
1147 int aspath_loop_check(struct aspath
*aspath
, as_t asno
)
1149 struct assegment
*seg
;
1152 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1155 seg
= aspath
->segments
;
1160 for (i
= 0; i
< seg
->length
; i
++)
1161 if (seg
->as
[i
] == asno
)
1169 /* When all of AS path is private AS return 1. */
1170 int aspath_private_as_check(struct aspath
*aspath
)
1172 struct assegment
*seg
;
1174 if (!(aspath
&& aspath
->segments
))
1177 seg
= aspath
->segments
;
1182 for (i
= 0; i
< seg
->length
; i
++) {
1183 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1191 /* Return True if the entire ASPATH consist of the specified ASN */
1192 int aspath_single_asn_check(struct aspath
*aspath
, as_t asn
)
1194 struct assegment
*seg
;
1196 if (!(aspath
&& aspath
->segments
))
1199 seg
= aspath
->segments
;
1204 for (i
= 0; i
< seg
->length
; i
++) {
1205 if (seg
->as
[i
] != asn
)
1213 /* Replace all instances of the target ASN with our own ASN */
1214 struct aspath
*aspath_replace_specific_asn(struct aspath
*aspath
,
1215 as_t target_asn
, as_t our_asn
)
1218 struct assegment
*seg
;
1220 new = aspath_dup(aspath
);
1221 seg
= new->segments
;
1226 for (i
= 0; i
< seg
->length
; i
++) {
1227 if (seg
->as
[i
] == target_asn
)
1228 seg
->as
[i
] = our_asn
;
1233 aspath_str_update(new, false);
1237 /* Replace all private ASNs with our own ASN */
1238 struct aspath
*aspath_replace_private_asns(struct aspath
*aspath
, as_t asn
)
1241 struct assegment
*seg
;
1243 new = aspath_dup(aspath
);
1244 seg
= new->segments
;
1249 for (i
= 0; i
< seg
->length
; i
++) {
1250 if (BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1256 aspath_str_update(new, false);
1260 /* Remove all private ASNs */
1261 struct aspath
*aspath_remove_private_asns(struct aspath
*aspath
)
1264 struct assegment
*seg
;
1265 struct assegment
*new_seg
;
1266 struct assegment
*last_new_seg
;
1271 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
1275 last_new_seg
= NULL
;
1276 seg
= aspath
->segments
;
1280 for (i
= 0; i
< seg
->length
; i
++) {
1282 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1288 // The entire segment is private so skip it
1294 // The entire segment is public so copy it
1295 else if (public == seg
->length
) {
1296 new_seg
= assegment_dup(seg
);
1299 // The segment is a mix of public and private ASNs. Copy as many
1301 // there are public ASNs then come back and fill in only the
1304 new_seg
= assegment_new(seg
->type
, public);
1306 for (i
= 0; i
< seg
->length
; i
++) {
1308 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1309 new_seg
->as
[j
] = seg
->as
[i
];
1315 // This is the first segment so set the aspath segments pointer
1318 new->segments
= new_seg
;
1320 last_new_seg
->next
= new_seg
;
1322 last_new_seg
= new_seg
;
1326 aspath_str_update(new, false);
1330 /* AS path confed check. If aspath contains confed set or sequence then return
1332 int aspath_confed_check(struct aspath
*aspath
)
1334 struct assegment
*seg
;
1336 if (!(aspath
&& aspath
->segments
))
1339 seg
= aspath
->segments
;
1342 if (seg
->type
== AS_CONFED_SET
1343 || seg
->type
== AS_CONFED_SEQUENCE
)
1350 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1351 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1352 int aspath_left_confed_check(struct aspath
*aspath
)
1355 if (!(aspath
&& aspath
->segments
))
1358 if ((aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1359 || (aspath
->segments
->type
== AS_CONFED_SET
))
1365 /* Merge as1 to as2. as2 should be uninterned aspath. */
1366 static struct aspath
*aspath_merge(struct aspath
*as1
, struct aspath
*as2
)
1368 struct assegment
*last
, *new;
1373 last
= new = assegment_dup_all(as1
->segments
);
1375 /* find the last valid segment */
1376 while (last
&& last
->next
)
1379 last
->next
= as2
->segments
;
1380 as2
->segments
= new;
1381 aspath_str_update(as2
, false);
1385 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1386 struct aspath
*aspath_prepend(struct aspath
*as1
, struct aspath
*as2
)
1388 struct assegment
*seg1
;
1389 struct assegment
*seg2
;
1394 seg1
= as1
->segments
;
1395 seg2
= as2
->segments
;
1397 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1399 as2
->segments
= assegment_dup_all(as1
->segments
);
1400 aspath_str_update(as2
, false);
1404 /* If as1 is empty AS, no prepending to do. */
1408 /* find the tail as1's segment chain. */
1409 while (seg1
&& seg1
->next
)
1412 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1413 if (seg1
->type
== AS_SEQUENCE
&& seg2
->type
== AS_CONFED_SEQUENCE
)
1414 as2
= aspath_delete_confed_seq(as2
);
1416 /* Compare last segment type of as1 and first segment type of as2. */
1417 if (seg1
->type
!= seg2
->type
)
1418 return aspath_merge(as1
, as2
);
1420 if (seg1
->type
== AS_SEQUENCE
) {
1421 /* We have two chains of segments, as1->segments and seg2,
1422 * and we have to attach them together, merging the attaching
1423 * segments together into one.
1425 * 1. dupe as1->segments onto head of as2
1426 * 2. merge seg2's asns onto last segment of this new chain
1427 * 3. attach chain after seg2
1430 /* dupe as1 onto as2's head */
1431 seg1
= as2
->segments
= assegment_dup_all(as1
->segments
);
1433 /* refind the tail of as2, reusing seg1 */
1434 while (seg1
&& seg1
->next
)
1437 /* merge the old head, seg2, into tail, seg1 */
1438 seg1
= assegment_append_asns(seg1
, seg2
->as
, seg2
->length
);
1440 /* bypass the merged seg2, and attach any chain after it to
1441 * chain descending from as2's head
1443 seg1
->next
= seg2
->next
;
1445 /* seg2 is now referenceless and useless*/
1446 assegment_free(seg2
);
1448 /* we've now prepended as1's segment chain to as2, merging
1449 * the inbetween AS_SEQUENCE of seg2 in the process
1451 aspath_str_update(as2
, false);
1454 /* AS_SET merge code is needed at here. */
1455 return aspath_merge(as1
, as2
);
1457 /* XXX: Ermmm, what if as1 has multiple segments?? */
1462 /* Iterate over AS_PATH segments and wipe all occurences of the
1463 * listed AS numbers. Hence some segments may lose some or even
1464 * all data on the way, the operation is implemented as a smarter
1465 * version of aspath_dup(), which allocates memory to hold the new
1466 * data, not the original. The new AS path is returned.
1468 struct aspath
*aspath_filter_exclude(struct aspath
*source
,
1469 struct aspath
*exclude_list
)
1471 struct assegment
*srcseg
, *exclseg
, *lastseg
;
1472 struct aspath
*newpath
;
1474 newpath
= aspath_new();
1477 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
) {
1478 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1479 struct assegment
*newseg
;
1481 /* Find out, how much ASns are we going to pick from this
1483 * We can't perform filtering right inline, because the size of
1484 * the new segment isn't known at the moment yet.
1486 for (i
= 0; i
< srcseg
->length
; i
++) {
1488 for (exclseg
= exclude_list
->segments
;
1489 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1490 for (y
= 0; y
< exclseg
->length
; y
++)
1491 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1493 // There's no sense in testing
1494 // the rest of exclusion list,
1501 /* newlen is now the number of ASns to copy */
1505 /* Actual copying. Allocate memory and iterate once more,
1506 * performing filtering. */
1507 newseg
= assegment_new(srcseg
->type
, newlen
);
1508 for (i
= 0; i
< srcseg
->length
; i
++) {
1510 for (exclseg
= exclude_list
->segments
;
1511 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1512 for (y
= 0; y
< exclseg
->length
; y
++)
1513 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1519 newseg
->as
[done
++] = srcseg
->as
[i
];
1521 /* At his point newlen must be equal to done, and both must be
1523 * the filtered segment to the gross result. */
1525 newpath
->segments
= newseg
;
1527 lastseg
->next
= newseg
;
1530 aspath_str_update(newpath
, false);
1531 /* We are happy returning even an empty AS_PATH, because the
1533 * might expect this very behaviour. There's a mean to avoid this, if
1535 * by having a match rule against certain AS_PATH regexps in the
1538 aspath_free(source
);
1542 /* Add specified AS to the leftmost of aspath. */
1543 static struct aspath
*aspath_add_asns(struct aspath
*aspath
, as_t asno
,
1544 uint8_t type
, unsigned num
)
1546 struct assegment
*assegment
= aspath
->segments
;
1549 if (assegment
&& assegment
->type
== type
) {
1550 /* extend existing segment */
1552 assegment_prepend_asns(aspath
->segments
, asno
, num
);
1554 /* prepend with new segment */
1555 struct assegment
*newsegment
= assegment_new(type
, num
);
1556 for (i
= 0; i
< num
; i
++)
1557 newsegment
->as
[i
] = asno
;
1559 /* insert potentially replacing empty segment */
1560 if (assegment
&& assegment
->length
== 0) {
1561 newsegment
->next
= assegment
->next
;
1562 assegment_free(assegment
);
1564 newsegment
->next
= assegment
;
1565 aspath
->segments
= newsegment
;
1568 aspath_str_update(aspath
, false);
1572 /* Add specified AS to the leftmost of aspath num times. */
1573 struct aspath
*aspath_add_seq_n(struct aspath
*aspath
, as_t asno
, unsigned num
)
1575 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, num
);
1578 /* Add specified AS to the leftmost of aspath. */
1579 struct aspath
*aspath_add_seq(struct aspath
*aspath
, as_t asno
)
1581 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, 1);
1584 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1585 as2's leftmost AS is same return 1. */
1586 int aspath_cmp_left(const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1588 const struct assegment
*seg1
;
1589 const struct assegment
*seg2
;
1591 if (!(aspath1
&& aspath2
))
1594 seg1
= aspath1
->segments
;
1595 seg2
= aspath2
->segments
;
1597 /* If both paths are originated in this AS then we do want to compare
1602 /* find first non-confed segments for each */
1603 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1604 || (seg1
->type
== AS_CONFED_SET
)))
1607 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1608 || (seg2
->type
== AS_CONFED_SET
)))
1612 if (!(seg1
&& seg2
&& (seg1
->type
== AS_SEQUENCE
)
1613 && (seg2
->type
== AS_SEQUENCE
)))
1616 if (seg1
->as
[0] == seg2
->as
[0])
1622 /* Truncate an aspath after a number of hops, and put the hops remaining
1623 * at the front of another aspath. Needed for AS4 compat.
1625 * Returned aspath is a /new/ aspath, which should either by free'd or
1626 * interned by the caller, as desired.
1628 struct aspath
*aspath_reconcile_as4(struct aspath
*aspath
,
1629 struct aspath
*as4path
)
1631 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1632 struct aspath
*newpath
= NULL
, *mergedpath
;
1633 int hops
, cpasns
= 0;
1635 if (!aspath
|| !as4path
)
1638 seg
= aspath
->segments
;
1640 /* CONFEDs should get reconciled too.. */
1641 hops
= (aspath_count_hops(aspath
) + aspath_count_confeds(aspath
))
1642 - aspath_count_hops(as4path
);
1645 if (BGP_DEBUG(as4
, AS4
))
1647 "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1648 /* Something's gone wrong. The RFC says we should now ignore
1650 * which is daft behaviour - it contains vital loop-detection
1651 * information which must have been removed from AS_PATH.
1653 hops
= aspath_count_hops(aspath
);
1657 newpath
= aspath_dup(as4path
);
1658 aspath_str_update(newpath
, false);
1662 if (BGP_DEBUG(as4
, AS4
))
1664 "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1665 aspath
->str
, as4path
->str
);
1667 while (seg
&& hops
> 0) {
1668 switch (seg
->type
) {
1672 cpasns
= seg
->length
;
1674 case AS_CONFED_SEQUENCE
:
1675 /* Should never split a confed-sequence, if hop-count
1676 * suggests we must then something's gone wrong
1679 * Most important goal is to preserve AS_PATHs prime
1681 * as loop-detector, so we fudge the numbers so that the
1683 * confed-sequence is merged in.
1685 if (hops
< seg
->length
) {
1686 if (BGP_DEBUG(as4
, AS4
))
1688 "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1689 " across 2/4 ASN boundary somewhere, broken..");
1694 cpasns
= MIN(seg
->length
, hops
);
1695 hops
-= seg
->length
;
1698 assert(cpasns
<= seg
->length
);
1700 newseg
= assegment_new(seg
->type
, 0);
1701 newseg
= assegment_append_asns(newseg
, seg
->as
, cpasns
);
1704 newpath
= aspath_new();
1705 newpath
->segments
= newseg
;
1707 prevseg
->next
= newseg
;
1713 /* We may be able to join some segments here, and we must
1714 * do this because... we want normalised aspaths in out hash
1715 * and we do not want to stumble in aspath_put.
1717 mergedpath
= aspath_merge(newpath
, aspath_dup(as4path
));
1718 aspath_free(newpath
);
1719 mergedpath
->segments
= assegment_normalise(mergedpath
->segments
);
1720 aspath_str_update(mergedpath
, false);
1722 if (BGP_DEBUG(as4
, AS4
))
1723 zlog_debug("[AS4] result of synthesizing is %s",
1729 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1730 as2's leftmost AS is same return 1. (confederation as-path
1732 int aspath_cmp_left_confed(const struct aspath
*aspath1
,
1733 const struct aspath
*aspath2
)
1735 if (!(aspath1
&& aspath2
))
1738 if (!(aspath1
->segments
&& aspath2
->segments
))
1741 if ((aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1742 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
))
1745 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1751 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1752 * RFC 5065 section 4.1.c.1
1754 * 1) if any path segments of the AS_PATH are of the type
1755 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1756 * removed from the AS_PATH attribute, leaving the sanitized
1757 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1759 struct aspath
*aspath_delete_confed_seq(struct aspath
*aspath
)
1761 struct assegment
*seg
, *prev
, *next
;
1762 char removed_confed_segment
;
1764 if (!(aspath
&& aspath
->segments
))
1767 seg
= aspath
->segments
;
1768 removed_confed_segment
= 0;
1775 if (seg
->type
== AS_CONFED_SEQUENCE
1776 || seg
->type
== AS_CONFED_SET
) {
1777 /* This is the first segment in the aspath */
1778 if (aspath
->segments
== seg
)
1779 aspath
->segments
= seg
->next
;
1781 prev
->next
= seg
->next
;
1783 assegment_free(seg
);
1784 removed_confed_segment
= 1;
1791 if (removed_confed_segment
)
1792 aspath_str_update(aspath
, false);
1797 /* Add new AS number to the leftmost part of the aspath as
1798 AS_CONFED_SEQUENCE. */
1799 struct aspath
*aspath_add_confed_seq(struct aspath
*aspath
, as_t asno
)
1801 return aspath_add_asns(aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1804 /* Add new as value to as path structure. */
1805 static void aspath_as_add(struct aspath
*as
, as_t asno
)
1807 struct assegment
*seg
= as
->segments
;
1812 /* Last segment search procedure. */
1816 assegment_append_asns(seg
, &asno
, 1);
1819 /* Add new as segment to the as path. */
1820 static void aspath_segment_add(struct aspath
*as
, int type
)
1822 struct assegment
*seg
= as
->segments
;
1823 struct assegment
*new = assegment_new(type
, 0);
1833 struct aspath
*aspath_empty(void)
1835 return aspath_parse(NULL
, 0, 1); /* 32Bit ;-) */
1838 struct aspath
*aspath_empty_get(void)
1840 struct aspath
*aspath
;
1842 aspath
= aspath_new();
1843 aspath_make_str_count(aspath
, false);
1847 unsigned long aspath_count(void)
1849 return ashash
->count
;
1853 Theoretically, one as path can have:
1855 One BGP packet size should be less than 4096.
1856 One BGP attribute size should be less than 4096 - BGP header size.
1857 One BGP aspath size should be less than 4096 - BGP header size -
1858 BGP mandantry attribute size.
1861 /* AS path string lexical token enum. */
1866 as_token_confed_seq_start
,
1867 as_token_confed_seq_end
,
1868 as_token_confed_set_start
,
1869 as_token_confed_set_end
,
1873 /* Return next token and point for string parse. */
1874 static const char *aspath_gettoken(const char *buf
, enum as_token
*token
,
1875 unsigned long *asno
)
1877 const char *p
= buf
;
1879 /* Skip seperators (space for sequences, ',' for sets). */
1880 while (isspace((int)*p
) || *p
== ',')
1883 /* Check the end of the string and type specify characters
1889 *token
= as_token_set_start
;
1893 *token
= as_token_set_end
;
1897 *token
= as_token_confed_seq_start
;
1901 *token
= as_token_confed_seq_end
;
1905 *token
= as_token_confed_set_start
;
1909 *token
= as_token_confed_set_end
;
1914 /* Check actual AS value. */
1915 if (isdigit((int)*p
)) {
1918 *token
= as_token_asval
;
1922 while (isdigit((int)*p
)) {
1924 asval
+= (*p
- '0');
1931 /* There is no match then return unknown token. */
1932 *token
= as_token_unknown
;
1937 struct aspath
*aspath_str2aspath(const char *str
)
1939 enum as_token token
= as_token_unknown
;
1940 unsigned short as_type
;
1941 unsigned long asno
= 0;
1942 struct aspath
*aspath
;
1945 aspath
= aspath_new();
1947 /* We start default type as AS_SEQUENCE. */
1948 as_type
= AS_SEQUENCE
;
1951 while ((str
= aspath_gettoken(str
, &token
, &asno
)) != NULL
) {
1953 case as_token_asval
:
1955 aspath_segment_add(aspath
, as_type
);
1958 aspath_as_add(aspath
, asno
);
1960 case as_token_set_start
:
1962 aspath_segment_add(aspath
, as_type
);
1965 case as_token_set_end
:
1966 as_type
= AS_SEQUENCE
;
1969 case as_token_confed_seq_start
:
1970 as_type
= AS_CONFED_SEQUENCE
;
1971 aspath_segment_add(aspath
, as_type
);
1974 case as_token_confed_seq_end
:
1975 as_type
= AS_SEQUENCE
;
1978 case as_token_confed_set_start
:
1979 as_type
= AS_CONFED_SET
;
1980 aspath_segment_add(aspath
, as_type
);
1983 case as_token_confed_set_end
:
1984 as_type
= AS_SEQUENCE
;
1987 case as_token_unknown
:
1989 aspath_free(aspath
);
1994 aspath_make_str_count(aspath
, false);
1999 /* Make hash value by raw aspath data. */
2000 unsigned int aspath_key_make(void *p
)
2002 struct aspath
*aspath
= (struct aspath
*)p
;
2003 unsigned int key
= 0;
2006 aspath_str_update(aspath
, false);
2008 key
= jhash(aspath
->str
, aspath
->str_len
, 2334325);
2013 /* If two aspath have same value then return 1 else return 0 */
2014 int aspath_cmp(const void *arg1
, const void *arg2
)
2016 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2017 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2019 while (seg1
|| seg2
) {
2021 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2023 if (seg1
->type
!= seg2
->type
)
2025 if (seg1
->length
!= seg2
->length
)
2027 for (i
= 0; i
< seg1
->length
; i
++)
2028 if (seg1
->as
[i
] != seg2
->as
[i
])
2036 /* AS path hash initialize. */
2037 void aspath_init(void)
2039 ashash
= hash_create_size(32768, aspath_key_make
, aspath_cmp
,
2043 void aspath_finish(void)
2045 hash_clean(ashash
, (void (*)(void *))aspath_free
);
2050 stream_free(snmp_stream
);
2053 /* return and as path value */
2054 const char *aspath_print(struct aspath
*as
)
2056 return (as
? as
->str
: NULL
);
2059 /* Printing functions */
2060 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
2061 * AS_PATH wasn't empty.
2063 void aspath_print_vty(struct vty
*vty
, const char *format
, struct aspath
*as
,
2067 vty_out(vty
, format
, as
->str
);
2068 if (as
->str_len
&& strlen(suffix
))
2069 vty_out(vty
, "%s", suffix
);
2072 static void aspath_show_all_iterator(struct hash_backet
*backet
,
2077 as
= (struct aspath
*)backet
->data
;
2079 vty_out(vty
, "[%p:%u] (%ld) ", (void *)backet
, backet
->key
, as
->refcnt
);
2080 vty_out(vty
, "%s\n", as
->str
);
2083 /* Print all aspath and hash information. This function is used from
2084 `show [ip] bgp paths' command. */
2085 void aspath_print_all_vty(struct vty
*vty
)
2087 hash_iterate(ashash
, (void (*)(struct hash_backet
*,
2088 void *))aspath_show_all_iterator
,