From 718e3744195351130f4ce7dbe0613f4b3e23df93 Mon Sep 17 00:00:00 2001 From: paul Date: Fri, 13 Dec 2002 20:15:29 +0000 Subject: Initial revision --- bgpd/bgp_aspath.c | 1186 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1186 insertions(+) create mode 100644 bgpd/bgp_aspath.c (limited to 'bgpd/bgp_aspath.c') diff --git a/bgpd/bgp_aspath.c b/bgpd/bgp_aspath.c new file mode 100644 index 00000000..fc5efb19 --- /dev/null +++ b/bgpd/bgp_aspath.c @@ -0,0 +1,1186 @@ +/* AS path management routines. + Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro + +This file is part of GNU Zebra. + +GNU Zebra is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 2, or (at your option) any +later version. + +GNU Zebra is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Zebra; see the file COPYING. If not, write to the Free +Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#include + +#include "hash.h" +#include "memory.h" +#include "vector.h" +#include "vty.h" +#include "str.h" +#include "log.h" + +#include "bgpd/bgpd.h" +#include "bgpd/bgp_aspath.h" + +/* Attr. Flags and Attr. Type Code. */ +#define AS_HEADER_SIZE 2 + +/* 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) + +/* To fetch and store as segment value. */ +struct assegment +{ + 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 struct aspath * +aspath_new () +{ + struct aspath *aspath; + + aspath = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); + memset (aspath, 0, sizeof (struct aspath)); + return aspath; +} + +/* Free AS path structure. */ +void +aspath_free (struct aspath *aspath) +{ + if (!aspath) + return; + if (aspath->data) + XFREE (MTYPE_AS_SEG, aspath->data); + if (aspath->str) + XFREE (MTYPE_AS_STR, aspath->str); + XFREE (MTYPE_AS_PATH, aspath); +} + +/* Unintern aspath from AS path bucket. */ +void +aspath_unintern (struct aspath *aspath) +{ + struct aspath *ret; + + if (aspath->refcnt) + aspath->refcnt--; + + if (aspath->refcnt == 0) + { + /* This aspath must exist in aspath hash table. */ + ret = hash_release (ashash, aspath); + assert (ret != NULL); + aspath_free (aspath); + } +} + +/* Return the start or end delimiters for a particular Segment type */ +#define AS_SEG_START 0 +#define AS_SEG_END 1 +static char +aspath_delimiter_char (u_char type, u_char which) +{ + int i; + struct + { + int type; + char start; + char end; + } aspath_delim_char [] = + { + { AS_SET, '{', '}' }, + { AS_SEQUENCE, ' ', ' ' }, + { AS_CONFED_SET, '[', ']' }, + { AS_CONFED_SEQUENCE, '(', ')' }, + { 0 } + }; + + for (i = 0; aspath_delim_char[i].type != 0; i++) + { + if (aspath_delim_char[i].type == type) + { + if (which == AS_SEG_START) + return aspath_delim_char[i].start; + else if (which == AS_SEG_END) + return aspath_delim_char[i].end; + } + } + return ' '; +} + +/* Convert aspath structure to string expression. */ +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; + u_char *str_buf; + int count = 0; + + /* Empty aspath. */ + if (as->length == 0) + { + str_buf = XMALLOC (MTYPE_AS_STR, 1); + str_buf[0] = '\0'; + as->count = count; + return str_buf; + } + + /* Set default value. */ + space = 0; + type = AS_SEQUENCE; + + /* Set initial pointer. */ + pnt = as->data; + end = pnt + as->length; + + str_buf = XMALLOC (MTYPE_AS_STR, str_size); + str_pnt = 0; + + assegment = (struct assegment *) pnt; + + while (pnt < end) + { + 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); + + /* 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 count - ignoring CONFED SETS/SEQUENCES */ + if (assegment->type != AS_CONFED_SEQUENCE + && assegment->type != AS_CONFED_SET) + { + if (assegment->type == AS_SEQUENCE) + count += assegment->length; + else if (assegment->type == AS_SET) + count++; + } + + 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; + } + + 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; + + return str_buf; +} + +/* Intern allocated AS path. */ +struct aspath * +aspath_intern (struct aspath *aspath) +{ + struct aspath *find; + + /* Assert this AS path structure is not interned. */ + assert (aspath->refcnt == 0); + + /* Check AS path hash. */ + find = hash_get (ashash, aspath, hash_alloc_intern); + + if (find != aspath) + aspath_free (aspath); + + find->refcnt++; + + if (! find->str) + find->str = aspath_make_str_count (find); + + return find; +} + +/* Duplicate aspath structure. Created same aspath structure but + reference count and AS path string is cleared. */ +struct aspath * +aspath_dup (struct aspath *aspath) +{ + struct aspath *new; + + new = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); + memset (new, 0, 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); + } + else + new->data = NULL; + + /* new->str = aspath_make_str_count (aspath); */ + + return new; +} + +void * +aspath_hash_alloc (struct aspath *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; + + /* Make AS path string. */ + aspath->str = aspath_make_str_count (aspath); + + /* Malformed AS path value. */ + if (! aspath->str) + { + aspath_free (aspath); + return NULL; + } + + return aspath; +} + +/* 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) +{ + struct aspath as; + struct aspath *find; + + /* If length is odd it's malformed AS path. */ + if (length % 2) + return NULL; + + /* Looking up aspath hash entry. */ + as.data = pnt; + as.length = length; + + /* If already same aspath exist then return it. */ + find = hash_get (ashash, &as, aspath_hash_alloc); + if (! find) + return NULL; + find->refcnt++; + + return find; +} + +#define min(A,B) ((A) < (B) ? (A) : (B)) + +#define ASSEGMENT_SIZE(N) (AS_HEADER_SIZE + ((N) * AS_VALUE_SIZE)) + +struct aspath * +aspath_aggregate_segment_copy (struct aspath *aspath, struct assegment *seg, + int i) +{ + struct assegment *newseg; + + if (! aspath->data) + { + aspath->data = XMALLOC (MTYPE_AS_SEG, ASSEGMENT_SIZE (i)); + newseg = (struct assegment *) aspath->data; + aspath->length = ASSEGMENT_SIZE (i); + } + else + { + 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); + } + + newseg->type = seg->type; + newseg->length = i; + memcpy (newseg->asval, seg->asval, (i * AS_VALUE_SIZE)); + + return aspath; +} + +struct assegment * +aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset, + as_t as) +{ + int i; + + /* 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); + } + 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); + } + asset->type = AS_SET; + asset->length = 1; + asset->asval[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) + 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++; + } + + return asset; +} + +/* Modify as1 using as2 for aggregation. */ +struct aspath * +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; + struct aspath *aspath; + struct assegment *asset; + + match = 0; + 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)) + { + /* Check segment type. */ + if (seg1->type != seg2->type) + break; + + /* Minimum segment length. */ + minlen = min (seg1->length, seg2->length); + + for (match = 0; match < minlen; match++) + if (seg1->asval[match] != seg2->asval[match]) + break; + + if (match) + { + if (! aspath) + aspath = aspath_new(); + aspath = aspath_aggregate_segment_copy (aspath, seg1, 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; + } + + if (! aspath) + aspath = aspath_new(); + + /* Make as-set using rest of all information. */ + match1 = match; + while (cp1 < end1) + { + 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); + } + + match2 = match; + while (cp2 < end2) + { + seg2 = (struct assegment *) cp2; + + 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); + } + + return aspath; +} + +/* When a BGP router receives an UPDATE with an MP_REACH_NLRI + attribute, check the leftmost AS number in the AS_PATH attribute is + or not the peer's AS number. */ +int +aspath_firstas_check (struct aspath *aspath, as_t asno) +{ + caddr_t pnt; + struct assegment *assegment; + + if (aspath == NULL) + return 0; + + pnt = aspath->data; + assegment = (struct assegment *) pnt; + + if (assegment + && assegment->type == AS_SEQUENCE + && assegment->asval[0] == htons (asno)) + return 1; + + return 0; +} + +/* AS path loop check. If aspath contains asno then return 1. */ +int +aspath_loop_check (struct aspath *aspath, as_t asno) +{ + caddr_t pnt; + caddr_t end; + struct assegment *assegment; + int count = 0; + + if (aspath == NULL) + return 0; + + pnt = aspath->data; + end = aspath->data + aspath->length; + + while (pnt < end) + { + int i; + assegment = (struct assegment *) pnt; + + for (i = 0; i < assegment->length; i++) + if (assegment->asval[i] == htons (asno)) + count++; + + pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE; + } + return count; +} + +/* When all of AS path is private AS return 1. */ +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) + return 0; + + pnt = aspath->data; + end = aspath->data + aspath->length; + + while (pnt < end) + { + int i; + assegment = (struct assegment *) pnt; + + for (i = 0; i < assegment->length; i++) + { + if (ntohs (assegment->asval[i]) < BGP_PRIVATE_AS_MIN + || ntohs (assegment->asval[i]) > BGP_PRIVATE_AS_MAX) + return 0; + } + pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE; + } + return 1; +} + +/* Merge as1 to as2. as2 should be uninterned aspath. */ +struct aspath * +aspath_merge (struct aspath *as1, struct aspath *as2) +{ + caddr_t data; + + 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; + return as2; +} + +/* Prepend as1 to as2. as2 should be uninterned aspath. */ +struct aspath * +aspath_prepend (struct aspath *as1, struct aspath *as2) +{ + caddr_t pnt; + caddr_t end; + struct assegment *seg1 = NULL; + struct assegment *seg2 = NULL; + + if (! as1 || ! as2) + return NULL; + + seg2 = (struct assegment *) as2->data; + + /* In case of as2 is empty AS. */ + 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); + 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 (seg1 == NULL) + return as2; + + /* Compare last segment type of as1 and first segment type of as2. */ + if (seg1->type != seg2->type) + return aspath_merge (as1, as2); + + if (seg1->type == AS_SEQUENCE) + { + caddr_t newdata; + struct assegment *seg = NULL; + + 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; + + return as2; + } + else + { + /* AS_SET merge code is needed at here. */ + return aspath_merge (as1, as2); + } + + /* Not reached */ +} + +/* Add specified AS to the leftmost of aspath. */ +static struct aspath * +aspath_add_one_as (struct aspath *aspath, as_t asno, u_char type) +{ + struct assegment *assegment; + + assegment = (struct assegment *) aspath->data; + + /* In case of empty aspath. */ + if (assegment == NULL || assegment->length == 0) + { + aspath->length = AS_HEADER_SIZE + AS_VALUE_SIZE; + + 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); + + return aspath; + } + + if (assegment->type == type) + { + 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; + 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; + } + + return aspath; +} + +/* Add specified AS to the leftmost of aspath. */ +struct aspath * +aspath_add_seq (struct aspath *aspath, as_t asno) +{ + return aspath_add_one_as (aspath, asno, AS_SEQUENCE); +} + +/* Compare leftmost AS value for MED check. If as1's leftmost AS and + as2's leftmost AS is same return 1. */ +int +aspath_cmp_left (struct aspath *aspath1, struct aspath *aspath2) +{ + struct assegment *seg1; + struct assegment *seg2; + as_t as1; + as_t as2; + + seg1 = (struct assegment *) aspath1->data; + seg2 = (struct assegment *) aspath2->data; + + 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)); + + /* Check as1's */ + if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_SEQUENCE) + return 0; + as1 = seg1->asval[0]; + + if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_SEQUENCE) + return 0; + as2 = seg2->asval[0]; + + if (as1 == as2) + return 1; + + return 0; +} + +/* Compare leftmost AS value for MED check. If as1's leftmost AS and + as2's leftmost AS is same return 1. (confederation as-path + only). */ +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) + return 0; + as1 = seg1->asval[0]; + + /* Check as2's */ + if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_CONFED_SEQUENCE) + return 0; + as2 = seg2->asval[0]; + + if (as1 == as2) + return 1; + + return 0; +} + +/* Delete first sequential AS_CONFED_SEQUENCE from aspath. */ +struct aspath * +aspath_delete_confed_seq (struct aspath *aspath) +{ + int seglen; + struct assegment *assegment; + + if (! aspath) + return aspath; + + assegment = (struct assegment *) aspath->data; + + while (assegment) + { + 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; + } + return aspath; +} + +/* Add new AS number to the leftmost part of the aspath as + AS_CONFED_SEQUENCE. */ +struct aspath* +aspath_add_confed_seq (struct aspath *aspath, as_t asno) +{ + return aspath_add_one_as (aspath, asno, AS_CONFED_SEQUENCE); +} + +/* Add new as value to as path structure. */ +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; + + /* 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++; +} + +/* Add new as segment to the as path. */ +void +aspath_segment_add (struct aspath *as, int type) +{ + struct assegment *assegment; + + if (as->data == NULL) + { + as->data = XMALLOC (MTYPE_AS_SEG, 2); + assegment = (struct assegment *) as->data; + as->length = 2; + } + 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; +} + +struct aspath * +aspath_empty () +{ + return aspath_parse (NULL, 0); +} + +struct aspath * +aspath_empty_get () +{ + struct aspath *aspath; + + aspath = aspath_new (); + aspath->str = aspath_make_str_count (aspath); + return aspath; +} + +unsigned long +aspath_count () +{ + return ashash->count; +} + +/* + Theoretically, one as path can have: + + One BGP packet size should be less than 4096. + One BGP attribute size should be less than 4096 - BGP header size. + One BGP aspath size should be less than 4096 - BGP header size - + BGP mandantry attribute size. +*/ + +/* AS path string lexical token enum. */ +enum as_token +{ + as_token_asval, + as_token_set_start, + as_token_set_end, + as_token_confed_start, + as_token_confed_end, + as_token_unknown +}; + +/* Return next token and point for string parse. */ +char * +aspath_gettoken (char *buf, enum as_token *token, u_short *asno) +{ + char *p = buf; + + /* Skip space. */ + while (isspace ((int) *p)) + p++; + + /* Check the end of the string and type specify characters + (e.g. {}()). */ + switch (*p) + { + case '\0': + return NULL; + break; + case '{': + *token = as_token_set_start; + p++; + return p; + break; + case '}': + *token = as_token_set_end; + p++; + return p; + break; + case '(': + *token = as_token_confed_start; + p++; + return p; + break; + case ')': + *token = as_token_confed_end; + p++; + return p; + break; + } + + /* Check actual AS value. */ + if (isdigit ((int) *p)) + { + u_short asval; + + *token = as_token_asval; + asval = (*p - '0'); + p++; + while (isdigit ((int) *p)) + { + asval *= 10; + asval += (*p - '0'); + p++; + } + *asno = asval; + return p; + } + + /* There is no match then return unknown token. */ + *token = as_token_unknown; + return p++; +} + +struct aspath * +aspath_str2aspath (char *str) +{ + enum as_token token; + u_short as_type; + u_short asno; + struct aspath *aspath; + int needtype; + + aspath = aspath_new (); + + /* We start default type as AS_SEQUENCE. */ + as_type = AS_SEQUENCE; + needtype = 1; + + while ((str = aspath_gettoken (str, &token, &asno)) != NULL) + { + switch (token) + { + case as_token_asval: + if (needtype) + { + aspath_segment_add (aspath, as_type); + needtype = 0; + } + aspath_as_add (aspath, asno); + break; + case as_token_set_start: + as_type = AS_SET; + aspath_segment_add (aspath, as_type); + needtype = 0; + break; + case as_token_set_end: + as_type = AS_SEQUENCE; + needtype = 1; + break; + case as_token_confed_start: + as_type = AS_CONFED_SEQUENCE; + aspath_segment_add (aspath, as_type); + needtype = 0; + break; + case as_token_confed_end: + as_type = AS_SEQUENCE; + needtype = 1; + break; + case as_token_unknown: + default: + return NULL; + break; + } + } + + aspath->str = aspath_make_str_count (aspath); + + return aspath; +} + +/* Make hash value by raw aspath data. */ +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; + + while (length) + { + key += *pnt++; + length--; + } + + return key; +} + +/* If two aspath have same value then return 1 else return 0 */ +int +aspath_cmp (struct aspath *as1, struct aspath *as2) +{ + if (as1->length == as2->length + && !memcmp (as1->data, as2->data, as1->length)) + return 1; + else + return 0; +} + +/* AS path hash initialize. */ +void +aspath_init () +{ + ashash = hash_create_size (32767, aspath_key_make, aspath_cmp); +} + +/* return and as path value */ +const char * +aspath_print (struct aspath *as) +{ + return as->str; +} + +/* Printing functions */ +void +aspath_print_vty (struct vty *vty, struct aspath *as) +{ + vty_out (vty, "%s", as->str); +} + +void +aspath_show_all_iterator (struct hash_backet *backet, struct vty *vty) +{ + struct aspath *as; + + as = (struct aspath *) backet->data; + + vty_out (vty, "[%p:%d] (%ld) ", backet, backet->key, as->refcnt); + vty_out (vty, "%s%s", as->str, VTY_NEWLINE); +} + +/* Print all aspath and hash information. This function is used from + `show ip bgp paths' command. */ +void +aspath_print_all_vty (struct vty *vty) +{ + hash_iterate (ashash, + (void (*) (struct hash_backet *, void *)) + aspath_show_all_iterator, + vty); +} -- cgit v1.2.1