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"
38 #include "bgpd/bgp_errors.h"
40 /* Attr. Flags and Attr. Type Code. */
41 #define AS_HEADER_SIZE 2
43 /* Now FOUR octets are used for AS value. */
44 #define AS_VALUE_SIZE sizeof (as_t)
45 /* This is the old one */
46 #define AS16_VALUE_SIZE sizeof (as16_t)
48 /* Maximum protocol segment length value */
49 #define AS_SEGMENT_MAX 255
51 /* The following length and size macros relate specifically to Quagga's
52 * internal representation of AS-Segments, not per se to the on-wire
53 * sizes and lengths. At present (200508) they sort of match, however
54 * the ONLY functions which should now about the on-wire syntax are
55 * aspath_put, assegment_put and assegment_parse.
57 * aspath_put returns bytes written, the only definitive record of
58 * size of wire-format attribute..
61 /* Calculated size in bytes of ASN segment data to hold N ASN's */
62 #define ASSEGMENT_DATA_SIZE(N, S) \
63 ((N) * ((S) ? AS_VALUE_SIZE : AS16_VALUE_SIZE))
65 /* Calculated size of segment struct to hold N ASN's */
66 #define ASSEGMENT_SIZE(N,S) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N,S))
68 /* AS segment octet length. */
69 #define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S)
71 /* AS_SEQUENCE segments can be packed together */
72 /* Can the types of X and Y be considered for packing? */
73 #define ASSEGMENT_TYPES_PACKABLE(X, Y) \
74 (((X)->type == (Y)->type) && ((X)->type == AS_SEQUENCE))
75 /* Types and length of X,Y suitable for packing? */
76 #define ASSEGMENTS_PACKABLE(X, Y) \
77 (ASSEGMENT_TYPES_PACKABLE((X), (Y)) \
78 && (((X)->length + (Y)->length) <= AS_SEGMENT_MAX))
80 /* As segment header - the on-wire representation
81 * NOT the internal representation!
83 struct assegment_header
{
88 /* Hash for aspath. This is the top level structure of AS path. */
89 static struct hash
*ashash
;
91 /* Stream for SNMP. See aspath_snmp_pathseg */
92 static struct stream
*snmp_stream
;
94 /* Callers are required to initialize the memory */
95 static as_t
*assegment_data_new(int num
)
97 return (XMALLOC(MTYPE_AS_SEG_DATA
, ASSEGMENT_DATA_SIZE(num
, 1)));
100 static void assegment_data_free(as_t
*asdata
)
102 XFREE(MTYPE_AS_SEG_DATA
, asdata
);
105 const char *aspath_segment_type_str
[] = {"as-invalid", "as-set", "as-sequence",
106 "as-confed-sequence", "as-confed-set"};
108 /* Get a new segment. Note that 0 is an allowed length,
109 * and will result in a segment with no allocated data segment.
110 * the caller should immediately assign data to the segment, as the segment
111 * otherwise is not generally valid
113 static struct assegment
*assegment_new(uint8_t type
, unsigned short length
)
115 struct assegment
*new;
117 new = XCALLOC(MTYPE_AS_SEG
, sizeof(struct assegment
));
120 new->as
= assegment_data_new(length
);
122 new->length
= length
;
128 static void assegment_free(struct assegment
*seg
)
134 assegment_data_free(seg
->as
);
135 memset(seg
, 0xfe, sizeof(struct assegment
));
136 XFREE(MTYPE_AS_SEG
, seg
);
141 /* free entire chain of segments */
142 static void assegment_free_all(struct assegment
*seg
)
144 struct assegment
*prev
;
149 assegment_free(prev
);
153 /* Duplicate just the given assegment and its data */
154 static struct assegment
*assegment_dup(struct assegment
*seg
)
156 struct assegment
*new;
158 new = assegment_new(seg
->type
, seg
->length
);
159 memcpy(new->as
, seg
->as
, ASSEGMENT_DATA_SIZE(new->length
, 1));
164 /* Duplicate entire chain of assegments, return the head */
165 static struct assegment
*assegment_dup_all(struct assegment
*seg
)
167 struct assegment
*new = NULL
;
168 struct assegment
*head
= NULL
;
172 new->next
= assegment_dup(seg
);
175 head
= new = assegment_dup(seg
);
182 /* prepend the as number to given segment, given num of times */
183 static struct assegment
*assegment_prepend_asns(struct assegment
*seg
,
192 if (num
>= AS_SEGMENT_MAX
)
193 return seg
; /* we don't do huge prepends */
195 if ((newas
= assegment_data_new(seg
->length
+ num
)) == NULL
)
198 for (i
= 0; i
< num
; i
++)
201 memcpy(newas
+ num
, seg
->as
, ASSEGMENT_DATA_SIZE(seg
->length
, 1));
202 assegment_data_free(seg
->as
);
209 /* append given array of as numbers to the segment */
210 static struct assegment
*assegment_append_asns(struct assegment
*seg
,
211 as_t
*asnos
, int num
)
218 newas
= XREALLOC(MTYPE_AS_SEG_DATA
, seg
->as
,
219 ASSEGMENT_DATA_SIZE(seg
->length
+ num
, 1));
222 memcpy(seg
->as
+ seg
->length
, asnos
,
223 ASSEGMENT_DATA_SIZE(num
, 1));
228 static int int_cmp(const void *p1
, const void *p2
)
230 const as_t
*as1
= p1
;
231 const as_t
*as2
= p2
;
233 return (*as1
== *as2
) ? 0 : ((*as1
> *as2
) ? 1 : -1);
236 /* normalise the segment.
237 * In particular, merge runs of AS_SEQUENCEs into one segment
238 * Internally, we do not care about the wire segment length limit, and
239 * we want each distinct AS_PATHs to have the exact same internal
240 * representation - eg, so that our hashing actually works..
242 static struct assegment
*assegment_normalise(struct assegment
*head
)
244 struct assegment
*seg
= head
, *pin
;
245 struct assegment
*tmp
;
253 /* Sort values SET segments, for determinism in paths to aid
254 * creation of hash values / path comparisons
255 * and because it helps other lesser implementations ;)
257 if (seg
->type
== AS_SET
|| seg
->type
== AS_CONFED_SET
) {
261 qsort(seg
->as
, seg
->length
, sizeof(as_t
), int_cmp
);
264 for (i
= 1; i
< seg
->length
; i
++) {
265 if (seg
->as
[tail
] == seg
->as
[i
])
270 seg
->as
[tail
] = seg
->as
[i
];
272 /* seg->length can be 0.. */
274 seg
->length
= tail
+ 1;
277 /* read ahead from the current, pinned segment while the
279 * are packable/mergeable. Append all following packable
281 * to the segment we have pinned and remove these appended
284 while (pin
->next
&& ASSEGMENT_TYPES_PACKABLE(pin
, pin
->next
)) {
288 /* append the next sequence to the pinned sequence */
289 pin
= assegment_append_asns(pin
, seg
->as
, seg
->length
);
291 /* bypass the next sequence */
292 pin
->next
= seg
->next
;
294 /* get rid of the now referenceless segment */
303 static struct aspath
*aspath_new(void)
305 return XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
308 /* Free AS path structure. */
309 void aspath_free(struct aspath
*aspath
)
313 if (aspath
->segments
)
314 assegment_free_all(aspath
->segments
);
315 XFREE(MTYPE_AS_STR
, aspath
->str
);
318 json_object_free(aspath
->json
);
322 XFREE(MTYPE_AS_PATH
, aspath
);
325 /* Unintern aspath from AS path bucket. */
326 void aspath_unintern(struct aspath
**aspath
)
329 struct aspath
*asp
= *aspath
;
334 if (asp
->refcnt
== 0) {
335 /* This aspath must exist in aspath hash table. */
336 ret
= hash_release(ashash
, asp
);
343 /* Return the start or end delimiters for a particular Segment type */
344 #define AS_SEG_START 0
346 static char aspath_delimiter_char(uint8_t type
, uint8_t which
)
353 } aspath_delim_char
[] = {{AS_SET
, '{', '}'},
354 {AS_CONFED_SET
, '[', ']'},
355 {AS_CONFED_SEQUENCE
, '(', ')'},
358 for (i
= 0; aspath_delim_char
[i
].type
!= 0; i
++) {
359 if (aspath_delim_char
[i
].type
== type
) {
360 if (which
== AS_SEG_START
)
361 return aspath_delim_char
[i
].start
;
362 else if (which
== AS_SEG_END
)
363 return aspath_delim_char
[i
].end
;
369 /* countup asns from this segment and index onward */
370 static int assegment_count_asns(struct assegment
*seg
, int from
)
375 count
+= seg
->length
;
377 count
+= (seg
->length
- from
);
385 unsigned int aspath_count_confeds(struct aspath
*aspath
)
388 struct assegment
*seg
= aspath
->segments
;
391 if (seg
->type
== AS_CONFED_SEQUENCE
)
392 count
+= seg
->length
;
393 else if (seg
->type
== AS_CONFED_SET
)
401 unsigned int aspath_count_hops(const struct aspath
*aspath
)
404 struct assegment
*seg
= aspath
->segments
;
407 if (seg
->type
== AS_SEQUENCE
)
408 count
+= seg
->length
;
409 else if (seg
->type
== AS_SET
)
417 /* Estimate size aspath /might/ take if encoded into an
420 * This is a quick estimate, not definitive! aspath_put()
421 * may return a different number!!
423 unsigned int aspath_size(struct aspath
*aspath
)
426 struct assegment
*seg
= aspath
->segments
;
429 size
+= ASSEGMENT_SIZE(seg
->length
, 1);
435 /* Return highest public ASN in path */
436 as_t
aspath_highest(struct aspath
*aspath
)
438 struct assegment
*seg
= aspath
->segments
;
443 for (i
= 0; i
< seg
->length
; i
++)
444 if (seg
->as
[i
] > highest
445 && !BGP_AS_IS_PRIVATE(seg
->as
[i
]))
446 highest
= seg
->as
[i
];
452 /* Return the left-most ASN in path */
453 as_t
aspath_leftmost(struct aspath
*aspath
)
455 struct assegment
*seg
= aspath
->segments
;
458 if (seg
&& seg
->length
&& seg
->type
== AS_SEQUENCE
)
459 leftmost
= seg
->as
[0];
464 /* Return 1 if there are any 4-byte ASes in the path */
465 unsigned int aspath_has_as4(struct aspath
*aspath
)
467 struct assegment
*seg
= aspath
->segments
;
471 for (i
= 0; i
< seg
->length
; i
++)
472 if (seg
->as
[i
] > BGP_AS_MAX
)
479 /* Convert aspath structure to string expression. */
480 static void aspath_make_str_count(struct aspath
*as
, bool make_json
)
482 struct assegment
*seg
;
486 json_object
*jaspath_segments
= NULL
;
487 json_object
*jseg
= NULL
;
488 json_object
*jseg_list
= NULL
;
491 as
->json
= json_object_new_object();
492 jaspath_segments
= json_object_new_array();
498 json_object_string_add(as
->json
, "string", "Local");
499 json_object_object_add(as
->json
, "segments",
501 json_object_int_add(as
->json
, "length", 0);
503 as
->str
= XMALLOC(MTYPE_AS_STR
, 1);
511 /* ASN takes 5 to 10 chars plus seperator, see below.
512 * If there is one differing segment type, we need an additional
513 * 2 chars for segment delimiters, and the final '\0'.
514 * Hopefully this is large enough to avoid hitting the realloc
515 * code below for most common sequences.
517 * This was changed to 10 after the well-known BGP assertion, which
518 * had hit some parts of the Internet in May of 2009.
520 #define ASN_STR_LEN (10 + 1)
521 str_size
= MAX(assegment_count_asns(seg
, 0) * ASN_STR_LEN
+ 2 + 1,
522 ASPATH_STR_DEFAULT_LEN
);
523 str_buf
= XMALLOC(MTYPE_AS_STR
, str_size
);
529 /* Check AS type validity. Set seperator for segment */
536 case AS_CONFED_SEQUENCE
:
540 XFREE(MTYPE_AS_STR
, str_buf
);
543 json_object_free(as
->json
);
549 /* We might need to increase str_buf, particularly if path has
550 * differing segments types, our initial guesstimate above will
551 * have been wrong. Need 10 chars for ASN, a seperator each and
552 * potentially two segment delimiters, plus a space between each
553 * segment and trailing zero.
555 * This definitely didn't work with the value of 5 bytes and
558 #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
559 if ((len
+ SEGMENT_STR_LEN(seg
)) > str_size
) {
560 str_size
= len
+ SEGMENT_STR_LEN(seg
);
561 str_buf
= XREALLOC(MTYPE_AS_STR
, str_buf
, str_size
);
564 #undef SEGMENT_STR_LEN
566 if (seg
->type
!= AS_SEQUENCE
)
568 str_buf
+ len
, str_size
- len
, "%c",
569 aspath_delimiter_char(seg
->type
, AS_SEG_START
));
572 jseg_list
= json_object_new_array();
574 /* write out the ASNs, with their seperators, bar the last one*/
575 for (i
= 0; i
< seg
->length
; i
++) {
577 json_object_array_add(
579 json_object_new_int(seg
->as
[i
]));
581 len
+= snprintf(str_buf
+ len
, str_size
- len
, "%u",
584 if (i
< (seg
->length
- 1))
585 len
+= snprintf(str_buf
+ len
, str_size
- len
,
590 jseg
= json_object_new_object();
591 json_object_string_add(
593 aspath_segment_type_str
[seg
->type
]);
594 json_object_object_add(jseg
, "list", jseg_list
);
595 json_object_array_add(jaspath_segments
, jseg
);
598 if (seg
->type
!= AS_SEQUENCE
)
600 str_buf
+ len
, str_size
- len
, "%c",
601 aspath_delimiter_char(seg
->type
, AS_SEG_END
));
603 len
+= snprintf(str_buf
+ len
, str_size
- len
, " ");
608 assert(len
< str_size
);
615 json_object_string_add(as
->json
, "string", str_buf
);
616 json_object_object_add(as
->json
, "segments", jaspath_segments
);
617 json_object_int_add(as
->json
, "length", aspath_count_hops(as
));
623 void aspath_str_update(struct aspath
*as
, bool make_json
)
625 XFREE(MTYPE_AS_STR
, as
->str
);
628 json_object_free(as
->json
);
632 aspath_make_str_count(as
, make_json
);
635 /* Intern allocated AS path. */
636 struct aspath
*aspath_intern(struct aspath
*aspath
)
640 /* Assert this AS path structure is not interned and has the string
641 representation built. */
642 assert(aspath
->refcnt
== 0);
645 /* Check AS path hash. */
646 find
= hash_get(ashash
, aspath
, hash_alloc_intern
);
655 /* Duplicate aspath structure. Created same aspath structure but
656 reference count and AS path string is cleared. */
657 struct aspath
*aspath_dup(struct aspath
*aspath
)
659 unsigned short buflen
= aspath
->str_len
+ 1;
662 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
665 if (aspath
->segments
)
666 new->segments
= assegment_dup_all(aspath
->segments
);
671 new->str
= XMALLOC(MTYPE_AS_STR
, buflen
);
672 new->str_len
= aspath
->str_len
;
674 /* copy the string data */
675 if (aspath
->str_len
> 0)
676 memcpy(new->str
, aspath
->str
, buflen
);
683 static void *aspath_hash_alloc(void *arg
)
685 const struct aspath
*aspath
= arg
;
688 /* Malformed AS path value. */
691 /* New aspath structure is needed. */
692 new = XMALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
694 /* Reuse segments and string representation */
696 new->segments
= aspath
->segments
;
697 new->str
= aspath
->str
;
698 new->str_len
= aspath
->str_len
;
699 new->json
= aspath
->json
;
704 /* parse as-segment byte stream in struct assegment */
705 static int assegments_parse(struct stream
*s
, size_t length
,
706 struct assegment
**result
, int use32bit
)
708 struct assegment_header segh
;
709 struct assegment
*seg
, *prev
= NULL
, *head
= NULL
;
712 /* empty aspath (ie iBGP or somesuch) */
716 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
718 "[AS4SEG] Parse aspath segment: got total byte length %lu",
719 (unsigned long)length
);
721 if ((STREAM_READABLE(s
) < length
)
722 || (STREAM_READABLE(s
) < AS_HEADER_SIZE
)
723 || (length
% AS16_VALUE_SIZE
))
726 while (bytes
< length
) {
730 if ((length
- bytes
) <= AS_HEADER_SIZE
) {
732 assegment_free_all(head
);
736 /* softly softly, get the header first on its own */
737 segh
.type
= stream_getc(s
);
738 segh
.length
= stream_getc(s
);
740 seg_size
= ASSEGMENT_SIZE(segh
.length
, use32bit
);
742 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
744 "[AS4SEG] Parse aspath segment: got type %d, length %d",
745 segh
.type
, segh
.length
);
748 if (((bytes
+ seg_size
) > length
)
749 /* 1771bis 4.3b: seg length contains one or more */
750 || (segh
.length
== 0)
751 /* Paranoia in case someone changes type of segment length.
752 * Shift both values by 0x10 to make the comparison operate
753 * on more, than 8 bits (otherwise it's a warning, bug
756 || ((sizeof segh
.length
> 1)
757 && (0x10 + segh
.length
> 0x10 + AS_SEGMENT_MAX
))) {
759 assegment_free_all(head
);
766 case AS_CONFED_SEQUENCE
:
771 assegment_free_all(head
);
775 /* now its safe to trust lengths */
776 seg
= assegment_new(segh
.type
, segh
.length
);
780 else /* it's the first segment */
783 for (i
= 0; i
< segh
.length
; i
++)
785 (use32bit
) ? stream_getl(s
) : stream_getw(s
);
789 if (BGP_DEBUG(as4
, AS4_SEGMENT
))
791 "[AS4SEG] Parse aspath segment: Bytes now: %lu",
792 (unsigned long)bytes
);
797 *result
= assegment_normalise(head
);
801 /* AS path parse function. pnt is a pointer to byte stream and length
802 is length of byte stream. If there is same AS path in the the AS
803 path hash then return it else make new AS path structure.
805 On error NULL is returned.
807 struct aspath
*aspath_parse(struct stream
*s
, size_t length
, int use32bit
)
812 /* If length is odd it's malformed AS path. */
813 /* Nit-picking: if (use32bit == 0) it is malformed if odd,
814 * otherwise its malformed when length is larger than 2 and (length-2)
815 * is not dividable by 4.
816 * But... this time we're lazy
818 if (length
% AS16_VALUE_SIZE
)
821 memset(&as
, 0, sizeof(struct aspath
));
822 if (assegments_parse(s
, length
, &as
.segments
, use32bit
) < 0)
825 /* If already same aspath exist then return it. */
826 find
= hash_get(ashash
, &as
, aspath_hash_alloc
);
828 /* bug! should not happen, let the daemon crash below */
831 /* if the aspath was already hashed free temporary memory. */
833 assegment_free_all(as
.segments
);
834 /* aspath_key_make() always updates the string */
835 XFREE(MTYPE_AS_STR
, as
.str
);
837 json_object_free(as
.json
);
847 static void assegment_data_put(struct stream
*s
, as_t
*as
, int num
,
851 assert(num
<= AS_SEGMENT_MAX
);
853 for (i
= 0; i
< num
; i
++)
855 stream_putl(s
, as
[i
]);
857 if (as
[i
] <= BGP_AS_MAX
)
858 stream_putw(s
, as
[i
]);
860 stream_putw(s
, BGP_AS_TRANS
);
864 static size_t assegment_header_put(struct stream
*s
, uint8_t type
, int length
)
867 assert(length
<= AS_SEGMENT_MAX
);
868 stream_putc(s
, type
);
869 lenp
= stream_get_endp(s
);
870 stream_putc(s
, length
);
874 /* write aspath data to stream */
875 size_t aspath_put(struct stream
*s
, struct aspath
*as
, int use32bit
)
877 struct assegment
*seg
= as
->segments
;
880 if (!seg
|| seg
->length
== 0)
885 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
886 * At the moment, we would write out a partial aspath, and our
888 * will complain and drop the session :-/
890 * The general assumption here is that many things tested will
891 * never happen. And, in real live, up to now, they have not.
893 while (seg
&& (ASSEGMENT_LEN(seg
, use32bit
)
894 <= STREAM_WRITEABLE(s
))) {
895 struct assegment
*next
= seg
->next
;
900 /* Overlength segments have to be split up */
901 while ((seg
->length
- written
) > AS_SEGMENT_MAX
) {
902 assegment_header_put(s
, seg
->type
,
904 assegment_data_put(s
, (seg
->as
+ written
), AS_SEGMENT_MAX
,
906 written
+= AS_SEGMENT_MAX
;
907 bytes
+= ASSEGMENT_SIZE(AS_SEGMENT_MAX
,
911 /* write the final segment, probably is also the first
913 lenp
= assegment_header_put(s
, seg
->type
,
914 seg
->length
- written
);
915 assegment_data_put(s
, (seg
->as
+ written
),
916 seg
->length
- written
, use32bit
);
918 /* Sequence-type segments can be 'packed' together
919 * Case of a segment which was overlength and split up
920 * will be missed here, but that doesn't matter.
922 while (next
&& ASSEGMENTS_PACKABLE(seg
, next
)) {
923 /* NB: We should never normally get here given
925 * normalise aspath data when parse them.
927 * safe than sorry. We potentially could call
928 * assegment_normalise here instead, but it's
930 * easier to do it on the fly here rather than
932 * the segment list twice every time we write
937 /* Next segment's data can fit in this one */
938 assegment_data_put(s
, next
->as
, next
->length
,
941 /* update the length of the segment header */
942 stream_putc_at(s
, lenp
,
943 seg
->length
- written
945 asns_packed
+= next
->length
;
950 bytes
+= ASSEGMENT_SIZE(
951 seg
->length
- written
+ asns_packed
, use32bit
);
958 /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
959 * We have no way to manage the storage, so we use a static stream
960 * wrapper around aspath_put.
962 uint8_t *aspath_snmp_pathseg(struct aspath
*as
, size_t *varlen
)
964 #define SNMP_PATHSEG_MAX 1024
967 snmp_stream
= stream_new(SNMP_PATHSEG_MAX
);
969 stream_reset(snmp_stream
);
975 aspath_put(snmp_stream
, as
, 0); /* use 16 bit for now here */
977 *varlen
= stream_get_endp(snmp_stream
);
978 return stream_pnt(snmp_stream
);
981 #define min(A,B) ((A) < (B) ? (A) : (B))
983 static struct assegment
*aspath_aggregate_as_set_add(struct aspath
*aspath
,
984 struct assegment
*asset
,
989 /* If this is first AS set member, create new as-set segment. */
991 asset
= assegment_new(AS_SET
, 1);
992 if (!aspath
->segments
)
993 aspath
->segments
= asset
;
995 struct assegment
*seg
= aspath
->segments
;
1000 asset
->type
= AS_SET
;
1004 /* Check this AS value already exists or not. */
1005 for (i
= 0; i
< asset
->length
; i
++)
1006 if (asset
->as
[i
] == as
)
1010 asset
->as
= XREALLOC(MTYPE_AS_SEG_DATA
, asset
->as
,
1011 asset
->length
* AS_VALUE_SIZE
);
1012 asset
->as
[asset
->length
- 1] = as
;
1019 /* Modify as1 using as2 for aggregation. */
1020 struct aspath
*aspath_aggregate(struct aspath
*as1
, struct aspath
*as2
)
1026 struct assegment
*seg1
= as1
->segments
;
1027 struct assegment
*seg2
= as2
->segments
;
1028 struct aspath
*aspath
= NULL
;
1029 struct assegment
*asset
= NULL
;
1030 struct assegment
*prevseg
= NULL
;
1032 /* First of all check common leading sequence. */
1033 while (seg1
&& seg2
) {
1034 /* Check segment type. */
1035 if (seg1
->type
!= seg2
->type
)
1038 /* Minimum segment length. */
1039 minlen
= min(seg1
->length
, seg2
->length
);
1041 for (match
= 0; match
< minlen
; match
++)
1042 if (seg1
->as
[match
] != seg2
->as
[match
])
1046 struct assegment
*seg
= assegment_new(seg1
->type
, 0);
1048 seg
= assegment_append_asns(seg
, seg1
->as
, match
);
1051 aspath
= aspath_new();
1052 aspath
->segments
= seg
;
1054 prevseg
->next
= seg
;
1059 if (match
!= minlen
|| match
!= seg1
->length
1060 || seg1
->length
!= seg2
->length
)
1062 /* We are moving on to the next segment to reset match */
1071 aspath
= aspath_new();
1073 /* Make as-set using rest of all information. */
1076 for (i
= from
; i
< seg1
->length
; i
++)
1077 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1086 for (i
= from
; i
< seg2
->length
; i
++)
1087 asset
= aspath_aggregate_as_set_add(aspath
, asset
,
1094 assegment_normalise(aspath
->segments
);
1095 aspath_str_update(aspath
, false);
1099 /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
1100 attribute, check the leftmost AS number in the AS_PATH attribute is
1101 or not the peer's AS number. */
1102 int aspath_firstas_check(struct aspath
*aspath
, as_t asno
)
1104 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1107 if (aspath
->segments
&& (aspath
->segments
->type
== AS_SEQUENCE
)
1108 && (aspath
->segments
->as
[0] == asno
))
1114 unsigned int aspath_get_first_as(struct aspath
*aspath
)
1116 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1119 return aspath
->segments
->as
[0];
1122 unsigned int aspath_get_last_as(struct aspath
*aspath
)
1125 unsigned int last_as
= 0;
1126 const struct assegment
*seg
;
1128 if (aspath
== NULL
|| aspath
->segments
== NULL
)
1131 seg
= aspath
->segments
;
1134 if (seg
->type
== AS_SEQUENCE
|| seg
->type
== AS_CONFED_SEQUENCE
)
1135 for (i
= 0; i
< seg
->length
; i
++)
1136 last_as
= seg
->as
[i
];
1143 /* AS path loop check. If aspath contains asno then return >= 1. */
1144 int aspath_loop_check(struct aspath
*aspath
, as_t asno
)
1146 struct assegment
*seg
;
1149 if ((aspath
== NULL
) || (aspath
->segments
== NULL
))
1152 seg
= aspath
->segments
;
1157 for (i
= 0; i
< seg
->length
; i
++)
1158 if (seg
->as
[i
] == asno
)
1166 /* When all of AS path is private AS return 1. */
1167 int aspath_private_as_check(struct aspath
*aspath
)
1169 struct assegment
*seg
;
1171 if (!(aspath
&& aspath
->segments
))
1174 seg
= aspath
->segments
;
1179 for (i
= 0; i
< seg
->length
; i
++) {
1180 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1188 /* Return True if the entire ASPATH consist of the specified ASN */
1189 int aspath_single_asn_check(struct aspath
*aspath
, as_t asn
)
1191 struct assegment
*seg
;
1193 if (!(aspath
&& aspath
->segments
))
1196 seg
= aspath
->segments
;
1201 for (i
= 0; i
< seg
->length
; i
++) {
1202 if (seg
->as
[i
] != asn
)
1210 /* Replace all instances of the target ASN with our own ASN */
1211 struct aspath
*aspath_replace_specific_asn(struct aspath
*aspath
,
1212 as_t target_asn
, as_t our_asn
)
1215 struct assegment
*seg
;
1217 new = aspath_dup(aspath
);
1218 seg
= new->segments
;
1223 for (i
= 0; i
< seg
->length
; i
++) {
1224 if (seg
->as
[i
] == target_asn
)
1225 seg
->as
[i
] = our_asn
;
1230 aspath_str_update(new, false);
1234 /* Replace all private ASNs with our own ASN */
1235 struct aspath
*aspath_replace_private_asns(struct aspath
*aspath
, as_t asn
)
1238 struct assegment
*seg
;
1240 new = aspath_dup(aspath
);
1241 seg
= new->segments
;
1246 for (i
= 0; i
< seg
->length
; i
++) {
1247 if (BGP_AS_IS_PRIVATE(seg
->as
[i
]))
1253 aspath_str_update(new, false);
1257 /* Remove all private ASNs */
1258 struct aspath
*aspath_remove_private_asns(struct aspath
*aspath
)
1261 struct assegment
*seg
;
1262 struct assegment
*new_seg
;
1263 struct assegment
*last_new_seg
;
1268 new = XCALLOC(MTYPE_AS_PATH
, sizeof(struct aspath
));
1272 last_new_seg
= NULL
;
1273 seg
= aspath
->segments
;
1277 for (i
= 0; i
< seg
->length
; i
++) {
1279 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1285 // The entire segment is private so skip it
1291 // The entire segment is public so copy it
1292 else if (public == seg
->length
) {
1293 new_seg
= assegment_dup(seg
);
1296 // The segment is a mix of public and private ASNs. Copy as many
1298 // there are public ASNs then come back and fill in only the
1301 new_seg
= assegment_new(seg
->type
, public);
1303 for (i
= 0; i
< seg
->length
; i
++) {
1305 if (!BGP_AS_IS_PRIVATE(seg
->as
[i
])) {
1306 new_seg
->as
[j
] = seg
->as
[i
];
1312 // This is the first segment so set the aspath segments pointer
1315 new->segments
= new_seg
;
1317 last_new_seg
->next
= new_seg
;
1319 last_new_seg
= new_seg
;
1323 aspath_str_update(new, false);
1327 /* AS path confed check. If aspath contains confed set or sequence then return
1329 int aspath_confed_check(struct aspath
*aspath
)
1331 struct assegment
*seg
;
1333 if (!(aspath
&& aspath
->segments
))
1336 seg
= aspath
->segments
;
1339 if (seg
->type
== AS_CONFED_SET
1340 || seg
->type
== AS_CONFED_SEQUENCE
)
1347 /* Leftmost AS path segment confed check. If leftmost AS segment is of type
1348 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
1349 int aspath_left_confed_check(struct aspath
*aspath
)
1352 if (!(aspath
&& aspath
->segments
))
1355 if ((aspath
->segments
->type
== AS_CONFED_SEQUENCE
)
1356 || (aspath
->segments
->type
== AS_CONFED_SET
))
1362 /* Merge as1 to as2. as2 should be uninterned aspath. */
1363 static struct aspath
*aspath_merge(struct aspath
*as1
, struct aspath
*as2
)
1365 struct assegment
*last
, *new;
1370 last
= new = assegment_dup_all(as1
->segments
);
1372 /* find the last valid segment */
1373 while (last
&& last
->next
)
1377 last
->next
= as2
->segments
;
1378 as2
->segments
= new;
1379 aspath_str_update(as2
, false);
1383 /* Prepend as1 to as2. as2 should be uninterned aspath. */
1384 struct aspath
*aspath_prepend(struct aspath
*as1
, struct aspath
*as2
)
1386 struct assegment
*as1segtail
;
1387 struct assegment
*as2segtail
;
1388 struct assegment
*as2seghead
;
1393 /* If as2 is empty, only need to dupe as1's chain onto as2 */
1394 if (as2
->segments
== NULL
) {
1395 as2
->segments
= assegment_dup_all(as1
->segments
);
1396 aspath_str_update(as2
, false);
1400 /* If as1 is empty AS, no prepending to do. */
1401 if (as1
->segments
== NULL
)
1404 /* find the tail as1's segment chain. */
1405 as1segtail
= as1
->segments
;
1406 while (as1segtail
&& as1segtail
->next
)
1407 as1segtail
= as1segtail
->next
;
1409 /* Delete any AS_CONFED_SEQUENCE segment from as2. */
1410 if (as1segtail
->type
== AS_SEQUENCE
1411 && as2
->segments
->type
== AS_CONFED_SEQUENCE
)
1412 as2
= aspath_delete_confed_seq(as2
);
1414 if (!as2
->segments
) {
1415 as2
->segments
= assegment_dup_all(as1
->segments
);
1416 aspath_str_update(as2
, false);
1420 /* Compare last segment type of as1 and first segment type of as2. */
1421 if (as1segtail
->type
!= as2
->segments
->type
)
1422 return aspath_merge(as1
, as2
);
1424 if (as1segtail
->type
== AS_SEQUENCE
) {
1425 /* We have two chains of segments, as1->segments and seg2,
1426 * and we have to attach them together, merging the attaching
1427 * segments together into one.
1429 * 1. dupe as1->segments onto head of as2
1430 * 2. merge seg2's asns onto last segment of this new chain
1431 * 3. attach chain after seg2
1435 as2seghead
= as2
->segments
;
1437 /* dupe as1 onto as2's head */
1438 as2segtail
= as2
->segments
= assegment_dup_all(as1
->segments
);
1440 /* refind the tail of as2 */
1441 while (as2segtail
&& as2segtail
->next
)
1442 as2segtail
= as2segtail
->next
;
1444 /* merge the old head, seg2, into tail, seg1 */
1445 assegment_append_asns(as2segtail
, as2seghead
->as
,
1446 as2seghead
->length
);
1449 * bypass the merged seg2, and attach any chain after it
1450 * to chain descending from as2's head
1453 as2segtail
->next
= as2seghead
->next
;
1455 /* as2->segments is now referenceless and useless */
1456 assegment_free(as2seghead
);
1458 /* we've now prepended as1's segment chain to as2, merging
1459 * the inbetween AS_SEQUENCE of seg2 in the process
1461 aspath_str_update(as2
, false);
1464 /* AS_SET merge code is needed at here. */
1465 return aspath_merge(as1
, as2
);
1467 /* XXX: Ermmm, what if as1 has multiple segments?? */
1472 /* Iterate over AS_PATH segments and wipe all occurences of the
1473 * listed AS numbers. Hence some segments may lose some or even
1474 * all data on the way, the operation is implemented as a smarter
1475 * version of aspath_dup(), which allocates memory to hold the new
1476 * data, not the original. The new AS path is returned.
1478 struct aspath
*aspath_filter_exclude(struct aspath
*source
,
1479 struct aspath
*exclude_list
)
1481 struct assegment
*srcseg
, *exclseg
, *lastseg
;
1482 struct aspath
*newpath
;
1484 newpath
= aspath_new();
1487 for (srcseg
= source
->segments
; srcseg
; srcseg
= srcseg
->next
) {
1488 unsigned i
, y
, newlen
= 0, done
= 0, skip_as
;
1489 struct assegment
*newseg
;
1491 /* Find out, how much ASns are we going to pick from this
1493 * We can't perform filtering right inline, because the size of
1494 * the new segment isn't known at the moment yet.
1496 for (i
= 0; i
< srcseg
->length
; i
++) {
1498 for (exclseg
= exclude_list
->segments
;
1499 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1500 for (y
= 0; y
< exclseg
->length
; y
++)
1501 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1503 // There's no sense in testing
1504 // the rest of exclusion list,
1511 /* newlen is now the number of ASns to copy */
1515 /* Actual copying. Allocate memory and iterate once more,
1516 * performing filtering. */
1517 newseg
= assegment_new(srcseg
->type
, newlen
);
1518 for (i
= 0; i
< srcseg
->length
; i
++) {
1520 for (exclseg
= exclude_list
->segments
;
1521 exclseg
&& !skip_as
; exclseg
= exclseg
->next
)
1522 for (y
= 0; y
< exclseg
->length
; y
++)
1523 if (srcseg
->as
[i
] == exclseg
->as
[y
]) {
1529 newseg
->as
[done
++] = srcseg
->as
[i
];
1531 /* At his point newlen must be equal to done, and both must be
1533 * the filtered segment to the gross result. */
1535 newpath
->segments
= newseg
;
1537 lastseg
->next
= newseg
;
1540 aspath_str_update(newpath
, false);
1541 /* We are happy returning even an empty AS_PATH, because the
1543 * might expect this very behaviour. There's a mean to avoid this, if
1545 * by having a match rule against certain AS_PATH regexps in the
1548 aspath_free(source
);
1552 /* Add specified AS to the leftmost of aspath. */
1553 static struct aspath
*aspath_add_asns(struct aspath
*aspath
, as_t asno
,
1554 uint8_t type
, unsigned num
)
1556 struct assegment
*assegment
= aspath
->segments
;
1559 if (assegment
&& assegment
->type
== type
) {
1560 /* extend existing segment */
1562 assegment_prepend_asns(aspath
->segments
, asno
, num
);
1564 /* prepend with new segment */
1565 struct assegment
*newsegment
= assegment_new(type
, num
);
1566 for (i
= 0; i
< num
; i
++)
1567 newsegment
->as
[i
] = asno
;
1569 /* insert potentially replacing empty segment */
1570 if (assegment
&& assegment
->length
== 0) {
1571 newsegment
->next
= assegment
->next
;
1572 assegment_free(assegment
);
1574 newsegment
->next
= assegment
;
1575 aspath
->segments
= newsegment
;
1578 aspath_str_update(aspath
, false);
1582 /* Add specified AS to the leftmost of aspath num times. */
1583 struct aspath
*aspath_add_seq_n(struct aspath
*aspath
, as_t asno
, unsigned num
)
1585 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, num
);
1588 /* Add specified AS to the leftmost of aspath. */
1589 struct aspath
*aspath_add_seq(struct aspath
*aspath
, as_t asno
)
1591 return aspath_add_asns(aspath
, asno
, AS_SEQUENCE
, 1);
1594 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1595 as2's leftmost AS is same return 1. */
1596 int aspath_cmp_left(const struct aspath
*aspath1
, const struct aspath
*aspath2
)
1598 const struct assegment
*seg1
;
1599 const struct assegment
*seg2
;
1601 if (!(aspath1
&& aspath2
))
1604 seg1
= aspath1
->segments
;
1605 seg2
= aspath2
->segments
;
1607 /* If both paths are originated in this AS then we do want to compare
1612 /* find first non-confed segments for each */
1613 while (seg1
&& ((seg1
->type
== AS_CONFED_SEQUENCE
)
1614 || (seg1
->type
== AS_CONFED_SET
)))
1617 while (seg2
&& ((seg2
->type
== AS_CONFED_SEQUENCE
)
1618 || (seg2
->type
== AS_CONFED_SET
)))
1622 if (!(seg1
&& seg2
&& (seg1
->type
== AS_SEQUENCE
)
1623 && (seg2
->type
== AS_SEQUENCE
)))
1626 if (seg1
->as
[0] == seg2
->as
[0])
1632 /* Truncate an aspath after a number of hops, and put the hops remaining
1633 * at the front of another aspath. Needed for AS4 compat.
1635 * Returned aspath is a /new/ aspath, which should either by free'd or
1636 * interned by the caller, as desired.
1638 struct aspath
*aspath_reconcile_as4(struct aspath
*aspath
,
1639 struct aspath
*as4path
)
1641 struct assegment
*seg
, *newseg
, *prevseg
= NULL
;
1642 struct aspath
*newpath
= NULL
, *mergedpath
;
1643 int hops
, cpasns
= 0;
1645 if (!aspath
|| !as4path
)
1648 seg
= aspath
->segments
;
1650 /* CONFEDs should get reconciled too.. */
1651 hops
= (aspath_count_hops(aspath
) + aspath_count_confeds(aspath
))
1652 - aspath_count_hops(as4path
);
1655 if (BGP_DEBUG(as4
, AS4
))
1657 EC_BGP_ASPATH_FEWER_HOPS
,
1658 "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
1659 /* Something's gone wrong. The RFC says we should now ignore
1661 * which is daft behaviour - it contains vital loop-detection
1662 * information which must have been removed from AS_PATH.
1664 hops
= aspath_count_hops(aspath
);
1668 newpath
= aspath_dup(as4path
);
1669 aspath_str_update(newpath
, false);
1673 if (BGP_DEBUG(as4
, AS4
))
1675 "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
1676 aspath
->str
, as4path
->str
);
1678 while (seg
&& hops
> 0) {
1679 switch (seg
->type
) {
1683 cpasns
= seg
->length
;
1685 case AS_CONFED_SEQUENCE
:
1686 /* Should never split a confed-sequence, if hop-count
1687 * suggests we must then something's gone wrong
1690 * Most important goal is to preserve AS_PATHs prime
1692 * as loop-detector, so we fudge the numbers so that the
1694 * confed-sequence is merged in.
1696 if (hops
< seg
->length
) {
1697 if (BGP_DEBUG(as4
, AS4
))
1699 "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
1700 " across 2/4 ASN boundary somewhere, broken..");
1705 cpasns
= MIN(seg
->length
, hops
);
1706 hops
-= seg
->length
;
1709 assert(cpasns
<= seg
->length
);
1711 newseg
= assegment_new(seg
->type
, 0);
1712 newseg
= assegment_append_asns(newseg
, seg
->as
, cpasns
);
1715 newpath
= aspath_new();
1716 newpath
->segments
= newseg
;
1718 prevseg
->next
= newseg
;
1724 /* We may be able to join some segments here, and we must
1725 * do this because... we want normalised aspaths in out hash
1726 * and we do not want to stumble in aspath_put.
1728 mergedpath
= aspath_merge(newpath
, aspath_dup(as4path
));
1729 aspath_free(newpath
);
1730 mergedpath
->segments
= assegment_normalise(mergedpath
->segments
);
1731 aspath_str_update(mergedpath
, false);
1733 if (BGP_DEBUG(as4
, AS4
))
1734 zlog_debug("[AS4] result of synthesizing is %s",
1740 /* Compare leftmost AS value for MED check. If as1's leftmost AS and
1741 as2's leftmost AS is same return 1. (confederation as-path
1743 bool aspath_cmp_left_confed(const struct aspath
*aspath1
,
1744 const struct aspath
*aspath2
)
1746 if (!(aspath1
&& aspath2
))
1749 if (!(aspath1
->segments
&& aspath2
->segments
))
1752 if ((aspath1
->segments
->type
!= AS_CONFED_SEQUENCE
)
1753 || (aspath2
->segments
->type
!= AS_CONFED_SEQUENCE
))
1756 if (aspath1
->segments
->as
[0] == aspath2
->segments
->as
[0])
1762 /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
1763 * RFC 5065 section 4.1.c.1
1765 * 1) if any path segments of the AS_PATH are of the type
1766 * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
1767 * removed from the AS_PATH attribute, leaving the sanitized
1768 * AS_PATH attribute to be operated on by steps 2, 3 or 4.
1770 struct aspath
*aspath_delete_confed_seq(struct aspath
*aspath
)
1772 struct assegment
*seg
, *prev
, *next
;
1773 char removed_confed_segment
;
1775 if (!(aspath
&& aspath
->segments
))
1778 seg
= aspath
->segments
;
1779 removed_confed_segment
= 0;
1786 if (seg
->type
== AS_CONFED_SEQUENCE
1787 || seg
->type
== AS_CONFED_SET
) {
1788 /* This is the first segment in the aspath */
1789 if (aspath
->segments
== seg
)
1790 aspath
->segments
= seg
->next
;
1792 prev
->next
= seg
->next
;
1794 assegment_free(seg
);
1795 removed_confed_segment
= 1;
1802 if (removed_confed_segment
)
1803 aspath_str_update(aspath
, false);
1808 /* Add new AS number to the leftmost part of the aspath as
1809 AS_CONFED_SEQUENCE. */
1810 struct aspath
*aspath_add_confed_seq(struct aspath
*aspath
, as_t asno
)
1812 return aspath_add_asns(aspath
, asno
, AS_CONFED_SEQUENCE
, 1);
1815 /* Add new as value to as path structure. */
1816 static void aspath_as_add(struct aspath
*as
, as_t asno
)
1818 struct assegment
*seg
= as
->segments
;
1823 /* Last segment search procedure. */
1827 assegment_append_asns(seg
, &asno
, 1);
1830 /* Add new as segment to the as path. */
1831 static void aspath_segment_add(struct aspath
*as
, int type
)
1833 struct assegment
*seg
= as
->segments
;
1834 struct assegment
*new = assegment_new(type
, 0);
1844 struct aspath
*aspath_empty(void)
1846 return aspath_parse(NULL
, 0, 1); /* 32Bit ;-) */
1849 struct aspath
*aspath_empty_get(void)
1851 struct aspath
*aspath
;
1853 aspath
= aspath_new();
1854 aspath_make_str_count(aspath
, false);
1858 unsigned long aspath_count(void)
1860 return ashash
->count
;
1864 Theoretically, one as path can have:
1866 One BGP packet size should be less than 4096.
1867 One BGP attribute size should be less than 4096 - BGP header size.
1868 One BGP aspath size should be less than 4096 - BGP header size -
1869 BGP mandantry attribute size.
1872 /* AS path string lexical token enum. */
1877 as_token_confed_seq_start
,
1878 as_token_confed_seq_end
,
1879 as_token_confed_set_start
,
1880 as_token_confed_set_end
,
1884 /* Return next token and point for string parse. */
1885 static const char *aspath_gettoken(const char *buf
, enum as_token
*token
,
1886 unsigned long *asno
)
1888 const char *p
= buf
;
1890 /* Skip seperators (space for sequences, ',' for sets). */
1891 while (isspace((int)*p
) || *p
== ',')
1894 /* Check the end of the string and type specify characters
1900 *token
= as_token_set_start
;
1904 *token
= as_token_set_end
;
1908 *token
= as_token_confed_seq_start
;
1912 *token
= as_token_confed_seq_end
;
1916 *token
= as_token_confed_set_start
;
1920 *token
= as_token_confed_set_end
;
1925 /* Check actual AS value. */
1926 if (isdigit((int)*p
)) {
1929 *token
= as_token_asval
;
1933 while (isdigit((int)*p
)) {
1935 asval
+= (*p
- '0');
1942 /* There is no match then return unknown token. */
1943 *token
= as_token_unknown
;
1948 struct aspath
*aspath_str2aspath(const char *str
)
1950 enum as_token token
= as_token_unknown
;
1951 unsigned short as_type
;
1952 unsigned long asno
= 0;
1953 struct aspath
*aspath
;
1956 aspath
= aspath_new();
1958 /* We start default type as AS_SEQUENCE. */
1959 as_type
= AS_SEQUENCE
;
1962 while ((str
= aspath_gettoken(str
, &token
, &asno
)) != NULL
) {
1964 case as_token_asval
:
1966 aspath_segment_add(aspath
, as_type
);
1969 aspath_as_add(aspath
, asno
);
1971 case as_token_set_start
:
1973 aspath_segment_add(aspath
, as_type
);
1976 case as_token_set_end
:
1977 as_type
= AS_SEQUENCE
;
1980 case as_token_confed_seq_start
:
1981 as_type
= AS_CONFED_SEQUENCE
;
1982 aspath_segment_add(aspath
, as_type
);
1985 case as_token_confed_seq_end
:
1986 as_type
= AS_SEQUENCE
;
1989 case as_token_confed_set_start
:
1990 as_type
= AS_CONFED_SET
;
1991 aspath_segment_add(aspath
, as_type
);
1994 case as_token_confed_set_end
:
1995 as_type
= AS_SEQUENCE
;
1998 case as_token_unknown
:
2000 aspath_free(aspath
);
2005 aspath_make_str_count(aspath
, false);
2010 /* Make hash value by raw aspath data. */
2011 unsigned int aspath_key_make(const void *p
)
2013 const struct aspath
*aspath
= p
;
2014 unsigned int key
= 0;
2017 aspath_str_update((struct aspath
*)aspath
, false);
2019 key
= jhash(aspath
->str
, aspath
->str_len
, 2334325);
2024 /* If two aspath have same value then return 1 else return 0 */
2025 bool aspath_cmp(const void *arg1
, const void *arg2
)
2027 const struct assegment
*seg1
= ((const struct aspath
*)arg1
)->segments
;
2028 const struct assegment
*seg2
= ((const struct aspath
*)arg2
)->segments
;
2030 while (seg1
|| seg2
) {
2032 if ((!seg1
&& seg2
) || (seg1
&& !seg2
))
2034 if (seg1
->type
!= seg2
->type
)
2036 if (seg1
->length
!= seg2
->length
)
2038 for (i
= 0; i
< seg1
->length
; i
++)
2039 if (seg1
->as
[i
] != seg2
->as
[i
])
2047 /* AS path hash initialize. */
2048 void aspath_init(void)
2050 ashash
= hash_create_size(32768, aspath_key_make
, aspath_cmp
,
2054 void aspath_finish(void)
2056 hash_clean(ashash
, (void (*)(void *))aspath_free
);
2061 stream_free(snmp_stream
);
2064 /* return and as path value */
2065 const char *aspath_print(struct aspath
*as
)
2067 return (as
? as
->str
: NULL
);
2070 /* Printing functions */
2071 /* Feed the AS_PATH to the vty; the suffix string follows it only in case
2072 * AS_PATH wasn't empty.
2074 void aspath_print_vty(struct vty
*vty
, const char *format
, struct aspath
*as
,
2078 vty_out(vty
, format
, as
->str
);
2079 if (as
->str_len
&& strlen(suffix
))
2080 vty_out(vty
, "%s", suffix
);
2083 static void aspath_show_all_iterator(struct hash_bucket
*bucket
,
2088 as
= (struct aspath
*)bucket
->data
;
2090 vty_out(vty
, "[%p:%u] (%ld) ", (void *)bucket
, bucket
->key
, as
->refcnt
);
2091 vty_out(vty
, "%s\n", as
->str
);
2094 /* Print all aspath and hash information. This function is used from
2095 `show [ip] bgp paths' command. */
2096 void aspath_print_all_vty(struct vty
*vty
)
2098 hash_iterate(ashash
, (void (*)(struct hash_bucket
*,
2099 void *))aspath_show_all_iterator
,
2103 static struct aspath
*bgp_aggr_aspath_lookup(struct bgp_aggregate
*aggregate
,
2104 struct aspath
*aspath
)
2106 return hash_lookup(aggregate
->aspath_hash
, aspath
);
2109 static void *bgp_aggr_aspath_hash_alloc(void *p
)
2111 struct aspath
*ref
= (struct aspath
*)p
;
2112 struct aspath
*aspath
= NULL
;
2114 aspath
= aspath_dup(ref
);
2118 static void bgp_aggr_aspath_prepare(struct hash_backet
*hb
, void *arg
)
2120 struct aspath
*asmerge
= NULL
;
2121 struct aspath
*hb_aspath
= hb
->data
;
2122 struct aspath
**aggr_aspath
= arg
;
2125 asmerge
= aspath_aggregate(*aggr_aspath
, hb_aspath
);
2126 aspath_free(*aggr_aspath
);
2127 *aggr_aspath
= asmerge
;
2129 *aggr_aspath
= aspath_dup(hb_aspath
);
2132 void bgp_aggr_aspath_remove(void *arg
)
2134 struct aspath
*aspath
= arg
;
2136 aspath_free(aspath
);
2139 void bgp_compute_aggregate_aspath(struct bgp_aggregate
*aggregate
,
2140 struct aspath
*aspath
)
2142 struct aspath
*aggr_aspath
= NULL
;
2144 if ((aggregate
== NULL
) || (aspath
== NULL
))
2147 /* Create hash if not already created.
2149 if (aggregate
->aspath_hash
== NULL
)
2150 aggregate
->aspath_hash
= hash_create(
2151 aspath_key_make
, aspath_cmp
,
2152 "BGP Aggregator as-path hash");
2154 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2155 if (aggr_aspath
== NULL
) {
2156 /* Insert as-path into hash.
2158 aggr_aspath
= hash_get(aggregate
->aspath_hash
, aspath
,
2159 bgp_aggr_aspath_hash_alloc
);
2161 /* Compute aggregate's as-path.
2163 hash_iterate(aggregate
->aspath_hash
,
2164 bgp_aggr_aspath_prepare
,
2165 &aggregate
->aspath
);
2168 /* Increment refernce counter.
2170 aggr_aspath
->refcnt
++;
2173 void bgp_remove_aspath_from_aggregate(struct bgp_aggregate
*aggregate
,
2174 struct aspath
*aspath
)
2176 struct aspath
*aggr_aspath
= NULL
;
2177 struct aspath
*ret_aspath
= NULL
;
2179 if ((aggregate
== NULL
) || (aspath
== NULL
))
2182 if (aggregate
->aspath_hash
== NULL
)
2185 /* Look-up the aspath in the hash.
2187 aggr_aspath
= bgp_aggr_aspath_lookup(aggregate
, aspath
);
2189 aggr_aspath
->refcnt
--;
2191 if (aggr_aspath
->refcnt
== 0) {
2192 ret_aspath
= hash_release(aggregate
->aspath_hash
,
2194 aspath_free(ret_aspath
);
2196 /* Remove aggregate's old as-path.
2198 aspath_free(aggregate
->aspath
);
2199 aggregate
->aspath
= NULL
;
2201 /* Compute aggregate's as-path.
2203 hash_iterate(aggregate
->aspath_hash
,
2204 bgp_aggr_aspath_prepare
,
2205 &aggregate
->aspath
);