Adding upstream version 8.4.4.upstream/8.4.4upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 2276 insertions, 0 deletions

diff --git a/bgpd/bgp_aspath.c b/bgpd/bgp_aspath.c
new file mode 100644
index 0000000..06f6073
--- /dev/null
+++ b/bgpd/bgp_aspath.c
@@ -0,0 +1,2276 @@
+/* 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.
+ *
+ * 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 this program; see the file COPYING; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <zebra.h>
+
+#include "hash.h"
+#include "memory.h"
+#include "vector.h"
+#include "log.h"
+#include "stream.h"
+#include "command.h"
+#include "jhash.h"
+#include "queue.h"
+#include "filter.h"
+
+#include "bgpd/bgpd.h"
+#include "bgpd/bgp_aspath.h"
+#include "bgpd/bgp_debug.h"
+#include "bgpd/bgp_attr.h"
+#include "bgpd/bgp_errors.h"
+
+/* Attr. Flags and Attr. Type Code. */
+#define AS_HEADER_SIZE 2
+
+/* Now FOUR octets are used for AS value. */
+#define AS_VALUE_SIZE         sizeof(as_t)
+/* This is the old one */
+#define AS16_VALUE_SIZE	      sizeof(as16_t)
+
+/* 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.
+ *
+ * aspath_put returns bytes written, the only definitive record of
+ * size of wire-format attribute..
+ */
+
+/* Calculated size in bytes of ASN segment data to hold N ASN's */
+#define ASSEGMENT_DATA_SIZE(N, S)                                              \
+	((N) * ((S) ? AS_VALUE_SIZE : AS16_VALUE_SIZE))
+
+/* Calculated size of segment struct to hold N ASN's */
+#define ASSEGMENT_SIZE(N,S)  (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N,S))
+
+/* AS segment octet length. */
+#define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S)
+
+/* 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 {
+	uint8_t type;
+	uint8_t length;
+};
+
+/* Hash for aspath.  This is the top level structure of AS path. */
+static struct hash *ashash;
+
+/* Stream for SNMP. See aspath_snmp_pathseg */
+static struct stream *snmp_stream;
+
+/* Callers are required to initialize the memory */
+static as_t *assegment_data_new(int num)
+{
+	return (XMALLOC(MTYPE_AS_SEG_DATA, ASSEGMENT_DATA_SIZE(num, 1)));
+}
+
+static void assegment_data_free(as_t *asdata)
+{
+	XFREE(MTYPE_AS_SEG_DATA, asdata);
+}
+
+const char *const aspath_segment_type_str[] = {
+	"as-invalid", "as-set", "as-sequence", "as-confed-sequence",
+	"as-confed-set"
+};
+
+/* 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(uint8_t type, unsigned 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;
+
+	assegment_data_free(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, 1));
+
+	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;
+	int i;
+
+	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 == NULL)
+		return seg;
+
+	for (i = 0; i < num; i++)
+		newas[i] = asnum;
+
+	memcpy(newas + num, seg->as, ASSEGMENT_DATA_SIZE(seg->length, 1));
+	assegment_data_free(seg->as);
+	seg->as = newas;
+	seg->length += num;
+
+	return seg;
+}
+
+/* append given array of as numbers to the segment */
+static struct assegment *assegment_append_asns(struct assegment *seg,
+					       as_t *asnos, int num)
+{
+	as_t *newas;
+
+	if (!seg)
+		return seg;
+
+	newas = XREALLOC(MTYPE_AS_SEG_DATA, seg->as,
+			 ASSEGMENT_DATA_SIZE(seg->length + num, 1));
+
+	seg->as = newas;
+	memcpy(seg->as + seg->length, asnos,
+	       ASSEGMENT_DATA_SIZE(num, 1));
+	seg->length += num;
+	return seg;
+}
+
+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) {
+			int tail = 0;
+			int i;
+
+			qsort(seg->as, seg->length, sizeof(as_t), int_cmp);
+
+			/* weed out dupes */
+			for (i = 1; i < seg->length; i++) {
+				if (seg->as[tail] == seg->as[i])
+					continue;
+
+				tail++;
+				if (tail < i)
+					seg->as[tail] = seg->as[i];
+			}
+			/* seg->length can be 0.. */
+			if (seg->length)
+				seg->length = tail + 1;
+		}
+
+		/* 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(void)
+{
+	return XCALLOC(MTYPE_AS_PATH, sizeof(struct aspath));
+}
+
+/* Free AS path structure. */
+void aspath_free(struct aspath *aspath)
+{
+	if (!aspath)
+		return;
+	if (aspath->segments)
+		assegment_free_all(aspath->segments);
+	XFREE(MTYPE_AS_STR, aspath->str);
+
+	if (aspath->json) {
+		json_object_free(aspath->json);
+		aspath->json = NULL;
+	}
+
+	XFREE(MTYPE_AS_PATH, aspath);
+}
+
+/* Unintern aspath from AS path bucket. */
+void aspath_unintern(struct aspath **aspath)
+{
+	struct aspath *ret;
+	struct aspath *asp;
+
+	if (!*aspath)
+		return;
+
+	asp = *aspath;
+
+	if (asp->refcnt)
+		asp->refcnt--;
+
+	if (asp->refcnt == 0) {
+		/* This aspath must exist in aspath hash table. */
+		ret = hash_release(ashash, asp);
+		assert(ret != NULL);
+		aspath_free(asp);
+		*aspath = NULL;
+	}
+}
+
+/* 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(uint8_t type, uint8_t which)
+{
+	int i;
+	struct {
+		int type;
+		char start;
+		char end;
+	} aspath_delim_char[] = {{AS_SET, '{', '}'},
+				 {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 ' ';
+}
+
+/* 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(const 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;
+}
+
+/* Check if aspath has AS_SET or AS_CONFED_SET */
+bool aspath_check_as_sets(struct aspath *aspath)
+{
+	struct assegment *seg = aspath->segments;
+
+	while (seg) {
+		if (seg->type == AS_SET || seg->type == AS_CONFED_SET)
+			return true;
+		seg = seg->next;
+	}
+	return false;
+}
+
+/* Check if aspath has BGP_AS_ZERO */
+bool aspath_check_as_zero(struct aspath *aspath)
+{
+	struct assegment *seg = aspath->segments;
+	unsigned int i;
+
+	while (seg) {
+		for (i = 0; i < seg->length; i++)
+			if (seg->as[i] == BGP_AS_ZERO)
+				return true;
+		seg = seg->next;
+	}
+
+	return false;
+}
+
+/* Estimate size aspath /might/ take if encoded into an
+ * ASPATH attribute.
+ *
+ * This is a quick estimate, not definitive! aspath_put()
+ * may return a different number!!
+ */
+unsigned int aspath_size(struct aspath *aspath)
+{
+	int size = 0;
+	struct assegment *seg = aspath->segments;
+
+	while (seg) {
+		size += ASSEGMENT_SIZE(seg->length, 1);
+		seg = seg->next;
+	}
+	return size;
+}
+
+/* Return highest public ASN in path */
+as_t aspath_highest(struct aspath *aspath)
+{
+	struct assegment *seg = aspath->segments;
+	as_t highest = 0;
+	unsigned int i;
+
+	while (seg) {
+		for (i = 0; i < seg->length; i++)
+			if (seg->as[i] > highest
+			    && !BGP_AS_IS_PRIVATE(seg->as[i]))
+				highest = seg->as[i];
+		seg = seg->next;
+	}
+	return highest;
+}
+
+/* Return the left-most ASN in path */
+as_t aspath_leftmost(struct aspath *aspath)
+{
+	struct assegment *seg = aspath->segments;
+	as_t leftmost = 0;
+
+	if (seg && seg->length && seg->type == AS_SEQUENCE)
+		leftmost = seg->as[0];
+
+	return leftmost;
+}
+
+/* Return 1 if there are any 4-byte ASes in the path */
+bool aspath_has_as4(struct aspath *aspath)
+{
+	struct assegment *seg = aspath->segments;
+	unsigned int i;
+
+	while (seg) {
+		for (i = 0; i < seg->length; i++)
+			if (seg->as[i] > BGP_AS_MAX)
+				return true;
+		seg = seg->next;
+	}
+	return false;
+}
+
+/* Convert aspath structure to string expression. */
+static void aspath_make_str_count(struct aspath *as, bool make_json)
+{
+	struct assegment *seg;
+	int str_size;
+	int len = 0;
+	char *str_buf;
+	json_object *jaspath_segments = NULL;
+	json_object *jseg = NULL;
+	json_object *jseg_list = NULL;
+
+	if (make_json) {
+		as->json = json_object_new_object();
+		jaspath_segments = json_object_new_array();
+	}
+
+	/* Empty aspath. */
+	if (!as->segments) {
+		if (make_json) {
+			json_object_string_add(as->json, "string", "Local");
+			json_object_object_add(as->json, "segments",
+					       jaspath_segments);
+			json_object_int_add(as->json, "length", 0);
+		}
+		as->str = XMALLOC(MTYPE_AS_STR, 1);
+		as->str[0] = '\0';
+		as->str_len = 0;
+		return;
+	}
+
+	seg = as->segments;
+
+/* ASN takes 5 to 10 chars plus separator, 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.
+ *
+ * This was changed to 10 after the well-known BGP assertion, which
+ * had hit some parts of the Internet in May of 2009.
+ */
+#define ASN_STR_LEN (10 + 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);
+
+	while (seg) {
+		int i;
+		char separator;
+
+		/* Check AS type validity. Set separator for segment */
+		switch (seg->type) {
+		case AS_SET:
+		case AS_CONFED_SET:
+			separator = ',';
+			break;
+		case AS_SEQUENCE:
+		case AS_CONFED_SEQUENCE:
+			separator = ' ';
+			break;
+		default:
+			XFREE(MTYPE_AS_STR, str_buf);
+			as->str = NULL;
+			as->str_len = 0;
+			json_object_free(as->json);
+			as->json = NULL;
+
+			return;
+		}
+
+/* We might need to increase str_buf, particularly if path has
+ * differing segments types, our initial guesstimate above will
+ * have been wrong. Need 10 chars for ASN, a separator each and
+ * potentially two segment delimiters, plus a space between each
+ * segment and trailing zero.
+ *
+ * This definitely didn't work with the value of 5 bytes and
+ * 32-bit ASNs.
+ */
+#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));
+
+		if (make_json)
+			jseg_list = json_object_new_array();
+
+		/* write out the ASNs, with their separators, bar the last one*/
+		for (i = 0; i < seg->length; i++) {
+			if (make_json)
+				json_object_array_add(
+					jseg_list,
+					json_object_new_int64(seg->as[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", separator);
+		}
+
+		if (make_json) {
+			jseg = json_object_new_object();
+			json_object_string_add(
+				jseg, "type",
+				aspath_segment_type_str[seg->type]);
+			json_object_object_add(jseg, "list", jseg_list);
+			json_object_array_add(jaspath_segments, jseg);
+		}
+
+		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;
+	}
+
+	assert(len < str_size);
+
+	str_buf[len] = '\0';
+	as->str = str_buf;
+	as->str_len = len;
+
+	if (make_json) {
+		json_object_string_add(as->json, "string", str_buf);
+		json_object_object_add(as->json, "segments", jaspath_segments);
+		json_object_int_add(as->json, "length", aspath_count_hops(as));
+	}
+
+	return;
+}
+
+void aspath_str_update(struct aspath *as, bool make_json)
+{
+	XFREE(MTYPE_AS_STR, as->str);
+
+	if (as->json) {
+		json_object_free(as->json);
+		as->json = NULL;
+	}
+
+	aspath_make_str_count(as, make_json);
+}
+
+/* Intern allocated AS path. */
+struct aspath *aspath_intern(struct aspath *aspath)
+{
+	struct aspath *find;
+
+	/* Assert this AS path structure is not interned and has the string
+	   representation built. */
+	assert(aspath->refcnt == 0);
+	assert(aspath->str);
+
+	/* Check AS path hash. */
+	find = hash_get(ashash, aspath, hash_alloc_intern);
+	if (find != aspath)
+		aspath_free(aspath);
+
+	find->refcnt++;
+
+	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)
+{
+	unsigned short buflen = aspath->str_len + 1;
+	struct aspath *new;
+
+	new = XCALLOC(MTYPE_AS_PATH, sizeof(struct aspath));
+	new->json = NULL;
+
+	if (aspath->segments)
+		new->segments = assegment_dup_all(aspath->segments);
+
+	if (!aspath->str)
+		return new;
+
+	new->str = XMALLOC(MTYPE_AS_STR, buflen);
+	new->str_len = aspath->str_len;
+
+	/* copy the string data */
+	if (aspath->str_len > 0)
+		memcpy(new->str, aspath->str, buflen);
+	else
+		new->str[0] = '\0';
+
+	return new;
+}
+
+static void *aspath_hash_alloc(void *arg)
+{
+	const struct aspath *aspath = arg;
+	struct aspath *new;
+
+	/* Malformed AS path value. */
+	assert(aspath->str);
+
+	/* New aspath structure is needed. */
+	new = XMALLOC(MTYPE_AS_PATH, sizeof(struct aspath));
+
+	/* Reuse segments and string representation */
+	new->refcnt = 0;
+	new->segments = aspath->segments;
+	new->str = aspath->str;
+	new->str_len = aspath->str_len;
+	new->json = aspath->json;
+
+	return new;
+}
+
+/* parse as-segment byte stream in struct assegment */
+static int assegments_parse(struct stream *s, size_t length,
+			    struct assegment **result, int use32bit)
+{
+	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 0;
+
+	if (BGP_DEBUG(as4, AS4_SEGMENT))
+		zlog_debug(
+			"[AS4SEG] Parse aspath segment: got total byte length %lu",
+			(unsigned long)length);
+	/* basic checks */
+	if ((STREAM_READABLE(s) < length)
+	    || (STREAM_READABLE(s) < AS_HEADER_SIZE)
+	    || (length % AS16_VALUE_SIZE))
+		return -1;
+
+	while (bytes < length) {
+		int i;
+		size_t seg_size;
+
+		if ((length - bytes) <= AS_HEADER_SIZE) {
+			if (head)
+				assegment_free_all(head);
+			return -1;
+		}
+
+		/* softly softly, get the header first on its own */
+		segh.type = stream_getc(s);
+		segh.length = stream_getc(s);
+
+		seg_size = ASSEGMENT_SIZE(segh.length, use32bit);
+
+		if (BGP_DEBUG(as4, AS4_SEGMENT))
+			zlog_debug(
+				"[AS4SEG] Parse aspath segment: got type %d, length %d",
+				segh.type, segh.length);
+
+		/* check it.. */
+		if (((bytes + seg_size) > length)
+		    /* 1771bis 4.3b: seg length contains one or more */
+		    || (segh.length == 0)
+		    /* Paranoia in case someone changes type of segment length.
+		     * Shift both values by 0x10 to make the comparison operate
+		     * on more, than 8 bits (otherwise it's a warning, bug
+		     * #564).
+		     */
+		    || ((sizeof(segh.length) > 1)
+			&& (0x10 + segh.length > 0x10 + AS_SEGMENT_MAX))) {
+			if (head)
+				assegment_free_all(head);
+			return -1;
+		}
+
+		switch (segh.type) {
+		case AS_SEQUENCE:
+		case AS_SET:
+		case AS_CONFED_SEQUENCE:
+		case AS_CONFED_SET:
+			break;
+		default:
+			if (head)
+				assegment_free_all(head);
+			return -1;
+		}
+
+		/* 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 = seg;
+
+		for (i = 0; i < segh.length; i++)
+			seg->as[i] =
+				(use32bit) ? stream_getl(s) : stream_getw(s);
+
+		bytes += seg_size;
+
+		if (BGP_DEBUG(as4, AS4_SEGMENT))
+			zlog_debug(
+				"[AS4SEG] Parse aspath segment: Bytes now: %lu",
+				(unsigned long)bytes);
+
+		prev = seg;
+	}
+
+	*result = assegment_normalise(head);
+	return 0;
+}
+
+/* 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.
+
+   On error NULL is returned.
+ */
+struct aspath *aspath_parse(struct stream *s, size_t length, int use32bit)
+{
+	struct aspath as;
+	struct aspath *find;
+
+	/* If length is odd it's malformed AS path. */
+	/* Nit-picking: if (use32bit == 0) it is malformed if odd,
+	 * otherwise its malformed when length is larger than 2 and (length-2)
+	 * is not dividable by 4.
+	 * But... this time we're lazy
+	 */
+	if (length % AS16_VALUE_SIZE)
+		return NULL;
+
+	memset(&as, 0, sizeof(as));
+	if (assegments_parse(s, length, &as.segments, use32bit) < 0)
+		return NULL;
+
+	/* If already same aspath exist then return it. */
+	find = hash_get(ashash, &as, aspath_hash_alloc);
+
+	/* if the aspath was already hashed free temporary memory. */
+	if (find->refcnt) {
+		assegment_free_all(as.segments);
+		/* aspath_key_make() always updates the string */
+		XFREE(MTYPE_AS_STR, as.str);
+		if (as.json) {
+			json_object_free(as.json);
+			as.json = NULL;
+		}
+	}
+
+	find->refcnt++;
+
+	return find;
+}
+
+static void assegment_data_put(struct stream *s, as_t *as, int num,
+			       int use32bit)
+{
+	int i;
+	assert(num <= AS_SEGMENT_MAX);
+
+	for (i = 0; i < num; i++)
+		if (use32bit)
+			stream_putl(s, as[i]);
+		else {
+			if (as[i] <= BGP_AS_MAX)
+				stream_putw(s, as[i]);
+			else
+				stream_putw(s, BGP_AS_TRANS);
+		}
+}
+
+static size_t assegment_header_put(struct stream *s, uint8_t type, int length)
+{
+	size_t lenp;
+	assert(length <= AS_SEGMENT_MAX);
+	stream_putc(s, type);
+	lenp = stream_get_endp(s);
+	stream_putc(s, length);
+	return lenp;
+}
+
+/* write aspath data to stream */
+size_t aspath_put(struct stream *s, struct aspath *as, int use32bit)
+{
+	struct assegment *seg = as->segments;
+	size_t bytes = 0;
+
+	if (!seg || seg->length == 0)
+		return 0;
+
+	/*
+	 * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
+	 * At the moment, we would write out a partial aspath, and our
+	 * peer
+	 * will complain and drop the session :-/
+	 *
+	 * The general assumption here is that many things tested will
+	 * never happen.  And, in real live, up to now, they have not.
+	 */
+	while (seg && (ASSEGMENT_LEN(seg, use32bit) <= STREAM_WRITEABLE(s))) {
+		struct assegment *next = seg->next;
+		int written = 0;
+		int asns_packed = 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 + written),
+					   AS_SEGMENT_MAX, use32bit);
+			written += AS_SEGMENT_MAX;
+			bytes += ASSEGMENT_SIZE(AS_SEGMENT_MAX, use32bit);
+		}
+
+		/* 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, use32bit);
+
+		/* 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.
+		 */
+		while (next && ASSEGMENTS_PACKABLE(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, next->as, next->length, use32bit);
+
+			/* update the length of the segment header */
+			stream_putc_at(s, lenp,
+				       seg->length - written + next->length);
+			asns_packed += next->length;
+
+			next = next->next;
+		}
+
+		bytes += ASSEGMENT_SIZE(seg->length - written + asns_packed,
+					use32bit);
+		seg = next;
+	}
+	return bytes;
+}
+
+/* This is for SNMP BGP4PATHATTRASPATHSEGMENT
+ * We have no way to manage the storage, so we use a static stream
+ * wrapper around aspath_put.
+ */
+uint8_t *aspath_snmp_pathseg(struct aspath *as, size_t *varlen)
+{
+#define SNMP_PATHSEG_MAX 1024
+
+	if (!snmp_stream)
+		snmp_stream = stream_new(SNMP_PATHSEG_MAX);
+	else
+		stream_reset(snmp_stream);
+
+	if (!as) {
+		*varlen = 0;
+		return NULL;
+	}
+	aspath_put(snmp_stream, as, 0); /* use 16 bit for now here */
+
+	*varlen = stream_get_endp(snmp_stream);
+	return stream_pnt(snmp_stream);
+}
+
+static 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) {
+		asset = assegment_new(AS_SET, 1);
+		if (!aspath->segments)
+			aspath->segments = asset;
+		else {
+			struct assegment *seg = aspath->segments;
+			while (seg->next)
+				seg = seg->next;
+			seg->next = asset;
+		}
+		asset->type = AS_SET;
+		asset->length = 1;
+		asset->as[0] = as;
+	} else {
+		/* Check this AS value already exists or not. */
+		for (i = 0; i < asset->length; i++)
+			if (asset->as[i] == as)
+				return asset;
+
+		asset->length++;
+		asset->as = XREALLOC(MTYPE_AS_SEG_DATA, asset->as,
+				     asset->length * AS_VALUE_SIZE);
+		asset->as[asset->length - 1] = as;
+	}
+
+
+	return asset;
+}
+
+/* Modify as1 using as2 for aggregation. */
+struct aspath *aspath_aggregate(struct aspath *as1, struct aspath *as2)
+{
+	int i;
+	int minlen = 0;
+	int match = 0;
+	int from;
+	struct assegment *seg1 = as1->segments;
+	struct assegment *seg2 = as2->segments;
+	struct aspath *aspath = NULL;
+	struct assegment *asset = NULL;
+	struct assegment *prevseg = NULL;
+
+	/* First of all check common leading sequence. */
+	while (seg1 && seg2) {
+		/* 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->as[match] != seg2->as[match])
+				break;
+
+		if (match) {
+			struct assegment *seg = assegment_new(seg1->type, 0);
+
+			seg = assegment_append_asns(seg, seg1->as, match);
+
+			if (!aspath) {
+				aspath = aspath_new();
+				aspath->segments = seg;
+			} else
+				prevseg->next = seg;
+
+			prevseg = seg;
+		}
+
+		if (match != minlen || match != seg1->length
+		    || seg1->length != seg2->length)
+			break;
+		/* We are moving on to the next segment to reset match */
+		else
+			match = 0;
+
+		seg1 = seg1->next;
+		seg2 = seg2->next;
+	}
+
+	if (!aspath)
+		aspath = aspath_new();
+
+	/* Make as-set using rest of all information. */
+	from = match;
+	while (seg1) {
+		for (i = from; i < seg1->length; i++)
+			asset = aspath_aggregate_as_set_add(aspath, asset,
+							    seg1->as[i]);
+
+		from = 0;
+		seg1 = seg1->next;
+	}
+
+	from = match;
+	while (seg2) {
+		for (i = from; i < seg2->length; i++)
+			asset = aspath_aggregate_as_set_add(aspath, asset,
+							    seg2->as[i]);
+
+		from = 0;
+		seg2 = seg2->next;
+	}
+
+	assegment_normalise(aspath->segments);
+	aspath_str_update(aspath, false);
+	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. */
+bool aspath_firstas_check(struct aspath *aspath, as_t asno)
+{
+	if ((aspath == NULL) || (aspath->segments == NULL))
+		return false;
+
+	if (aspath->segments && (aspath->segments->type == AS_SEQUENCE)
+	    && (aspath->segments->as[0] == asno))
+		return true;
+
+	return false;
+}
+
+unsigned int aspath_get_first_as(struct aspath *aspath)
+{
+	if (aspath == NULL || aspath->segments == NULL)
+		return 0;
+
+	return aspath->segments->as[0];
+}
+
+unsigned int aspath_get_last_as(struct aspath *aspath)
+{
+	int i;
+	unsigned int last_as = 0;
+	const struct assegment *seg;
+
+	if (aspath == NULL || aspath->segments == NULL)
+		return last_as;
+
+	seg = aspath->segments;
+
+	while (seg) {
+		if (seg->type == AS_SEQUENCE || seg->type == AS_CONFED_SEQUENCE)
+			for (i = 0; i < seg->length; i++)
+				last_as = seg->as[i];
+		seg = seg->next;
+	}
+
+	return last_as;
+}
+
+/* AS path loop check.  If aspath contains asno then return >= 1. */
+int aspath_loop_check(struct aspath *aspath, as_t asno)
+{
+	struct assegment *seg;
+	int count = 0;
+
+	if ((aspath == NULL) || (aspath->segments == NULL))
+		return 0;
+
+	seg = aspath->segments;
+
+	while (seg) {
+		int i;
+
+		for (i = 0; i < seg->length; i++)
+			if (seg->as[i] == asno)
+				count++;
+
+		seg = seg->next;
+	}
+	return count;
+}
+
+/* When all of AS path is private AS return 1.  */
+bool aspath_private_as_check(struct aspath *aspath)
+{
+	struct assegment *seg;
+
+	if (!(aspath && aspath->segments))
+		return false;
+
+	seg = aspath->segments;
+
+	while (seg) {
+		int i;
+
+		for (i = 0; i < seg->length; i++) {
+			if (!BGP_AS_IS_PRIVATE(seg->as[i]))
+				return false;
+		}
+		seg = seg->next;
+	}
+	return true;
+}
+
+/* Replace all instances of the target ASN with our own ASN */
+struct aspath *aspath_replace_specific_asn(struct aspath *aspath,
+					   as_t target_asn, as_t our_asn)
+{
+	struct aspath *new;
+	struct assegment *seg;
+
+	new = aspath_dup(aspath);
+	seg = new->segments;
+
+	while (seg) {
+		int i;
+
+		for (i = 0; i < seg->length; i++) {
+			if (seg->as[i] == target_asn)
+				seg->as[i] = our_asn;
+		}
+		seg = seg->next;
+	}
+
+	aspath_str_update(new, false);
+	return new;
+}
+
+/* Replace all ASNs with our own ASN */
+struct aspath *aspath_replace_all_asn(struct aspath *aspath, as_t our_asn)
+{
+	struct aspath *new;
+	struct assegment *seg;
+
+	new = aspath_dup(aspath);
+	seg = new->segments;
+
+	while (seg) {
+		int i;
+
+		for (i = 0; i < seg->length; i++)
+			seg->as[i] = our_asn;
+
+		seg = seg->next;
+	}
+
+	aspath_str_update(new, false);
+	return new;
+}
+
+/* Replace all private ASNs with our own ASN */
+struct aspath *aspath_replace_private_asns(struct aspath *aspath, as_t asn,
+					   as_t peer_asn)
+{
+	struct aspath *new;
+	struct assegment *seg;
+
+	new = aspath_dup(aspath);
+	seg = new->segments;
+
+	while (seg) {
+		int i;
+
+		for (i = 0; i < seg->length; i++) {
+			/* Don't replace if public ASN or peer's ASN */
+			if (BGP_AS_IS_PRIVATE(seg->as[i])
+			    && (seg->as[i] != peer_asn))
+				seg->as[i] = asn;
+		}
+		seg = seg->next;
+	}
+
+	aspath_str_update(new, false);
+	return new;
+}
+
+/* Remove all private ASNs */
+struct aspath *aspath_remove_private_asns(struct aspath *aspath, as_t peer_asn)
+{
+	struct aspath *new;
+	struct assegment *seg;
+	struct assegment *new_seg;
+	struct assegment *last_new_seg;
+	int i;
+	int j;
+	int public = 0;
+	int peer = 0;
+
+	new = XCALLOC(MTYPE_AS_PATH, sizeof(struct aspath));
+
+	new->json = NULL;
+	new_seg = NULL;
+	last_new_seg = NULL;
+	seg = aspath->segments;
+	while (seg) {
+		public = 0;
+		peer = 0;
+		for (i = 0; i < seg->length; i++) {
+			// ASN is public
+			if (!BGP_AS_IS_PRIVATE(seg->as[i]))
+				public++;
+			/* ASN matches peer's.
+			 * Don't double-count if peer_asn is public.
+			 */
+			else if (seg->as[i] == peer_asn)
+				peer++;
+		}
+
+		// The entire segment is public so copy it
+		if (public == seg->length)
+			new_seg = assegment_dup(seg);
+
+		// The segment is a mix of public and private ASNs. Copy as many
+		// spots as
+		// there are public ASNs then come back and fill in only the
+		// public ASNs.
+		else {
+			/* length needs to account for all retained ASNs
+			 * (public or peer_asn), not just public
+			 */
+			new_seg = assegment_new(seg->type, (public + peer));
+			j = 0;
+			for (i = 0; i < seg->length; i++) {
+				// keep ASN if public or matches peer's ASN
+				if (!BGP_AS_IS_PRIVATE(seg->as[i])
+				    || (seg->as[i] == peer_asn)) {
+					new_seg->as[j] = seg->as[i];
+					j++;
+				}
+			}
+		}
+
+		// This is the first segment so set the aspath segments pointer
+		// to this one
+		if (!last_new_seg)
+			new->segments = new_seg;
+		else
+			last_new_seg->next = new_seg;
+
+		last_new_seg = new_seg;
+		seg = seg->next;
+	}
+
+	aspath_str_update(new, false);
+	return new;
+}
+
+/* AS path confed check.  If aspath contains confed set or sequence then return
+ * 1. */
+bool aspath_confed_check(struct aspath *aspath)
+{
+	struct assegment *seg;
+
+	if (!(aspath && aspath->segments))
+		return false;
+
+	seg = aspath->segments;
+
+	while (seg) {
+		if (seg->type == AS_CONFED_SET
+		    || seg->type == AS_CONFED_SEQUENCE)
+			return true;
+		seg = seg->next;
+	}
+	return false;
+}
+
+/* Leftmost AS path segment confed check.  If leftmost AS segment is of type
+  AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1.  */
+bool aspath_left_confed_check(struct aspath *aspath)
+{
+
+	if (!(aspath && aspath->segments))
+		return false;
+
+	if ((aspath->segments->type == AS_CONFED_SEQUENCE)
+	    || (aspath->segments->type == AS_CONFED_SET))
+		return true;
+
+	return false;
+}
+
+/* Merge as1 to as2.  as2 should be uninterned aspath. */
+static struct aspath *aspath_merge(struct aspath *as1, struct aspath *as2)
+{
+	struct assegment *last, *new;
+
+	if (!as1 || !as2)
+		return NULL;
+
+	last = new = assegment_dup_all(as1->segments);
+
+	/* find the last valid segment */
+	while (last && last->next)
+		last = last->next;
+
+	if (last)
+		last->next = as2->segments;
+	as2->segments = new;
+	aspath_str_update(as2, false);
+	return as2;
+}
+
+/* Prepend as1 to as2.  as2 should be uninterned aspath. */
+struct aspath *aspath_prepend(struct aspath *as1, struct aspath *as2)
+{
+	struct assegment *as1segtail;
+	struct assegment *as2segtail;
+	struct assegment *as2seghead;
+
+	if (!as1 || !as2)
+		return NULL;
+
+	/* If as2 is empty, only need to dupe as1's chain onto as2 */
+	if (as2->segments == NULL) {
+		as2->segments = assegment_dup_all(as1->segments);
+		aspath_str_update(as2, false);
+		return as2;
+	}
+
+	/* If as1 is empty AS, no prepending to do. */
+	if (as1->segments == NULL)
+		return as2;
+
+	/* find the tail as1's segment chain. */
+	as1segtail = as1->segments;
+	while (as1segtail && as1segtail->next)
+		as1segtail = as1segtail->next;
+
+	/* Delete any AS_CONFED_SEQUENCE segment from as2. */
+	if (as1segtail->type == AS_SEQUENCE
+	    && as2->segments->type == AS_CONFED_SEQUENCE)
+		as2 = aspath_delete_confed_seq(as2);
+
+	if (!as2->segments) {
+		as2->segments = assegment_dup_all(as1->segments);
+		aspath_str_update(as2, false);
+		return as2;
+	}
+
+	/* Compare last segment type of as1 and first segment type of as2. */
+	if (as1segtail->type != as2->segments->type)
+		return aspath_merge(as1, as2);
+
+	if (as1segtail->type == AS_SEQUENCE) {
+		/* 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
+		 */
+
+		/* save as2 head */
+		as2seghead = as2->segments;
+
+		/* dupe as1 onto as2's head */
+		as2segtail = as2->segments = assegment_dup_all(as1->segments);
+
+		/* refind the tail of as2 */
+		while (as2segtail && as2segtail->next)
+			as2segtail = as2segtail->next;
+
+		/* merge the old head, seg2, into tail, seg1 */
+		assegment_append_asns(as2segtail, as2seghead->as,
+				      as2seghead->length);
+
+		/*
+		 * bypass the merged seg2, and attach any chain after it
+		 * to chain descending from as2's head
+		 */
+		if (as2segtail)
+			as2segtail->next = as2seghead->next;
+
+		/* as2->segments is now referenceless and useless */
+		assegment_free(as2seghead);
+
+		/* we've now prepended as1's segment chain to as2, merging
+		 * the inbetween AS_SEQUENCE of seg2 in the process
+		 */
+		aspath_str_update(as2, false);
+		return as2;
+	} else {
+		/* AS_SET merge code is needed at here. */
+		return aspath_merge(as1, as2);
+	}
+	/* XXX: Ermmm, what if as1 has multiple segments?? */
+
+	/* Not reached */
+}
+
+/* Iterate over AS_PATH segments and wipe all occurrences of the
+ * listed AS numbers. Hence some segments may lose some or even
+ * all data on the way, the operation is implemented as a smarter
+ * version of aspath_dup(), which allocates memory to hold the new
+ * data, not the original. The new AS path is returned.
+ */
+struct aspath *aspath_filter_exclude(struct aspath *source,
+				     struct aspath *exclude_list)
+{
+	struct assegment *srcseg, *exclseg, *lastseg;
+	struct aspath *newpath;
+
+	newpath = aspath_new();
+	lastseg = NULL;
+
+	for (srcseg = source->segments; srcseg; srcseg = srcseg->next) {
+		unsigned i, y, newlen = 0, done = 0, skip_as;
+		struct assegment *newseg;
+
+		/* Find out, how much ASns are we going to pick from this
+		 * segment.
+		 * We can't perform filtering right inline, because the size of
+		 * the new segment isn't known at the moment yet.
+		 */
+		for (i = 0; i < srcseg->length; i++) {
+			skip_as = 0;
+			for (exclseg = exclude_list->segments;
+			     exclseg && !skip_as; exclseg = exclseg->next)
+				for (y = 0; y < exclseg->length; y++)
+					if (srcseg->as[i] == exclseg->as[y]) {
+						skip_as = 1;
+						// There's no sense in testing
+						// the rest of exclusion list,
+						// bail out.
+						break;
+					}
+			if (!skip_as)
+				newlen++;
+		}
+		/* newlen is now the number of ASns to copy */
+		if (!newlen)
+			continue;
+
+		/* Actual copying. Allocate memory and iterate once more,
+		 * performing filtering. */
+		newseg = assegment_new(srcseg->type, newlen);
+		for (i = 0; i < srcseg->length; i++) {
+			skip_as = 0;
+			for (exclseg = exclude_list->segments;
+			     exclseg && !skip_as; exclseg = exclseg->next)
+				for (y = 0; y < exclseg->length; y++)
+					if (srcseg->as[i] == exclseg->as[y]) {
+						skip_as = 1;
+						break;
+					}
+			if (skip_as)
+				continue;
+			newseg->as[done++] = srcseg->as[i];
+		}
+		/* At his point newlen must be equal to done, and both must be
+		 * positive. Append
+		 * the filtered segment to the gross result. */
+		if (!lastseg)
+			newpath->segments = newseg;
+		else
+			lastseg->next = newseg;
+		lastseg = newseg;
+	}
+	aspath_str_update(newpath, false);
+	/* We are happy returning even an empty AS_PATH, because the
+	 * administrator
+	 * might expect this very behaviour. There's a mean to avoid this, if
+	 * necessary,
+	 * by having a match rule against certain AS_PATH regexps in the
+	 * route-map index.
+	 */
+	aspath_free(source);
+	return newpath;
+}
+
+/* Add specified AS to the leftmost of aspath. */
+static struct aspath *aspath_add_asns(struct aspath *aspath, as_t asno,
+				      uint8_t type, unsigned num)
+{
+	struct assegment *assegment = aspath->segments;
+	unsigned i;
+
+	if (assegment && assegment->type == type) {
+		/* extend existing segment */
+		aspath->segments =
+			assegment_prepend_asns(aspath->segments, asno, num);
+	} else {
+		/* prepend with new segment */
+		struct assegment *newsegment = assegment_new(type, num);
+		for (i = 0; i < num; i++)
+			newsegment->as[i] = asno;
+
+		/* insert potentially replacing empty segment */
+		if (assegment && assegment->length == 0) {
+			newsegment->next = assegment->next;
+			assegment_free(assegment);
+		} else
+			newsegment->next = assegment;
+		aspath->segments = newsegment;
+	}
+
+	aspath_str_update(aspath, false);
+	return aspath;
+}
+
+/* Add specified AS to the leftmost of aspath num times. */
+struct aspath *aspath_add_seq_n(struct aspath *aspath, as_t asno, unsigned num)
+{
+	return aspath_add_asns(aspath, asno, AS_SEQUENCE, num);
+}
+
+/* Add specified AS to the leftmost of aspath. */
+struct aspath *aspath_add_seq(struct aspath *aspath, as_t asno)
+{
+	return aspath_add_asns(aspath, asno, AS_SEQUENCE, 1);
+}
+
+/* Compare leftmost AS value for MED check.  If as1's leftmost AS and
+   as2's leftmost AS is same return 1. */
+bool aspath_cmp_left(const struct aspath *aspath1, const struct aspath *aspath2)
+{
+	const struct assegment *seg1;
+	const struct assegment *seg2;
+
+	if (!(aspath1 && aspath2))
+		return false;
+
+	seg1 = aspath1->segments;
+	seg2 = aspath2->segments;
+
+	/* If both paths are originated in this AS then we do want to compare
+	 * MED */
+	if (!seg1 && !seg2)
+		return true;
+
+	/* find first non-confed segments for each */
+	while (seg1 && ((seg1->type == AS_CONFED_SEQUENCE)
+			|| (seg1->type == AS_CONFED_SET)))
+		seg1 = seg1->next;
+
+	while (seg2 && ((seg2->type == AS_CONFED_SEQUENCE)
+			|| (seg2->type == AS_CONFED_SET)))
+		seg2 = seg2->next;
+
+	/* Check as1's */
+	if (!(seg1 && seg2 && (seg1->type == AS_SEQUENCE)
+	      && (seg2->type == AS_SEQUENCE)))
+		return false;
+
+	if (seg1->as[0] == seg2->as[0])
+		return true;
+
+	return false;
+}
+
+/* Truncate an aspath after a number of hops, and put the hops remaining
+ * at the front of another aspath.  Needed for AS4 compat.
+ *
+ * Returned aspath is a /new/ aspath, which should either by free'd or
+ * interned by the caller, as desired.
+ */
+struct aspath *aspath_reconcile_as4(struct aspath *aspath,
+				    struct aspath *as4path)
+{
+	struct assegment *seg, *newseg, *prevseg = NULL;
+	struct aspath *newpath = NULL, *mergedpath;
+	int hops, cpasns = 0;
+
+	if (!aspath || !as4path)
+		return NULL;
+
+	seg = aspath->segments;
+
+	/* CONFEDs should get reconciled too.. */
+	hops = (aspath_count_hops(aspath) + aspath_count_confeds(aspath))
+	       - aspath_count_hops(as4path);
+
+	if (hops < 0) {
+		if (BGP_DEBUG(as4, AS4))
+			flog_warn(
+				EC_BGP_ASPATH_FEWER_HOPS,
+				"[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
+		/* Something's gone wrong. The RFC says we should now ignore
+		 * AS4_PATH,
+		 * which is daft behaviour - it contains vital loop-detection
+		 * information which must have been removed from AS_PATH.
+		 */
+		hops = aspath_count_hops(aspath);
+	}
+
+	if (!hops) {
+		newpath = aspath_dup(as4path);
+		aspath_str_update(newpath, false);
+		return newpath;
+	}
+
+	if (BGP_DEBUG(as4, AS4))
+		zlog_debug(
+			"[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
+			aspath->str, as4path->str);
+
+	while (seg && hops > 0) {
+		switch (seg->type) {
+		case AS_SET:
+		case AS_CONFED_SET:
+			hops--;
+			cpasns = seg->length;
+			break;
+		case AS_CONFED_SEQUENCE:
+			/* Should never split a confed-sequence, if hop-count
+			 * suggests we must then something's gone wrong
+			 * somewhere.
+			 *
+			 * Most important goal is to preserve AS_PATHs prime
+			 * function
+			 * as loop-detector, so we fudge the numbers so that the
+			 * entire
+			 * confed-sequence is merged in.
+			 */
+			if (hops < seg->length) {
+				if (BGP_DEBUG(as4, AS4))
+					zlog_debug(
+						"[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls across 2/4 ASN boundary somewhere, broken..");
+				hops = seg->length;
+			}
+		/* fallthru */
+		case AS_SEQUENCE:
+			cpasns = MIN(seg->length, hops);
+			hops -= seg->length;
+		}
+
+		assert(cpasns <= seg->length);
+
+		newseg = assegment_new(seg->type, 0);
+		newseg = assegment_append_asns(newseg, seg->as, cpasns);
+
+		if (!newpath) {
+			newpath = aspath_new();
+			newpath->segments = newseg;
+		} else
+			prevseg->next = newseg;
+
+		prevseg = newseg;
+		seg = seg->next;
+	}
+
+	/* We may be able to join some segments here, and we must
+	 * do this because... we want normalised aspaths in out hash
+	 * and we do not want to stumble in aspath_put.
+	 */
+	mergedpath = aspath_merge(newpath, aspath_dup(as4path));
+	aspath_free(newpath);
+	mergedpath->segments = assegment_normalise(mergedpath->segments);
+	aspath_str_update(mergedpath, false);
+
+	if (BGP_DEBUG(as4, AS4))
+		zlog_debug("[AS4] result of synthesizing is %s",
+			   mergedpath->str);
+
+	return mergedpath;
+}
+
+/* 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).  */
+bool aspath_cmp_left_confed(const struct aspath *aspath1,
+			    const struct aspath *aspath2)
+{
+	if (!(aspath1 && aspath2))
+		return false;
+
+	if (!(aspath1->segments && aspath2->segments))
+		return false;
+
+	if ((aspath1->segments->type != AS_CONFED_SEQUENCE)
+	    || (aspath2->segments->type != AS_CONFED_SEQUENCE))
+		return false;
+
+	if (aspath1->segments->as[0] == aspath2->segments->as[0])
+		return true;
+
+	return false;
+}
+
+/* Delete all AS_CONFED_SEQUENCE/SET segments from aspath.
+ * RFC 5065 section 4.1.c.1
+ *
+ * 1) if any path segments of the AS_PATH are of the type
+ *    AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be
+ *    removed from the AS_PATH attribute, leaving the sanitized
+ *    AS_PATH attribute to be operated on by steps 2, 3 or 4.
+ */
+struct aspath *aspath_delete_confed_seq(struct aspath *aspath)
+{
+	struct assegment *seg, *prev, *next;
+	char removed_confed_segment;
+
+	if (!(aspath && aspath->segments))
+		return aspath;
+
+	seg = aspath->segments;
+	removed_confed_segment = 0;
+	next = NULL;
+	prev = NULL;
+
+	while (seg) {
+		next = seg->next;
+
+		if (seg->type == AS_CONFED_SEQUENCE
+		    || seg->type == AS_CONFED_SET) {
+			/* This is the first segment in the aspath */
+			if (aspath->segments == seg)
+				aspath->segments = seg->next;
+			else
+				prev->next = seg->next;
+
+			assegment_free(seg);
+			removed_confed_segment = 1;
+		} else
+			prev = seg;
+
+		seg = next;
+	}
+
+	if (removed_confed_segment)
+		aspath_str_update(aspath, false);
+
+	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_asns(aspath, asno, AS_CONFED_SEQUENCE, 1);
+}
+
+/* Add new as value to as path structure. */
+static void aspath_as_add(struct aspath *as, as_t asno)
+{
+	struct assegment *seg = as->segments;
+
+	if (!seg)
+		return;
+
+	/* Last segment search procedure. */
+	while (seg->next)
+		seg = seg->next;
+
+	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 *seg = as->segments;
+	struct assegment *new = assegment_new(type, 0);
+
+	if (seg) {
+		while (seg->next)
+			seg = seg->next;
+		seg->next = new;
+	} else
+		as->segments = new;
+}
+
+struct aspath *aspath_empty(void)
+{
+	return aspath_parse(NULL, 0, 1); /* 32Bit ;-) */
+}
+
+struct aspath *aspath_empty_get(void)
+{
+	struct aspath *aspath;
+
+	aspath = aspath_new();
+	aspath_make_str_count(aspath, false);
+	return aspath;
+}
+
+unsigned long aspath_count(void)
+{
+	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_seq_start,
+	as_token_confed_seq_end,
+	as_token_confed_set_start,
+	as_token_confed_set_end,
+	as_token_unknown
+};
+
+/* Return next token and point for string parse. */
+static const char *aspath_gettoken(const char *buf, enum as_token *token,
+				   unsigned long *asno)
+{
+	const char *p = buf;
+
+	/* Skip separators (space for sequences, ',' for sets). */
+	while (isspace((unsigned char)*p) || *p == ',')
+		p++;
+
+	/* Check the end of the string and type specify characters
+	   (e.g. {}()). */
+	switch (*p) {
+	case '\0':
+		return NULL;
+	case '{':
+		*token = as_token_set_start;
+		p++;
+		return p;
+	case '}':
+		*token = as_token_set_end;
+		p++;
+		return p;
+	case '(':
+		*token = as_token_confed_seq_start;
+		p++;
+		return p;
+	case ')':
+		*token = as_token_confed_seq_end;
+		p++;
+		return p;
+	case '[':
+		*token = as_token_confed_set_start;
+		p++;
+		return p;
+	case ']':
+		*token = as_token_confed_set_end;
+		p++;
+		return p;
+	}
+
+	/* Check actual AS value. */
+	if (isdigit((unsigned char)*p)) {
+		as_t asval;
+
+		*token = as_token_asval;
+		asval = (*p - '0');
+		p++;
+
+		while (isdigit((unsigned char)*p)) {
+			asval *= 10;
+			asval += (*p - '0');
+			p++;
+		}
+		*asno = asval;
+		return p;
+	}
+
+	/* There is no match then return unknown token. */
+	*token = as_token_unknown;
+	p++;
+	return p;
+}
+
+struct aspath *aspath_str2aspath(const char *str)
+{
+	enum as_token token = as_token_unknown;
+	unsigned short as_type;
+	unsigned long asno = 0;
+	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_seq_start:
+			as_type = AS_CONFED_SEQUENCE;
+			aspath_segment_add(aspath, as_type);
+			needtype = 0;
+			break;
+		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;
+		}
+	}
+
+	aspath_make_str_count(aspath, false);
+
+	return aspath;
+}
+
+/* Make hash value by raw aspath data. */
+unsigned int aspath_key_make(const void *p)
+{
+	const struct aspath *aspath = p;
+	unsigned int key = 0;
+
+	if (!aspath->str)
+		aspath_str_update((struct aspath *)aspath, false);
+
+	key = jhash(aspath->str, aspath->str_len, 2334325);
+
+	return key;
+}
+
+/* If two aspath have same value then return 1 else return 0 */
+bool aspath_cmp(const void *arg1, const void *arg2)
+{
+	const struct assegment *seg1 = ((const struct aspath *)arg1)->segments;
+	const struct assegment *seg2 = ((const struct aspath *)arg2)->segments;
+
+	while (seg1 || seg2) {
+		int i;
+		if ((!seg1 && seg2) || (seg1 && !seg2))
+			return false;
+		if (seg1->type != seg2->type)
+			return false;
+		if (seg1->length != seg2->length)
+			return false;
+		for (i = 0; i < seg1->length; i++)
+			if (seg1->as[i] != seg2->as[i])
+				return false;
+		seg1 = seg1->next;
+		seg2 = seg2->next;
+	}
+	return true;
+}
+
+/* AS path hash initialize. */
+void aspath_init(void)
+{
+	ashash = hash_create_size(32768, aspath_key_make, aspath_cmp,
+				  "BGP AS Path");
+}
+
+void aspath_finish(void)
+{
+	hash_clean(ashash, (void (*)(void *))aspath_free);
+	hash_free(ashash);
+	ashash = NULL;
+
+	if (snmp_stream)
+		stream_free(snmp_stream);
+}
+
+/* return and as path value */
+const char *aspath_print(struct aspath *as)
+{
+	return (as ? as->str : NULL);
+}
+
+/* Printing functions */
+/* Feed the AS_PATH to the vty; the suffix string follows it only in case
+ * AS_PATH wasn't empty.
+ */
+void aspath_print_vty(struct vty *vty, const char *format, struct aspath *as,
+		      const char *suffix)
+{
+	assert(format);
+	vty_out(vty, format, as->str);
+	if (as->str_len && strlen(suffix))
+		vty_out(vty, "%s", suffix);
+}
+
+static void aspath_show_all_iterator(struct hash_bucket *bucket,
+				     struct vty *vty)
+{
+	struct aspath *as;
+
+	as = (struct aspath *)bucket->data;
+
+	vty_out(vty, "[%p:%u] (%ld) ", (void *)bucket, bucket->key, as->refcnt);
+	vty_out(vty, "%s\n", as->str);
+}
+
+/* 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_bucket *,
+				       void *))aspath_show_all_iterator,
+		     vty);
+}
+
+static struct aspath *bgp_aggr_aspath_lookup(struct bgp_aggregate *aggregate,
+					     struct aspath *aspath)
+{
+	return hash_lookup(aggregate->aspath_hash, aspath);
+}
+
+static void *bgp_aggr_aspath_hash_alloc(void *p)
+{
+	struct aspath *ref = (struct aspath *)p;
+	struct aspath *aspath = NULL;
+
+	aspath = aspath_dup(ref);
+	return aspath;
+}
+
+static void bgp_aggr_aspath_prepare(struct hash_bucket *hb, void *arg)
+{
+	struct aspath *hb_aspath = hb->data;
+	struct aspath **aggr_aspath = arg;
+
+	if (*aggr_aspath)
+		*aggr_aspath = aspath_aggregate(*aggr_aspath, hb_aspath);
+	else
+		*aggr_aspath = aspath_dup(hb_aspath);
+}
+
+void bgp_aggr_aspath_remove(void *arg)
+{
+	struct aspath *aspath = arg;
+
+	aspath_free(aspath);
+}
+
+void bgp_compute_aggregate_aspath(struct bgp_aggregate *aggregate,
+				  struct aspath *aspath)
+{
+	bgp_compute_aggregate_aspath_hash(aggregate, aspath);
+
+	bgp_compute_aggregate_aspath_val(aggregate);
+
+}
+
+void bgp_compute_aggregate_aspath_hash(struct bgp_aggregate *aggregate,
+				       struct aspath *aspath)
+{
+	struct aspath *aggr_aspath = NULL;
+
+	if ((aggregate == NULL) || (aspath == NULL))
+		return;
+
+	/* Create hash if not already created.
+	 */
+	if (aggregate->aspath_hash == NULL)
+		aggregate->aspath_hash = hash_create(
+					aspath_key_make, aspath_cmp,
+					"BGP Aggregator as-path hash");
+
+	aggr_aspath = bgp_aggr_aspath_lookup(aggregate, aspath);
+	if (aggr_aspath == NULL) {
+		/* Insert as-path into hash.
+		 */
+		aggr_aspath = hash_get(aggregate->aspath_hash, aspath,
+				       bgp_aggr_aspath_hash_alloc);
+	}
+
+	/* Increment reference counter.
+	 */
+	aggr_aspath->refcnt++;
+}
+
+void bgp_compute_aggregate_aspath_val(struct bgp_aggregate *aggregate)
+{
+	if (aggregate == NULL)
+		return;
+	/* Re-compute aggregate's as-path.
+	 */
+	if (aggregate->aspath) {
+		aspath_free(aggregate->aspath);
+		aggregate->aspath = NULL;
+	}
+	if (aggregate->aspath_hash
+	    && aggregate->aspath_hash->count) {
+		hash_iterate(aggregate->aspath_hash,
+			     bgp_aggr_aspath_prepare,
+			     &aggregate->aspath);
+	}
+}
+
+void bgp_remove_aspath_from_aggregate(struct bgp_aggregate *aggregate,
+				      struct aspath *aspath)
+{
+	struct aspath *aggr_aspath = NULL;
+	struct aspath *ret_aspath = NULL;
+
+	if ((!aggregate)
+	    || (!aggregate->aspath_hash)
+	    || (!aspath))
+		return;
+
+	/* Look-up the aspath in the hash.
+	 */
+	aggr_aspath = bgp_aggr_aspath_lookup(aggregate, aspath);
+	if (aggr_aspath) {
+		aggr_aspath->refcnt--;
+
+		if (aggr_aspath->refcnt == 0) {
+			ret_aspath = hash_release(aggregate->aspath_hash,
+						  aggr_aspath);
+			aspath_free(ret_aspath);
+			ret_aspath = NULL;
+
+			/* Remove aggregate's old as-path.
+			 */
+			aspath_free(aggregate->aspath);
+			aggregate->aspath = NULL;
+
+			bgp_compute_aggregate_aspath_val(aggregate);
+		}
+	}
+}
+
+void bgp_remove_aspath_from_aggregate_hash(struct bgp_aggregate *aggregate,
+					   struct aspath *aspath)
+{
+	struct aspath *aggr_aspath = NULL;
+	struct aspath *ret_aspath = NULL;
+
+	if ((!aggregate)
+	    || (!aggregate->aspath_hash)
+	    || (!aspath))
+		return;
+
+	/* Look-up the aspath in the hash.
+	 */
+	aggr_aspath = bgp_aggr_aspath_lookup(aggregate, aspath);
+	if (aggr_aspath) {
+		aggr_aspath->refcnt--;
+
+		if (aggr_aspath->refcnt == 0) {
+			ret_aspath = hash_release(aggregate->aspath_hash,
+						  aggr_aspath);
+			aspath_free(ret_aspath);
+			ret_aspath = NULL;
+		}
+	}
+}
+