diff options
Diffstat (limited to 'bgpd')
| -rw-r--r-- | bgpd/ChangeLog | 100 | ||||
| -rw-r--r-- | bgpd/Makefile.am | 6 | ||||
| -rw-r--r-- | bgpd/bgp_aspath.c | 1343 | ||||
| -rw-r--r-- | bgpd/bgp_aspath.h | 31 | ||||
| -rw-r--r-- | bgpd/bgp_attr.c | 31 | ||||
| -rw-r--r-- | bgpd/bgp_route.c | 39 | ||||
| -rw-r--r-- | bgpd/bgp_snmp.c | 3 |
7 files changed, 992 insertions, 561 deletions
diff --git a/bgpd/ChangeLog b/bgpd/ChangeLog index 94eb596f..a4145f4d 100644 --- a/bgpd/ChangeLog +++ b/bgpd/ChangeLog @@ -1,5 +1,105 @@ 2005-09-10 Paul Jakma <paul.jakma@sun.com> + * Makefile.am: bgpd shouldn't list libgp's sources as its own. + Use LDADD. + * bgp_aspath.h: + (struct assegment) New struct, abstract representation of a + list of AS_PATH segments and the contained ASNs. + (struct aspath) Remove the raw-data related + fields, reference the abstract struct assegment instead. + Remove several other computed fields, it's just a + headache to maintain them and they're cheap to compute from + struct assegment. + (aspath_parse) parse a stream, not a pointer to raw data. + (aspath_count_{hops,confeds,size}) helpers to access + information formerly directly contained in struct aspath. + (aspath_snmp_pathseg) Helper for SNMP, BGP MIB wants + to be able to output hex representation of raw data. + * bgp_aspath.c: (general) partial-rewrite. Store aspath data + as an abstract singly-linked list of abstract segments, + rather than storing the raw data, and parsing it each and + every time. Remove several count/size fields which are cheap + to compute from the abstract segment structure. + (global) Include stream.h, needed for aspath_parse, and + others. Couple of helper macros added. + (struct assegment_header) Just the header, and only the + header. + (assegment_data_{new,free}) convenience functions for + AS_SEG_DATA allocation, the dynamic, per-segment array of + ASNs. + (assegment_{new,free,free_all,dup,dup_all}) convenience + functions for creating struct assegments. The _all forms will + follow the entire chain of segments from the given segment. + (assegment_prepend_asns) new function, prepend an ASN N times + to segment. + (assegment_append_asns) Append a list (array) of ASNs to + segment. + (int_cmp) convenience function for the aspath hash. + (assegment_normalise) new function. Normalise the given + segment chain to meet expectations of Quagga, and to + eliminate differing raw representations of the same paths. + Merge 'runs' of SEQUENCEs into one segment as our internal + segment is not limited by the protocol AS_PATH segment + length. Sort ASNs in SETs. + (aspath_new) Take void argument to quell warnings. Use the + assegment convenience functions. + (assegment_count_{asns,confeds,hops}) new functions to + compute at runtime values previously held in struct aspath. + (aspath_size) ditto. + (aspath_make_str_count) rewritten to stringify new + representation, and to be slightly easier to understand + hopefully. + (aspath_str_update) convenience function, update the aspath + str. Should investigate removing maintained string from + struct aspath, just run-time compute it, as per other fields. + It's just a maintenance headache, would save noticeable + amount of RAM with possibly not much extra run-time cost. + (aspath_dup) use the assegment dup functions. + (aspath_hash_alloc) Take void * argument to satisfy gcc. Use + the proper helper functions to dup data. + (assegments_parse) new function. parse raw AS_PATH data into + struct assegments. Normalise and return the head of the list. + (aspath_parse) Parse a stream, not pointer to raw data and + use assegments_parse to do it. + (assegment_data_put) Write out a single segment data in protocol + form to stream. + (assegment_header_put) ditto but for segment header. + (aspath_put) new function. As per previous but for an entire + struct aspath. + (aspath_snmp_pathseg) wrapper around aspath_put for + bgp_snmp.c. Uses a static buffer sadly. + (aspath_aggregate_as_set_add) rewritten to use assegments. + (aspath_aggregate) ditto + (aspath_{firstas,loop,private_as}_check) ditto + (aspath_{merge,prepend,add_one_as}) ditto + (aspath_cmp_left{_confed}) ditto + (aspath_delete_confed_seq) ditto, plus fixed to properly + delete all leading confed segments. + (aspath_as_add) Just use assegment_append_asns. + (aspath_segment_add) updated to use assegments. + (enum as_token) Add values for confeds + (aspath_gettoken) Add support for confeds + (aspath_str2aspath) ditto + (aspath_key_make) updated to use as_segments. Also, add + segment type into the hash value as appropriate. + (aspath_cmp) updated to use as_segments. + (aspath_print) don't segfault on NULL argument. + * bgp_attr.c: (bgp_attr_aspath) aspath_parse wants the stream + now. No need for manual forwarding of stream. + (bgp_packet_attribute) empty aspath is now denoted by NULL + segment field, length is gone. + Use aspath_size() to determine size. + (bgp_attr_init) Fix declaration, explicitely specify void + arg. + (bgp_dump_routes_attr) Use aspath_size() to determine size. + * bgp_route.c: (bgp_info_cmp) use the aspath_count_* functions. + (bgp_rib_withdraw) remove unused variable. Use + aspath_count_hops. + * bgp_snmp.c: (bgp4PathAttrTable) raw data is gone, use + aspath_snmp_pathseg to get the representation. + +2005-09-10 Paul Jakma <paul.jakma@sun.com> + * bgp_vty.c: (bgp_vty_init) gcc 4 compile fix. static function declarations shouldn't be inside functions. * bgp_dump.c: (bgp_dump_interval_add) ditto. diff --git a/bgpd/Makefile.am b/bgpd/Makefile.am index 86408b46..0fe82ae0 100644 --- a/bgpd/Makefile.am +++ b/bgpd/Makefile.am @@ -21,10 +21,8 @@ noinst_HEADERS = \ bgp_ecommunity.h bgp_mplsvpn.h bgp_nexthop.h bgp_damp.h bgp_table.h \ bgp_advertise.h bgp_snmp.h bgp_vty.h -bgpd_SOURCES = \ - bgp_main.c $(libbgp_a_SOURCES) - -bgpd_LDADD = ../lib/libzebra.la @LIBCAP@ +bgpd_SOURCES = bgp_main.c +bgpd_LDADD = libbgp.a ../lib/libzebra.la @LIBCAP@ examplesdir = $(exampledir) dist_examples_DATA = bgpd.conf.sample bgpd.conf.sample2 diff --git a/bgpd/bgp_aspath.c b/bgpd/bgp_aspath.c index d13ed186..7f85ea10 100644 --- a/bgpd/bgp_aspath.c +++ b/bgpd/bgp_aspath.c @@ -1,5 +1,6 @@ /* AS path management routines. Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro + Copyright (C) 2005 Sun Microsystems, Inc. This file is part of GNU Zebra. @@ -26,6 +27,7 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA #include "vty.h" #include "str.h" #include "log.h" +#include "stream.h" #include "bgpd/bgpd.h" #include "bgpd/bgp_aspath.h" @@ -36,22 +38,255 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA /* Two octet is used for AS value. */ #define AS_VALUE_SIZE sizeof (as_t) -/* AS segment octet length. */ -#define ASSEGMENT_LEN(X) ((X)->length * AS_VALUE_SIZE + AS_HEADER_SIZE) +/* Maximum protocol segment length value */ +#define AS_SEGMENT_MAX 255 + +/* The following length and size macros relate specifically to Quagga's + * internal representation of AS-Segments, not per se to the on-wire + * sizes and lengths. At present (200508) they sort of match, however + * the ONLY functions which should now about the on-wire syntax are + * aspath_put, assegment_put and assegment_parse. + */ + +/* Calculated size in bytes of ASN segment data to hold N ASN's */ +#define ASSEGMENT_DATA_SIZE(N) ((N) * AS_VALUE_SIZE) -/* To fetch and store as segment value. */ -struct assegment +/* Calculated size of segment struct to hold N ASN's */ +#define ASSEGMENT_SIZE(N) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N)) + +/* AS segment octet length. */ +#define ASSEGMENT_LEN(X) ASSEGMENT_SIZE((X)->length) + +/* AS_SEQUENCE segments can be packed together */ +/* Can the types of X and Y be considered for packing? */ +#define ASSEGMENT_TYPES_PACKABLE(X,Y) \ + ( ((X)->type == (Y)->type) \ + && ((X)->type == AS_SEQUENCE)) +/* Types and length of X,Y suitable for packing? */ +#define ASSEGMENTS_PACKABLE(X,Y) \ + ( ASSEGMENT_TYPES_PACKABLE( (X), (Y)) \ + && ( ((X)->length + (Y)->length) <= AS_SEGMENT_MAX ) ) + +/* As segment header - the on-wire representation + * NOT the internal representation! + */ +struct assegment_header { u_char type; u_char length; - as_t asval[1]; }; /* Hash for aspath. This is the top level structure of AS path. */ struct hash *ashash; +static inline as_t * +assegment_data_new (int num) +{ + return (XCALLOC (MTYPE_AS_SEG_DATA, ASSEGMENT_DATA_SIZE (num))); +} + +static inline void +assegment_data_free (as_t *asdata) +{ + XFREE (MTYPE_AS_SEG_DATA,asdata); +} + +/* Get a new segment. Note that 0 is an allowed length, + * and will result in a segment with no allocated data segment. + * the caller should immediately assign data to the segment, as the segment + * otherwise is not generally valid + */ +static struct assegment * +assegment_new (u_char type, u_short length) +{ + struct assegment *new; + + new = XCALLOC (MTYPE_AS_SEG, sizeof (struct assegment)); + + if (length) + new->as = assegment_data_new (length); + + new->length = length; + new->type = type; + + return new; +} + +static void +assegment_free (struct assegment *seg) +{ + if (!seg) + return; + + if (seg->as) + XFREE (MTYPE_AS_SEG_DATA, seg->as); + memset (seg, 0xfe, sizeof(struct assegment)); + XFREE (MTYPE_AS_SEG, seg); + + return; +} + +/* free entire chain of segments */ +static void +assegment_free_all (struct assegment *seg) +{ + struct assegment *prev; + + while (seg) + { + prev = seg; + seg = seg->next; + assegment_free (prev); + } +} + +/* Duplicate just the given assegment and its data */ +static struct assegment * +assegment_dup (struct assegment *seg) +{ + struct assegment *new; + + new = assegment_new (seg->type, seg->length); + memcpy (new->as, seg->as, ASSEGMENT_DATA_SIZE (new->length) ); + + return new; +} + +/* Duplicate entire chain of assegments, return the head */ +static struct assegment * +assegment_dup_all (struct assegment *seg) +{ + struct assegment *new = NULL; + struct assegment *head = NULL; + + while (seg) + { + if (head) + { + new->next = assegment_dup (seg); + new = new->next; + } + else + head = new = assegment_dup (seg); + + seg = seg->next; + } + return head; +} + +/* prepend the as number to given segment, given num of times */ +static struct assegment * +assegment_prepend_asns (struct assegment *seg, as_t asnum, int num) +{ + as_t *newas; + + if (!num) + return seg; + + if (num >= AS_SEGMENT_MAX) + return seg; /* we don't do huge prepends */ + + newas = assegment_data_new (seg->length + num); + + if (newas) + { + int i; + for (i = 0; i < num; i++) + newas[i] = asnum; + + memcpy (newas + num, seg->as, ASSEGMENT_DATA_SIZE (seg->length)); + XFREE (MTYPE_AS_SEG_DATA, seg->as); + seg->as = newas; + seg->length += num; + return seg; + } + + assegment_free_all (seg); + return NULL; +} + +/* append given array of as numbers to the segment */ +static struct assegment * +assegment_append_asns (struct assegment *seg, as_t *asnos, int num) +{ + seg->as = XREALLOC (MTYPE_AS_SEG_DATA, seg->as, + ASSEGMENT_DATA_SIZE (seg->length + num)); + + if (seg->as) + { + memcpy (seg->as + seg->length, asnos, ASSEGMENT_DATA_SIZE(num)); + seg->length += num; + return seg; + } + + assegment_free_all (seg); + return NULL; +} + +static int +int_cmp (const void *p1, const void *p2) +{ + const as_t *as1 = p1; + const as_t *as2 = p2; + + return (*as1 == *as2) + ? 0 : ( (*as1 > *as2) ? 1 : -1); +} + +/* normalise the segment. + * In particular, merge runs of AS_SEQUENCEs into one segment + * Internally, we do not care about the wire segment length limit, and + * we want each distinct AS_PATHs to have the exact same internal + * representation - eg, so that our hashing actually works.. + */ +static struct assegment * +assegment_normalise (struct assegment *head) +{ + struct assegment *seg = head, *pin; + struct assegment *tmp; + + if (!head) + return head; + + while (seg) + { + pin = seg; + + /* Sort values SET segments, for determinism in paths to aid + * creation of hash values / path comparisons + * and because it helps other lesser implementations ;) + */ + if (seg->type == AS_SET || seg->type == AS_CONFED_SET) + qsort (seg->as, seg->length, sizeof(as_t), int_cmp); + + /* read ahead from the current, pinned segment while the segments + * are packable/mergeable. Append all following packable segments + * to the segment we have pinned and remove these appended + * segments. + */ + while (pin->next && ASSEGMENT_TYPES_PACKABLE(pin, pin->next)) + { + tmp = pin->next; + seg = pin->next; + + /* append the next sequence to the pinned sequence */ + pin = assegment_append_asns (pin, seg->as, seg->length); + + /* bypass the next sequence */ + pin->next = seg->next; + + /* get rid of the now referenceless segment */ + assegment_free (tmp); + + } + + seg = pin->next; + } + return head; +} + static struct aspath * -aspath_new () +aspath_new (void) { struct aspath *aspath; @@ -66,8 +301,8 @@ aspath_free (struct aspath *aspath) { if (!aspath) return; - if (aspath->data) - XFREE (MTYPE_AS_SEG, aspath->data); + if (aspath->segments) + assegment_free_all (aspath->segments); if (aspath->str) XFREE (MTYPE_AS_STR, aspath->str); XFREE (MTYPE_AS_PATH, aspath); @@ -106,7 +341,6 @@ aspath_delimiter_char (u_char type, u_char which) } aspath_delim_char [] = { { AS_SET, '{', '}' }, - { AS_SEQUENCE, ' ', ' ' }, { AS_CONFED_SET, '[', ']' }, { AS_CONFED_SEQUENCE, '(', ')' }, { 0 } @@ -125,142 +359,179 @@ aspath_delimiter_char (u_char type, u_char which) return ' '; } +/* countup asns from this segment and index onward */ +static int +assegment_count_asns (struct assegment *seg, int from) +{ + int count = 0; + while (seg) + { + if (!from) + count += seg->length; + else + { + count += (seg->length - from); + from = 0; + } + seg = seg->next; + } + return count; +} + +unsigned int +aspath_count_confeds (struct aspath *aspath) +{ + int count = 0; + struct assegment *seg = aspath->segments; + + while (seg) + { + if (seg->type == AS_CONFED_SEQUENCE) + count += seg->length; + else if (seg->type == AS_CONFED_SET) + count++; + + seg = seg->next; + } + return count; +} + +unsigned int +aspath_count_hops (struct aspath *aspath) +{ + int count = 0; + struct assegment *seg = aspath->segments; + + while (seg) + { + if (seg->type == AS_SEQUENCE) + count += seg->length; + else if (seg->type == AS_SET) + count++; + + seg = seg->next; + } + return count; +} + +unsigned int +aspath_size (struct aspath *aspath) +{ + int size = 0; + struct assegment *seg = aspath->segments; + + while (seg) + { + size += ASSEGMENT_SIZE(seg->length); + seg = seg->next; + } + return size; +} + /* Convert aspath structure to string expression. */ static char * aspath_make_str_count (struct aspath *as) { - int space; - u_char type; - caddr_t pnt; - caddr_t end; - struct assegment *assegment; - int str_size = ASPATH_STR_DEFAULT_LEN; - int str_pnt; + struct assegment *seg; + int str_size; + int len = 0; char *str_buf; - int count = 0; - int confed_count = 0; /* Empty aspath. */ - if (as->length == 0) + if (!as->segments) { str_buf = XMALLOC (MTYPE_AS_STR, 1); str_buf[0] = '\0'; - as->count = count; - as->confed_count = confed_count; return str_buf; } - - /* Set default value. */ - space = 0; - type = AS_SEQUENCE; - - /* Set initial pointer. */ - pnt = as->data; - end = pnt + as->length; - + + seg = as->segments; + + /* ASN takes 5 chars at least, plus seperator, see below. + * If there is one differing segment type, we need an additional + * 2 chars for segment delimiters, and the final '\0'. + * Hopefully this is large enough to avoid hitting the realloc + * code below for most common sequences. + */ +#define ASN_STR_LEN (5 + 1) + str_size = MAX (assegment_count_asns (seg, 0) * ASN_STR_LEN + 2 + 1, + ASPATH_STR_DEFAULT_LEN); str_buf = XMALLOC (MTYPE_AS_STR, str_size); - str_pnt = 0; - - assegment = (struct assegment *) pnt; - while (pnt < end) + while (seg) { int i; - int estimate_len; - - /* For fetch value. */ - assegment = (struct assegment *) pnt; - - /* Check AS type validity. */ - if ((assegment->type != AS_SET) && - (assegment->type != AS_SEQUENCE) && - (assegment->type != AS_CONFED_SET) && - (assegment->type != AS_CONFED_SEQUENCE)) - { - XFREE (MTYPE_AS_STR, str_buf); - return NULL; - } - - /* Check AS length. */ - if ((pnt + (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE) > end) - { - XFREE (MTYPE_AS_STR, str_buf); - return NULL; - } - - /* Buffer length check. */ - estimate_len = ((assegment->length * 6) + 4); + char seperator; - /* String length check. */ - while (str_pnt + estimate_len >= str_size) - { - str_size *= 2; - str_buf = XREALLOC (MTYPE_AS_STR, str_buf, str_size); - } - - /* If assegment type is changed, print previous type's end - character. */ - if (type != AS_SEQUENCE) - str_buf[str_pnt++] = aspath_delimiter_char (type, AS_SEG_END); - if (space) - str_buf[str_pnt++] = ' '; - - if (assegment->type != AS_SEQUENCE) - str_buf[str_pnt++] = aspath_delimiter_char (assegment->type, AS_SEG_START); - - space = 0; - - /* Increment counts */ - switch (assegment->type) - { - case AS_SEQUENCE: - count += assegment->length; - break; - case AS_SET: - count++; - break; - case AS_CONFED_SEQUENCE: - confed_count += assegment->length; - break; - case AS_CONFED_SET: - confed_count++; - break; - } - - for (i = 0; i < assegment->length; i++) - { - int len; - - if (space) - { - if (assegment->type == AS_SET - || assegment->type == AS_CONFED_SET) - str_buf[str_pnt++] = ','; - else - str_buf[str_pnt++] = ' '; - } - else - space = 1; - - len = sprintf (str_buf + str_pnt, "%d", ntohs (assegment->asval[i])); - str_pnt += len; - } - - type = assegment->type; - pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE; + /* Check AS type validity. Set seperator for segment */ + switch (seg->type) + { + case AS_SET: + case AS_CONFED_SET: + seperator = ','; + break; + case AS_SEQUENCE: + case AS_CONFED_SEQUENCE: + seperator = ' '; + break; + default: + XFREE (MTYPE_AS_STR, str_buf); + return NULL; + } + + /* We might need to increase str_buf, particularly if path has + * differing segments types, our initial guesstimate above will + * have been wrong. need 5 chars for ASN, a seperator each and + * potentially two segment delimiters, plus a space between each + * segment and trailing zero. + */ +#define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1) + if ( (len + SEGMENT_STR_LEN(seg)) > str_size) + { + str_size = len + SEGMENT_STR_LEN(seg); + str_buf = XREALLOC (MTYPE_AS_STR, str_buf, str_size); + } +#undef ASN_STR_LEN +#undef SEGMENT_STR_LEN + + if (seg->type != AS_SEQUENCE) + len += snprintf (str_buf + len, str_size - len, + "%c", + aspath_delimiter_char (seg->type, AS_SEG_START)); + + /* write out the ASNs, with their seperators, bar the last one*/ + for (i = 0; i < seg->length; i++) + { + len += snprintf (str_buf + len, str_size - len, "%u", seg->as[i]); + + if (i < (seg->length - 1)) + len += snprintf (str_buf + len, str_size - len, "%c", seperator); + } + + if (seg->type != AS_SEQUENCE) + len += snprintf (str_buf + len, str_size - len, "%c", + aspath_delimiter_char (seg->type, AS_SEG_END)); + if (seg->next) + len += snprintf (str_buf + len, str_size - len, " "); + + seg = seg->next; } - - if (assegment->type != AS_SEQUENCE) - str_buf[str_pnt++] = aspath_delimiter_char (assegment->type, AS_SEG_END); - - str_buf[str_pnt] = '\0'; - - as->count = count; - as->confed_count = confed_count; + + assert (len < str_size); + + str_buf[len] = '\0'; return str_buf; } +static void +aspath_str_update (struct aspath *as) +{ + if (as->str) + XFREE (MTYPE_AS_STR, as->str); + as->str = aspath_make_str_count (as); +} + /* Intern allocated AS path. */ struct aspath * aspath_intern (struct aspath *aspath) @@ -274,7 +545,7 @@ aspath_intern (struct aspath *aspath) find = hash_get (ashash, aspath, hash_alloc_intern); if (find != aspath) - aspath_free (aspath); + aspath_free (aspath); find->refcnt++; @@ -291,43 +562,26 @@ aspath_dup (struct aspath *aspath) { struct aspath *new; - new = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); - memset (new, 0, sizeof (struct aspath)); + new = XCALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); - new->length = aspath->length; - - if (new->length) - { - new->data = XMALLOC (MTYPE_AS_SEG, aspath->length); - memcpy (new->data, aspath->data, aspath->length); - } + if (aspath->segments) + new->segments = assegment_dup_all (aspath->segments); else - new->data = NULL; + new->segments = NULL; - /* new->str = aspath_make_str_count (aspath); */ + new->str = aspath_make_str_count (aspath); return new; } static void * -aspath_hash_alloc (struct aspath *arg) +aspath_hash_alloc (void *arg) { struct aspath *aspath; /* New aspath strucutre is needed. */ - aspath = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); - memset ((void *) aspath, 0, sizeof (struct aspath)); - aspath->length = arg->length; - - /* In case of IBGP connection aspath's length can be zero. */ - if (arg->length) - { - aspath->data = XMALLOC (MTYPE_AS_SEG, arg->length); - memcpy (aspath->data, arg->data, arg->length); - } - else - aspath->data = NULL; - + aspath = aspath_dup (arg); + /* Make AS path string. */ aspath->str = aspath_make_str_count (aspath); @@ -341,23 +595,79 @@ aspath_hash_alloc (struct aspath *arg) return aspath; } +/* parse as-segment byte stream in struct assegment */ +struct assegment * +assegments_parse (struct stream *s, size_t length) +{ + struct assegment_header segh; + struct assegment *seg, *prev = NULL, *head = NULL; + size_t bytes = 0; + + /* empty aspath (ie iBGP or somesuch) */ + if (length == 0) + return NULL; + + /* basic checks */ + if ( (STREAM_READABLE(s) < length) + || (STREAM_READABLE(s) < AS_HEADER_SIZE) + || (length % AS_VALUE_SIZE)) + return NULL; + + while ( (STREAM_READABLE(s) > AS_HEADER_SIZE) + && (bytes < length)) + { + int i; + + /* softly softly, get the header first on its own */ + segh.type = stream_getc (s); + segh.length = stream_getc (s); + + /* check it.. */ + if ( ((bytes + ASSEGMENT_SIZE(segh.length)) > length) + /* 1771bis 4.3b: seg length contains one or more */ + || (segh.length == 0) + /* Paranoia in case someone changes type of segment length */ + || ((sizeof segh.length > 1) && segh.length > AS_SEGMENT_MAX)) + { + if (head) + assegment_free_all (head); + return NULL; + } + + /* now its safe to trust lengths */ + seg = assegment_new (segh.type, segh.length); + + if (head) + prev->next = seg; + else /* it's the first segment */ + head = prev = seg; + + for (i = 0; i < segh.length; i++) + seg->as[i] = stream_getw (s); + + bytes += ASSEGMENT_SIZE(segh.length); + + prev = seg; + } + + return assegment_normalise (head); +} + /* AS path parse function. pnt is a pointer to byte stream and length is length of byte stream. If there is same AS path in the the AS path hash then return it else make new AS path structure. */ struct aspath * -aspath_parse (caddr_t pnt, int length) +aspath_parse (struct stream *s, size_t length) { struct aspath as; struct aspath *find; /* If length is odd it's malformed AS path. */ - if (length % 2) + if (length % AS_VALUE_SIZE) return NULL; - /* Looking up aspath hash entry. */ - as.data = pnt; - as.length = length; - + as.segments = assegments_parse (s, length); + /* If already same aspath exist then return it. */ find = hash_get (ashash, &as, aspath_hash_alloc); if (! find) @@ -367,36 +677,111 @@ aspath_parse (caddr_t pnt, int length) return find; } -#define min(A,B) ((A) < (B) ? (A) : (B)) - -#define ASSEGMENT_SIZE(N) (AS_HEADER_SIZE + ((N) * AS_VALUE_SIZE)) +static inline void +assegment_data_put (struct stream *s, as_t *as, int num) +{ + int i; + assert (num <= AS_SEGMENT_MAX); + + for (i = 0; i < num; i++) + stream_putw (s, as[i]); +} -static struct aspath * -aspath_aggregate_segment_copy (struct aspath *aspath, struct assegment *seg, - int i) +static inline size_t +assegment_header_put (struct stream *s, u_char type, int length) { - struct assegment *newseg; + size_t lenp; + assert (length <= AS_SEGMENT_MAX); + stream_putc (s, type); + lenp = stream_get_endp (s); + stream_putc (s, length); + return lenp; +} - if (! aspath->data) +/* write aspath data to stream */ +void +aspath_put (struct stream *s, struct aspath *as) +{ + struct assegment *seg = as->segments; + + if (!seg || seg->length == 0) + return; + + if (seg) { - aspath->data = XMALLOC (MTYPE_AS_SEG, ASSEGMENT_SIZE (i)); - newseg = (struct assegment *) aspath->data; - aspath->length = ASSEGMENT_SIZE (i); + while (seg && (ASSEGMENT_LEN (seg) <= STREAM_WRITEABLE(s))) + { + int written = 0; + size_t lenp; + + /* Overlength segments have to be split up */ + while ( (seg->length - written) > AS_SEGMENT_MAX) + { + assegment_header_put (s, seg->type, AS_SEGMENT_MAX); + assegment_data_put (s, seg->as, AS_SEGMENT_MAX); + written += AS_SEGMENT_MAX; + } + + /* write the final segment, probably is also the first */ + lenp = assegment_header_put (s, seg->type, seg->length - written); + assegment_data_put (s, (seg->as + written), seg->length - written); + + /* Sequence-type segments can be 'packed' together + * Case of a segment which was overlength and split up + * will be missed here, but that doesn't matter. + */ + if (seg->next && ASSEGMENTS_PACKABLE (seg, seg->next)) + { + /* NB: We should never normally get here given we + * normalise aspath data when parse them. However, better + * safe than sorry. We potentially could call + * assegment_normalise here instead, but it's cheaper and + * easier to do it on the fly here rather than go through + * the segment list twice every time we write out + * aspath's. + */ + + /* Next segment's data can fit in this one */ + assegment_data_put (s, seg->next->as, seg->next->length); + + /* update the length of the segment header */ + stream_putc_at (s, lenp, + seg->length - written + seg->next->length); + seg = seg->next->next; /* skip to past next */ + } + else + seg = seg->next; + } } +} + +/* This is for SNMP BGP4PATHATTRASPATHSEGMENT + * We have no way to manage the storage, so we use a static stream + * wrapper around aspath_put. + */ +u_char * +aspath_snmp_pathseg (struct aspath *as, size_t *varlen) +{ +#define SNMP_PATHSEG_MAX 1024 + static struct stream *s = NULL; + + if (!s) + s = stream_new (SNMP_PATHSEG_MAX); else + stream_reset (s); + + if (!as) { - aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, - aspath->length + ASSEGMENT_SIZE (i)); - newseg = (struct assegment *) (aspath->data + aspath->length); - aspath->length += ASSEGMENT_SIZE (i); + *varlen = 0; + return NULL; } - - newseg->type = seg->type; - newseg->length = i; - memcpy (newseg->asval, seg->asval, (i * AS_VALUE_SIZE)); - - return aspath; + aspath_put (s, as); + + *varlen = stream_get_endp (s); + return stream_pnt(s); } + +#define min(A,B) ((A) < (B) ? (A) : (B)) static struct assegment * aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset, @@ -407,41 +792,33 @@ aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset, /* If this is first AS set member, create new as-set segment. */ if (asset == NULL) { - if (! aspath->data) - { - aspath->data = XMALLOC (MTYPE_AS_SEG, ASSEGMENT_SIZE (1)); - asset = (struct assegment *) aspath->data; - aspath->length = ASSEGMENT_SIZE (1); - } + asset = assegment_new (AS_SET, 1); + if (! aspath->segments) + aspath->segments = asset; else - { - aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, - aspath->length + ASSEGMENT_SIZE (1)); - asset = (struct assegment *) (aspath->data + aspath->length); - aspath->length += ASSEGMENT_SIZE (1); - } + { + struct assegment *seg = aspath->segments; + while (seg->next) + seg = seg->next; + seg->next = asset; + } asset->type = AS_SET; asset->length = 1; - asset->asval[0] = as; + asset->as[0] = as; } else { - size_t offset; - /* Check this AS value already exists or not. */ for (i = 0; i < asset->length; i++) - if (asset->asval[i] == as) + if (asset->as[i] == as) return asset; - - offset = (caddr_t) asset - (caddr_t) aspath->data; - aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, - aspath->length + AS_VALUE_SIZE); - - asset = (struct assegment *) (aspath->data + offset); - aspath->length += AS_VALUE_SIZE; - asset->asval[asset->length] = as; + asset->length++; + asset->as = XREALLOC (MTYPE_AS_SEG_DATA, asset->as, + asset->length * AS_VALUE_SIZE); + asset->as[asset->length - 1] = as; } + return asset; } @@ -453,14 +830,9 @@ aspath_aggregate (struct aspath *as1, struct aspath *as2) int i; int minlen; int match; - int match1; - int match2; - caddr_t cp1; - caddr_t cp2; - caddr_t end1; - caddr_t end2; - struct assegment *seg1; - struct assegment *seg2; + int from; + struct assegment *seg1 = as1->segments; + struct assegment *seg2 = as2->segments; struct aspath *aspath; struct assegment *asset; @@ -468,16 +840,9 @@ aspath_aggregate (struct aspath *as1, struct aspath *as2) minlen = 0; aspath = NULL; asset = NULL; - cp1 = as1->data; - end1 = as1->data + as1->length; - cp2 = as2->data; - end2 = as2->data + as2->length; - - seg1 = (struct assegment *) cp1; - seg2 = (struct assegment *) cp2; /* First of all check common leading sequence. */ - while ((cp1 < end1) && (cp2 < end2)) + while (seg1 && seg2) { /* Check segment type. */ if (seg1->type != seg2->type) @@ -487,55 +852,52 @@ aspath_aggregate (struct aspath *as1, struct aspath *as2) minlen = min (seg1->length, seg2->length); for (match = 0; match < minlen; match++) - if (seg1->asval[match] != seg2->asval[match]) + if (seg1->as[match] != seg2->as[match]) break; if (match) { if (! aspath) - aspath = aspath_new(); - aspath = aspath_aggregate_segment_copy (aspath, seg1, match); + aspath = aspath_new (); + aspath->segments = assegment_new (seg1->type, 0); + aspath->segments = assegment_append_asns (aspath->segments, + seg1->as, match); } if (match != minlen || match != seg1->length || seg1->length != seg2->length) break; - - cp1 += ((seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE); - cp2 += ((seg2->length * AS_VALUE_SIZE) + AS_HEADER_SIZE); - - seg1 = (struct assegment *) cp1; - seg2 = (struct assegment *) cp2; + + seg1 = seg1->next; + seg2 = seg2->next; } if (! aspath) aspath = aspath_new(); /* Make as-set using rest of all information. */ - match1 = match; - while (cp1 < end1) + from = match; + while (seg1) { - seg1 = (struct assegment *) cp1; - - for (i = match1; i < seg1->length; i++) - asset = aspath_aggregate_as_set_add (aspath, asset, seg1->asval[i]); - - match1 = 0; - cp1 += ((seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE); + for (i = from; i < seg1->length; i++) + asset = aspath_aggregate_as_set_add (aspath, asset, seg1->as[i]); + + from = 0; + seg1 = seg1->next; } - match2 = match; - while (cp2 < end2) + from = match; + while (seg2) { - seg2 = (struct assegment *) cp2; + for (i = from; i < seg2->length; i++) + asset = aspath_aggregate_as_set_add (aspath, asset, seg2->as[i]); - for (i = match2; i < seg2->length; i++) - asset = aspath_aggregate_as_set_add (aspath, asset, seg2->asval[i]); - - match2 = 0; - cp2 += ((seg2->length * AS_VALUE_SIZE) + AS_HEADER_SIZE); + from = 0; + seg2 = seg2->next; } - + + assegment_normalise (aspath->segments); + aspath_str_update (aspath); return aspath; } @@ -545,18 +907,12 @@ aspath_aggregate (struct aspath *as1, struct aspath *as2) int aspath_firstas_check (struct aspath *aspath, as_t asno) { - caddr_t pnt; - struct assegment *assegment; - - if (aspath == NULL) + if ( (aspath == NULL) || (aspath->segments == NULL) ) return 0; - - pnt = aspath->data; - assegment = (struct assegment *) pnt; - - if (assegment - && assegment->type == AS_SEQUENCE - && assegment->asval[0] == htons (asno)) + + if (aspath->segments + && (aspath->segments->type == AS_SEQUENCE) + && (aspath->segments->as[0] == asno )) return 1; return 0; @@ -566,27 +922,23 @@ aspath_firstas_check (struct aspath *aspath, as_t asno) int aspath_loop_check (struct aspath *aspath, as_t asno) { - caddr_t pnt; - caddr_t end; - struct assegment *assegment; + struct assegment *seg; int count = 0; - if (aspath == NULL) + if ( (aspath == NULL) || (aspath->segments) ) return 0; - - pnt = aspath->data; - end = aspath->data + aspath->length; - - while (pnt < end) + + seg = aspath->segments; + + while (seg) { int i; - assegment = (struct assegment *) pnt; - for (i = 0; i < assegment->length; i++) - if (assegment->asval[i] == htons (asno)) + for (i = 0; i < seg->length; i++) + if (seg->as[i] == asno) count++; - - pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE; + + seg = seg->next; } return count; } @@ -595,31 +947,24 @@ aspath_loop_check (struct aspath *aspath, as_t asno) int aspath_private_as_check (struct aspath *aspath) { - caddr_t pnt; - caddr_t end; - struct assegment *assegment; - - if (aspath == NULL) - return 0; - - if (aspath->length == 0) + struct assegment *seg; + + if ( !(aspath && aspath->segments) ) return 0; + + seg = aspath->segments; - pnt = aspath->data; - end = aspath->data + aspath->length; - - while (pnt < end) + while (seg) { int i; - assegment = (struct assegment *) pnt; - for (i = 0; i < assegment->length; i++) + for (i = 0; i < seg->length; i++) { - if (ntohs (assegment->asval[i]) < BGP_PRIVATE_AS_MIN - || ntohs (assegment->asval[i]) > BGP_PRIVATE_AS_MAX) + if ( (seg->as[i] < BGP_PRIVATE_AS_MIN) + || (seg->as[i] > BGP_PRIVATE_AS_MAX) ) return 0; } - pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE; + seg = seg->next; } return 1; } @@ -628,19 +973,20 @@ aspath_private_as_check (struct aspath *aspath) static struct aspath * aspath_merge (struct aspath *as1, struct aspath *as2) { - caddr_t data; + struct assegment *last, *new; if (! as1 || ! as2) return NULL; - data = XMALLOC (MTYPE_AS_SEG, as1->length + as2->length); - memcpy (data, as1->data, as1->length); - memcpy (data + as1->length, as2->data, as2->length); - - XFREE (MTYPE_AS_SEG, as2->data); - as2->data = data; - as2->length += as1->length; - as2->count += as1->count; + last = new = assegment_dup_all (as1->segments); + + /* find the last valid segment */ + while (last && last->next) + last = last->next; + + last->next = as2->segments; + as2->segments = new; + aspath_str_update (as2); return as2; } @@ -648,38 +994,30 @@ aspath_merge (struct aspath *as1, struct aspath *as2) struct aspath * aspath_prepend (struct aspath *as1, struct aspath *as2) { - caddr_t pnt; - caddr_t end; - struct assegment *seg1 = NULL; - struct assegment *seg2 = NULL; + struct assegment *seg1; + struct assegment *seg2; if (! as1 || ! as2) return NULL; - - seg2 = (struct assegment *) as2->data; - - /* In case of as2 is empty AS. */ + + seg1 = as1->segments; + seg2 = as2->segments; + + /* If as2 is empty, only need to dupe as1's chain onto as2 */ if (seg2 == NULL) { - as2->length = as1->length; - as2->data = XMALLOC (MTYPE_AS_SEG, as1->length); - as2->count = as1->count; - memcpy (as2->data, as1->data, as1->length); + as2->segments = assegment_dup_all (as1->segments); + aspath_str_update (as2); return as2; } - - /* assegment points last segment of as1. */ - pnt = as1->data; - end = as1->data + as1->length; - while (pnt < end) - { - seg1 = (struct assegment *) pnt; - pnt += (seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE; - } - - /* In case of as1 is empty AS. */ + + /* If as1 is empty AS, no prepending to do. */ if (seg1 == NULL) return as2; + + /* find the tail as1's segment chain. */ + while (seg1 && seg1->next) + seg1 = seg1->next; /* Compare last segment type of as1 and first segment type of as2. */ if (seg1->type != seg2->type) @@ -687,22 +1025,37 @@ aspath_prepend (struct aspath *as1, struct aspath *as2) if (seg1->type == AS_SEQUENCE) { - caddr_t newdata; - struct assegment *seg = NULL; + /* We have two chains of segments, as1->segments and seg2, + * and we have to attach them together, merging the attaching + * segments together into one. + * + * 1. dupe as1->segments onto head of as2 + * 2. merge seg2's asns onto last segment of this new chain + * 3. attach chain after seg2 + */ - newdata = XMALLOC (MTYPE_AS_SEG, - as1->length + as2->length - AS_HEADER_SIZE); - memcpy (newdata, as1->data, as1->length); - seg = (struct assegment *) (newdata + ((caddr_t)seg1 - as1->data)); - seg->length += seg2->length; - memcpy (newdata + as1->length, as2->data + AS_HEADER_SIZE, - as2->length - AS_HEADER_SIZE); - - XFREE (MTYPE_AS_SEG, as2->data); - as2->data = newdata; - as2->length += (as1->length - AS_HEADER_SIZE); - as2->count += as1->count; - + /* dupe as1 onto as2's head */ + seg1 = as2->segments = assegment_dup_all (as1->segments); + + /* refind the tail of as2, reusing seg1 */ + while (seg1 && seg1->next) + seg1 = seg1->next; + + /* merge the old head, seg2, into tail, seg1 */ + seg1 = assegment_append_asns (seg1, seg2->as, seg2->length); + + /* bypass the merged seg2, and attach any chain after it to + * chain descending from as2's head + */ + seg1->next = seg2->next; + + /* seg2 is now referenceless and useless*/ + assegment_free (seg2); + + /* we've now prepended as1's segment chain to as2, merging + * the inbetween AS_SEQUENCE of seg2 in the process + */ + aspath_str_update (as2); return as2; } else @@ -710,7 +1063,8 @@ aspath_prepend (struct aspath *as1, struct aspath *as2) /* AS_SET merge code is needed at here. */ return aspath_merge (as1, as2); } - + /* XXX: Ermmm, what if as1 has multiple segments?? */ + /* Not reached */ } @@ -718,67 +1072,34 @@ aspath_prepend (struct aspath *as1, struct aspath *as2) static struct aspath * aspath_add_one_as (struct aspath *aspath, as_t asno, u_char type) { - struct assegment *assegment; - - assegment = (struct assegment *) aspath->data; + struct assegment *assegment = aspath->segments; /* In case of empty aspath. */ if (assegment == NULL || assegment->length == 0) { - aspath->length = AS_HEADER_SIZE + AS_VALUE_SIZE; - + aspath->segments = assegment_new (type, 1); + aspath->segments->as[0] = asno; + if (assegment) - aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, aspath->length); - else - aspath->data = XMALLOC (MTYPE_AS_SEG, aspath->length); - - assegment = (struct assegment *) aspath->data; - assegment->type = type; - assegment->length = 1; - assegment->asval[0] = htons (asno); + assegment_free (assegment); return aspath; } if (assegment->type == type) + aspath->segments = assegment_prepend_asns (aspath->segments, asno, 1); + else { - caddr_t newdata; - struct assegment *newsegment; - - newdata = XMALLOC (MTYPE_AS_SEG, aspath->length + AS_VALUE_SIZE); - newsegment = (struct assegment *) newdata; - - newsegment->type = type; - newsegment->length = assegment->length + 1; - newsegment->asval[0] = htons (asno); - - memcpy (newdata + AS_HEADER_SIZE + AS_VALUE_SIZE, - aspath->data + AS_HEADER_SIZE, - aspath->length - AS_HEADER_SIZE); - - XFREE (MTYPE_AS_SEG, aspath->data); - - aspath->data = newdata; - aspath->length += AS_VALUE_SIZE; - } else { - caddr_t newdata; + /* create new segment + * push it onto head of aspath's segment chain + */ struct assegment *newsegment; - - newdata = XMALLOC (MTYPE_AS_SEG, aspath->length + AS_VALUE_SIZE + AS_HEADER_SIZE); - newsegment = (struct assegment *) newdata; - - newsegment->type = type; - newsegment->length = 1; - newsegment->asval[0] = htons (asno); - - memcpy (newdata + AS_HEADER_SIZE + AS_VALUE_SIZE, - aspath->data, - aspath->length); - - XFREE (MTYPE_AS_SEG, aspath->data); - - aspath->data = newdata; - aspath->length += AS_HEADER_SIZE + AS_VALUE_SIZE; + + newsegment = assegment_new (type, 1); + newsegment->as[0] = asno; + + newsegment->next = assegment; + aspath->segments = newsegment; } return aspath; @@ -796,31 +1117,30 @@ aspath_add_seq (struct aspath *aspath, as_t asno) int aspath_cmp_left (struct aspath *aspath1, struct aspath *aspath2) { - struct assegment *seg1; - struct assegment *seg2; - as_t as1; - as_t as2; + struct assegment *seg1 = NULL; + struct assegment *seg2 = NULL; - seg1 = (struct assegment *) aspath1->data; - seg2 = (struct assegment *) aspath2->data; + if (!(aspath1 && aspath2)) + return 0; - while (seg1 && seg1->length - && (seg1->type == AS_CONFED_SEQUENCE || seg1->type == AS_CONFED_SET)) - seg1 = (struct assegment *) ((caddr_t) seg1 + ASSEGMENT_LEN (seg1)); - while (seg2 && seg2->length - && (seg2->type == AS_CONFED_SEQUENCE || seg2->type == AS_CONFED_SET)) - seg2 = (struct assegment *) ((caddr_t) seg2 + ASSEGMENT_LEN (seg2)); + seg1 = aspath1->segments; + seg2 = aspath2->segments; - /* Check as1's */ - if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_SEQUENCE) - return 0; - as1 = seg1->asval[0]; + /* find first non-confed segments for each */ + while (seg1 && ((seg1->type == AS_CONFED_SEQUENCE) + || (seg1->type == AS_CONFED_SET))) + seg1 = seg1->next; - if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_SEQUENCE) - return 0; - as2 = seg2->asval[0]; + while (seg2 && ((seg2->type == AS_CONFED_SEQUENCE) + || (seg2->type == AS_CONFED_SET))) + seg2 = seg2->next; - if (as1 == as2) + /* Check as1's */ + if (!(seg1 && seg2 + && (seg1->type == AS_SEQUENCE) && (seg2->type == AS_SEQUENCE))) + return 0; + + if (seg1->as[0] == seg2->as[0]) return 1; return 0; @@ -832,70 +1152,49 @@ aspath_cmp_left (struct aspath *aspath1, struct aspath *aspath2) int aspath_cmp_left_confed (struct aspath *aspath1, struct aspath *aspath2) { - struct assegment *seg1; - struct assegment *seg2; - - as_t as1; - as_t as2; - - if (aspath1->count || aspath2->count) - return 0; - - seg1 = (struct assegment *) aspath1->data; - seg2 = (struct assegment *) aspath2->data; - - /* Check as1's */ - if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_CONFED_SEQUENCE) + if (! (aspath1 && aspath2) ) return 0; - as1 = seg1->asval[0]; - - /* Check as2's */ - if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_CONFED_SEQUENCE) + + if ( (aspath1->segments->type != AS_CONFED_SEQUENCE) + || (aspath2->segments->type != AS_CONFED_SEQUENCE) ) return 0; - as2 = seg2->asval[0]; - - if (as1 == as2) + + if (aspath1->segments->as[0] == aspath2->segments->as[0]) return 1; return 0; } -/* Delete first sequential AS_CONFED_SEQUENCE from aspath. */ +/* Delete all leading AS_CONFED_SEQUENCE/SET segments from aspath. + * See RFC3065, 6.1 c1 */ struct aspath * aspath_delete_confed_seq (struct aspath *aspath) { - int seglen; - struct assegment *assegment; + struct assegment *seg; - if (! aspath) + if (!(aspath && aspath->segments)) return aspath; - assegment = (struct assegment *) aspath->data; + seg = aspath->segments; + + /* "if the first path segment of the AS_PATH is + * of type AS_CONFED_SEQUENCE," + */ + if (aspath->segments->type != AS_CONFED_SEQUENCE) + return aspath; - while (assegment) + /* "... that segment and any immediately following segments + * of the type AS_CONFED_SET or AS_CONFED_SEQUENCE are removed + * from the AS_PATH attribute," + */ + while (seg && + (seg->type == AS_CONFED_SEQUENCE || seg->type == AS_CONFED_SET)) { - if (assegment->type != AS_CONFED_SEQUENCE) - return aspath; - - seglen = ASSEGMENT_LEN (assegment); - - if (seglen == aspath->length) - { - XFREE (MTYPE_AS_SEG, aspath->data); - aspath->data = NULL; - aspath->length = 0; - } - else - { - memcpy (aspath->data, aspath->data + seglen, - aspath->length - seglen); - aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, - aspath->length - seglen); - aspath->length -= seglen; - } - - assegment = (struct assegment *) aspath->data; + aspath->segments = seg->next; + assegment_free (seg); + seg = aspath->segments; } + aspath_str_update (aspath); return aspath; } @@ -911,53 +1210,32 @@ aspath_add_confed_seq (struct aspath *aspath, as_t asno) static void aspath_as_add (struct aspath *as, as_t asno) { - caddr_t pnt; - caddr_t end; - struct assegment *assegment; - - /* Increase as->data for new as value. */ - as->data = XREALLOC (MTYPE_AS_SEG, as->data, as->length + 2); - as->length += 2; - - pnt = as->data; - end = as->data + as->length; - assegment = (struct assegment *) pnt; + struct assegment *seg = as->segments; /* Last segment search procedure. */ - while (pnt + 2 < end) - { - assegment = (struct assegment *) pnt; - - /* We add 2 for segment_type and segment_length and segment - value assegment->length * 2. */ - pnt += (AS_HEADER_SIZE + (assegment->length * AS_VALUE_SIZE)); - } - - assegment->asval[assegment->length] = htons (asno); - assegment->length++; + while (seg && seg->next) + seg = seg->next; + + if (!seg) + return; + + assegment_append_asns (seg, &asno, 1); } /* Add new as segment to the as path. */ static void aspath_segment_add (struct aspath *as, int type) { - struct assegment *assegment; + struct assegment *seg = as->segments; + struct assegment *new = assegment_new (type, 0); - if (as->data == NULL) - { - as->data = XMALLOC (MTYPE_AS_SEG, 2); - assegment = (struct assegment *) as->data; - as->length = 2; - } + while (seg && seg->next) + seg = seg->next; + + if (seg == NULL) + as->segments = new; else - { - as->data = XREALLOC (MTYPE_AS_SEG, as->data, as->length + 2); - assegment = (struct assegment *) (as->data + as->length); - as->length += 2; - } - - assegment->type = type; - assegment->length = 0; + seg->next = new; } struct aspath * @@ -977,7 +1255,7 @@ aspath_empty_get (void) } unsigned long -aspath_count () +aspath_count (void) { return ashash->count; } @@ -997,8 +1275,10 @@ enum as_token as_token_asval, as_token_set_start, as_token_set_end, - as_token_confed_start, - as_token_confed_end, + as_token_confed_seq_start, + as_token_confed_seq_end, + as_token_confed_set_start, + as_token_confed_set_end, as_token_unknown }; @@ -1008,8 +1288,8 @@ aspath_gettoken (const char *buf, enum as_token *token, u_short *asno) { const char *p = buf; - /* Skip space. */ - while (isspace ((int) *p)) + /* Skip seperators (space for sequences, ',' for sets). */ + while (isspace ((int) *p) || *p == ',') p++; /* Check the end of the string and type specify characters @@ -1030,12 +1310,22 @@ aspath_gettoken (const char *buf, enum as_token *token, u_short *asno) return p; break; case '(': - *token = as_token_confed_start; + *token = as_token_confed_seq_start; p++; return p; break; case ')': - *token = as_token_confed_end; + *token = as_token_confed_seq_end; + p++; + return p; + break; + case '[': + *token = as_token_confed_set_start; + p++; + return p; + break; + case ']': + *token = as_token_confed_set_end; p++; return p; break; @@ -1100,17 +1390,27 @@ aspath_str2aspath (const char *str) as_type = AS_SEQUENCE; needtype = 1; break; - case as_token_confed_start: + case as_token_confed_seq_start: as_type = AS_CONFED_SEQUENCE; aspath_segment_add (aspath, as_type); needtype = 0; break; - case as_token_confed_end: + case as_token_confed_seq_end: + as_type = AS_SEQUENCE; + needtype = 1; + break; + case as_token_confed_set_start: + as_type = AS_CONFED_SET; + aspath_segment_add (aspath, as_type); + needtype = 0; + break; + case as_token_confed_set_end: as_type = AS_SEQUENCE; needtype = 1; break; case as_token_unknown: default: + aspath_free (aspath); return NULL; break; } @@ -1126,16 +1426,23 @@ unsigned int aspath_key_make (struct aspath *aspath) { unsigned int key = 0; - int length; - unsigned short *pnt; - - length = aspath->length / 2; - pnt = (unsigned short *) aspath->data; + unsigned int i; + struct assegment *seg = aspath->segments; + struct assegment *prev = NULL; - while (length) + while (seg) { - key += *pnt++; - length--; + /* segment types should be part of the hash + * otherwise seq(1) and set(1) will hash to same value + */ + if (!(prev && seg->type == AS_SEQUENCE && seg->type == prev->type)) + key += seg->type; + + for (i = 0; i < seg->length; i++) + key += seg->as[i]; + + prev = seg; + seg = seg->next; } return key; @@ -1143,13 +1450,27 @@ aspath_key_make (struct aspath *aspath) /* If two aspath have same value then return 1 else return 0 */ static int -aspath_cmp (struct aspath *as1, struct aspath *as2) +aspath_cmp (void *arg1, void *arg2) { - if (as1->length == as2->length - && !memcmp (as1->data, as2->data, as1->length)) - return 1; - else - return 0; + struct assegment *seg1 = ((struct aspath *)arg1)->segments; + struct assegment *seg2 = ((struct aspath *)arg2)->segments; + + while (seg1 || seg2) + { + int i; + if ((!seg1 && seg2) || (seg1 && !seg2)) + return 0; + if (seg1->type != seg2->type) + return 0; + if (seg1->length != seg2->length) + return 0; + for (i = 0; i < seg1->length; i++) + if (seg1->as[i] != seg2->as[i]) + return 0; + seg1 = seg1->next; + seg2 = seg2->next; + } + return 1; } /* AS path hash initialize. */ @@ -1163,7 +1484,7 @@ aspath_init (void) const char * aspath_print (struct aspath *as) { - return as->str; + return (as ? as->str : NULL); } /* Printing functions */ diff --git a/bgpd/bgp_aspath.h b/bgpd/bgp_aspath.h index c89b5e5a..adf58517 100644 --- a/bgpd/bgp_aspath.h +++ b/bgpd/bgp_aspath.h @@ -33,24 +33,24 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA #define BGP_AS_MAX 65535U +/* AS_PATH segment data in abstracted form, no limit is placed on length */ +struct assegment +{ + struct assegment *next; + as_t *as; + u_short length; + u_char type; +}; + /* AS path may be include some AsSegments. */ struct aspath { /* Reference count to this aspath. */ unsigned long refcnt; - /* Rawdata length. */ - int length; - - /* AS count. */ - int count; - - /* Confederation set/segment AS count. */ - int confed_count; + /* segment data */ + struct assegment *segments; - /* Rawdata. */ - caddr_t data; - /* String expression of AS path. This string is used by vty output and AS path regular expression match. */ char *str; @@ -60,7 +60,7 @@ struct aspath /* Prototypes. */ extern void aspath_init (void); -extern struct aspath *aspath_parse (caddr_t, int); +extern struct aspath *aspath_parse (struct stream *, size_t); extern struct aspath *aspath_dup (struct aspath *); extern struct aspath *aspath_aggregate (struct aspath *, struct aspath *); extern struct aspath *aspath_prepend (struct aspath *, struct aspath *); @@ -83,5 +83,12 @@ extern int aspath_loop_check (struct aspath *, as_t); extern int aspath_private_as_check (struct aspath *); extern int aspath_firstas_check (struct aspath *, as_t); extern unsigned long aspath_count (void); +extern unsigned int aspath_count_hops (struct aspath *); +extern unsigned int aspath_count_confeds (struct aspath *); +extern unsigned int aspath_size (struct aspath *); +extern void aspath_put (struct stream *, struct aspath *); + +/* For SNMP BGP4PATHATTRASPATHSEGMENT, might be useful for debug */ +extern u_char *aspath_snmp_pathseg (struct aspath *, size_t *); #endif /* _QUAGGA_BGP_ASPATH_H */ diff --git a/bgpd/bgp_attr.c b/bgpd/bgp_attr.c index d566f469..4b94b11e 100644 --- a/bgpd/bgp_attr.c +++ b/bgpd/bgp_attr.c @@ -663,7 +663,7 @@ bgp_attr_aspath (struct peer *peer, bgp_size_t length, } /* In case of IBGP, length will be zero. */ - attr->aspath = aspath_parse (stream_pnt (peer->ibuf), length); + attr->aspath = aspath_parse (peer->ibuf, length); if (! attr->aspath) { zlog (peer->log, LOG_ERR, "Malformed AS path length is %d", length); @@ -701,7 +701,7 @@ bgp_attr_aspath (struct peer *peer, bgp_size_t length, } /* Forward pointer. */ - stream_forward_getp (peer->ibuf, length); +/* stream_forward_getp (peer->ibuf, length);*/ /* Set aspath attribute flag. */ attr->flag |= ATTR_FLAG_BIT (BGP_ATTR_AS_PATH); @@ -1341,7 +1341,8 @@ bgp_packet_attribute (struct bgp *bgp, struct peer *peer, afi_t afi, safi_t safi, struct peer *from, struct prefix_rd *prd, char *tag) { - unsigned long cp; + size_t cp; + unsigned int aspath_data_size; struct aspath *aspath; if (! bgp) @@ -1361,7 +1362,7 @@ bgp_packet_attribute (struct bgp *bgp, struct peer *peer, /* If remote-peer is EBGP */ if (peer_sort (peer) == BGP_PEER_EBGP && (! CHECK_FLAG (peer->af_flags[afi][safi], PEER_FLAG_AS_PATH_UNCHANGED) - || attr->aspath->length == 0) + || attr->aspath->segments == NULL) && (! CHECK_FLAG (peer->af_flags[afi][safi], PEER_FLAG_RSERVER_CLIENT))) { aspath = aspath_dup (attr->aspath); @@ -1390,19 +1391,20 @@ bgp_packet_attribute (struct bgp *bgp, struct peer *peer, aspath = attr->aspath; /* AS path attribute extended length bit check. */ - if (aspath->length > 255) + aspath_data_size = aspath_size (aspath); + if (aspath_data_size > 255) { stream_putc (s, BGP_ATTR_FLAG_TRANS|BGP_ATTR_FLAG_EXTLEN); stream_putc (s, BGP_ATTR_AS_PATH); - stream_putw (s, aspath->length); + stream_putw (s, aspath_data_size); } else { stream_putc (s, BGP_ATTR_FLAG_TRANS); - stream_putc(s, BGP_ATTR_AS_PATH); - stream_putc (s, aspath->length); + stream_putc (s, BGP_ATTR_AS_PATH); + stream_putc (s, aspath_data_size); } - stream_put (s, aspath->data, aspath->length); + aspath_put (s, aspath); if (aspath != attr->aspath) aspath_free (aspath); @@ -1735,7 +1737,7 @@ bgp_packet_withdraw (struct peer *peer, struct stream *s, struct prefix *p, /* Initialization of attribute. */ void -bgp_attr_init () +bgp_attr_init (void) { void attrhash_init (); @@ -1754,6 +1756,7 @@ bgp_dump_routes_attr (struct stream *s, struct attr *attr, { unsigned long cp; unsigned long len; + unsigned int aspathlen; struct aspath *aspath; /* Remember current pointer. */ @@ -1770,19 +1773,19 @@ bgp_dump_routes_attr (struct stream *s, struct attr *attr, aspath = attr->aspath; - if (aspath->length > 255) + if ( (aspathlen = aspath_size (aspath)) > 255 ) { stream_putc (s, BGP_ATTR_FLAG_TRANS|BGP_ATTR_FLAG_EXTLEN); stream_putc (s, BGP_ATTR_AS_PATH); - stream_putw (s, aspath->length); + stream_putw (s, aspathlen); } else { stream_putc (s, BGP_ATTR_FLAG_TRANS); stream_putc (s, BGP_ATTR_AS_PATH); - stream_putc (s, aspath->length); + stream_putc (s, aspathlen); } - stream_put (s, aspath->data, aspath->length); + aspath_put (s, aspath); /* Nexthop attribute. */ /* If it's an IPv6 prefix, don't dump the IPv4 nexthop to save space */ diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c index 14fa86a5..0658cabe 100644 --- a/bgpd/bgp_route.c +++ b/bgpd/bgp_route.c @@ -268,24 +268,28 @@ bgp_info_cmp (struct bgp *bgp, struct bgp_info *new, struct bgp_info *exist) /* 4. AS path length check. */ if (! bgp_flag_check (bgp, BGP_FLAG_ASPATH_IGNORE)) { + int exist_hops = aspath_count_hops (exist->attr->aspath); + int exist_confeds = aspath_count_confeds (exist->attr->aspath); + if (bgp_flag_check (bgp, BGP_FLAG_ASPATH_CONFED)) { - if ((new->attr->aspath->count + - new->attr->aspath->confed_count) - < (exist->attr->aspath->count + - exist->attr->aspath->confed_count)) + int aspath_hops; + + aspath_hops = aspath_count_hops (new->attr->aspath); + aspath_hops += aspath_count_confeds (new->attr->aspath); + + if ( aspath_hops < (exist_hops + exist_confeds)) return 1; - if ((new->attr->aspath->count + - new->attr->aspath->confed_count) - > (exist->attr->aspath->count + - exist->attr->aspath->confed_count)) + if ( aspath_hops > (exist_hops + exist_confeds)) return 0; } else { - if (new->attr->aspath->count < exist->attr->aspath->count) + int newhops = aspath_count_hops (new->attr->aspath); + + if (newhops < exist_hops) return 1; - if (new->attr->aspath->count > exist->attr->aspath->count) + if (newhops > exist_hops) return 0; } } @@ -297,12 +301,12 @@ bgp_info_cmp (struct bgp *bgp, struct bgp_info *new, struct bgp_info *exist) return 0; /* 6. MED check. */ - internal_as_route = (new->attr->aspath->length == 0 - && exist->attr->aspath->length == 0); - confed_as_route = (new->attr->aspath->length > 0 - && exist->attr->aspath->length > 0 - && new->attr->aspath->count == 0 - && exist->attr->aspath->count == 0); + internal_as_route = (aspath_count_hops (new->attr->aspath) == 0 + && aspath_count_hops (exist->attr->aspath) == 0); + confed_as_route = (aspath_count_confeds (new->attr->aspath) > 0 + && aspath_count_confeds (exist->attr->aspath) > 0 + && aspath_count_hops (new->attr->aspath) == 0 + && aspath_count_hops (exist->attr->aspath) == 0); if (bgp_flag_check (bgp, BGP_FLAG_ALWAYS_COMPARE_MED) || (bgp_flag_check (bgp, BGP_FLAG_MED_CONFED) @@ -1573,7 +1577,6 @@ static void bgp_rib_withdraw (struct bgp_node *rn, struct bgp_info *ri, struct peer *peer, afi_t afi, safi_t safi) { - int valid; int status = BGP_DAMP_NONE; if (!CHECK_FLAG (ri->flags, BGP_INFO_HISTORY) @@ -5371,7 +5374,7 @@ route_vty_out_detail (struct vty *vty, struct bgp *bgp, struct prefix *p, if (attr->aspath) { vty_out (vty, " "); - if (attr->aspath->length == 0) + if (aspath_count_hops (attr->aspath) == 0) vty_out (vty, "Local"); else aspath_print_vty (vty, attr->aspath); diff --git a/bgpd/bgp_snmp.c b/bgpd/bgp_snmp.c index 344358e3..430521f1 100644 --- a/bgpd/bgp_snmp.c +++ b/bgpd/bgp_snmp.c @@ -782,8 +782,7 @@ bgp4PathAttrTable (struct variable *v, oid name[], size_t *length, return SNMP_INTEGER (binfo->attr->origin); break; case BGP4PATHATTRASPATHSEGMENT: /* 5 */ - *var_len = binfo->attr->aspath->length; - return (u_char *) binfo->attr->aspath->data; + return aspath_snmp_pathseg (binfo->attr->aspath, var_len); break; case BGP4PATHATTRNEXTHOP: /* 6 */ return SNMP_IPADDRESS (binfo->attr->nexthop); |