bgp_mpath.c

/*
 * BGP Multipath
 * Copyright (C) 2010 Google Inc.
 *
 * This file is part of Quagga
 *
 * Quagga 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.
 *
 * Quagga 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 "command.h"
#include "prefix.h"
#include "linklist.h"
#include "sockunion.h"
#include "memory.h"
#include "queue.h"
#include "filter.h"

#include "bgpd/bgpd.h"
#include "bgpd/bgp_table.h"
#include "bgpd/bgp_route.h"
#include "bgpd/bgp_attr.h"
#include "bgpd/bgp_debug.h"
#include "bgpd/bgp_aspath.h"
#include "bgpd/bgp_community.h"
#include "bgpd/bgp_ecommunity.h"
#include "bgpd/bgp_lcommunity.h"
#include "bgpd/bgp_mpath.h"

/*
 * bgp_maximum_paths_set
 *
 * Record maximum-paths configuration for BGP instance
 */
int bgp_maximum_paths_set(struct bgp *bgp, afi_t afi, safi_t safi, int peertype,
			  u_int16_t maxpaths, u_int16_t options)
{
	if (!bgp || (afi >= AFI_MAX) || (safi >= SAFI_MAX))
		return -1;

	switch (peertype) {
	case BGP_PEER_IBGP:
		bgp->maxpaths[afi][safi].maxpaths_ibgp = maxpaths;
		bgp->maxpaths[afi][safi].ibgp_flags |= options;
		break;
	case BGP_PEER_EBGP:
		bgp->maxpaths[afi][safi].maxpaths_ebgp = maxpaths;
		break;
	default:
		return -1;
	}

	return 0;
}

/*
 * bgp_maximum_paths_unset
 *
 * Remove maximum-paths configuration from BGP instance
 */
int bgp_maximum_paths_unset(struct bgp *bgp, afi_t afi, safi_t safi,
			    int peertype)
{
	if (!bgp || (afi >= AFI_MAX) || (safi >= SAFI_MAX))
		return -1;

	switch (peertype) {
	case BGP_PEER_IBGP:
		bgp->maxpaths[afi][safi].maxpaths_ibgp = multipath_num;
		bgp->maxpaths[afi][safi].ibgp_flags = 0;
		break;
	case BGP_PEER_EBGP:
		bgp->maxpaths[afi][safi].maxpaths_ebgp = multipath_num;
		break;
	default:
		return -1;
	}

	return 0;
}

/*
 * bgp_info_nexthop_cmp
 *
 * Compare the nexthops of two paths. Return value is less than, equal to,
 * or greater than zero if bi1 is respectively less than, equal to,
 * or greater than bi2.
 */
int bgp_info_nexthop_cmp(struct bgp_info *bi1, struct bgp_info *bi2)
{
	int compare;

	compare = IPV4_ADDR_CMP(&bi1->attr->nexthop, &bi2->attr->nexthop);
	if (!compare) {
		if (bi1->attr->mp_nexthop_len == bi2->attr->mp_nexthop_len) {
			switch (bi1->attr->mp_nexthop_len) {
			case BGP_ATTR_NHLEN_IPV4:
			case BGP_ATTR_NHLEN_VPNV4:
				compare = IPV4_ADDR_CMP(
					&bi1->attr->mp_nexthop_global_in,
					&bi2->attr->mp_nexthop_global_in);
				break;
			case BGP_ATTR_NHLEN_IPV6_GLOBAL:
			case BGP_ATTR_NHLEN_VPNV6_GLOBAL:
				compare = IPV6_ADDR_CMP(
					&bi1->attr->mp_nexthop_global,
					&bi2->attr->mp_nexthop_global);
				break;
			case BGP_ATTR_NHLEN_IPV6_GLOBAL_AND_LL:
				compare = IPV6_ADDR_CMP(
					&bi1->attr->mp_nexthop_global,
					&bi2->attr->mp_nexthop_global);
				if (!compare)
					compare = IPV6_ADDR_CMP(
						&bi1->attr->mp_nexthop_local,
						&bi2->attr->mp_nexthop_local);
				break;
			}
		}

		/* This can happen if one IPv6 peer sends you global and
		 * link-local
		 * nexthops but another IPv6 peer only sends you global
		 */
		else if (bi1->attr->mp_nexthop_len == BGP_ATTR_NHLEN_IPV6_GLOBAL
			 || bi1->attr->mp_nexthop_len
				    == BGP_ATTR_NHLEN_IPV6_GLOBAL_AND_LL) {
			compare = IPV6_ADDR_CMP(&bi1->attr->mp_nexthop_global,
						&bi2->attr->mp_nexthop_global);
			if (!compare) {
				if (bi1->attr->mp_nexthop_len
				    < bi2->attr->mp_nexthop_len)
					compare = -1;
				else
					compare = 1;
			}
		}
	}

	return compare;
}

/*
 * bgp_info_mpath_cmp
 *
 * This function determines our multipath list ordering. By ordering
 * the list we can deterministically select which paths are included
 * in the multipath set. The ordering also helps in detecting changes
 * in the multipath selection so we can detect whether to send an
 * update to zebra.
 *
 * The order of paths is determined first by received nexthop, and then
 * by peer address if the nexthops are the same.
 */
static int bgp_info_mpath_cmp(void *val1, void *val2)
{
	struct bgp_info *bi1, *bi2;
	int compare;

	bi1 = val1;
	bi2 = val2;

	compare = bgp_info_nexthop_cmp(bi1, bi2);

	if (!compare) {
		if (!bi1->peer->su_remote && !bi2->peer->su_remote)
			compare = 0;
		else if (!bi1->peer->su_remote)
			compare = 1;
		else if (!bi2->peer->su_remote)
			compare = -1;
		else
			compare = sockunion_cmp(bi1->peer->su_remote,
						bi2->peer->su_remote);
	}

	return compare;
}

/*
 * bgp_mp_list_init
 *
 * Initialize the mp_list, which holds the list of multipaths
 * selected by bgp_best_selection
 */
void bgp_mp_list_init(struct list *mp_list)
{
	assert(mp_list);
	memset(mp_list, 0, sizeof(struct list));
	mp_list->cmp = bgp_info_mpath_cmp;
}

/*
 * bgp_mp_list_clear
 *
 * Clears all entries out of the mp_list
 */
void bgp_mp_list_clear(struct list *mp_list)
{
	assert(mp_list);
	list_delete_all_node(mp_list);
}

/*
 * bgp_mp_list_add
 *
 * Adds a multipath entry to the mp_list
 */
void bgp_mp_list_add(struct list *mp_list, struct bgp_info *mpinfo)
{
	assert(mp_list && mpinfo);
	listnode_add_sort(mp_list, mpinfo);
}

/*
 * bgp_info_mpath_new
 *
 * Allocate and zero memory for a new bgp_info_mpath element
 */
static struct bgp_info_mpath *bgp_info_mpath_new(void)
{
	struct bgp_info_mpath *new_mpath;
	new_mpath =
		XCALLOC(MTYPE_BGP_MPATH_INFO, sizeof(struct bgp_info_mpath));
	return new_mpath;
}

/*
 * bgp_info_mpath_free
 *
 * Release resources for a bgp_info_mpath element and zero out pointer
 */
void bgp_info_mpath_free(struct bgp_info_mpath **mpath)
{
	if (mpath && *mpath) {
		if ((*mpath)->mp_attr)
			bgp_attr_unintern(&(*mpath)->mp_attr);
		XFREE(MTYPE_BGP_MPATH_INFO, *mpath);
		*mpath = NULL;
	}
}

/*
 * bgp_info_mpath_get
 *
 * Fetch the mpath element for the given bgp_info. Used for
 * doing lazy allocation.
 */
static struct bgp_info_mpath *bgp_info_mpath_get(struct bgp_info *binfo)
{
	struct bgp_info_mpath *mpath;
	if (!binfo->mpath) {
		mpath = bgp_info_mpath_new();
		if (!mpath)
			return NULL;
		binfo->mpath = mpath;
		mpath->mp_info = binfo;
	}
	return binfo->mpath;
}

/*
 * bgp_info_mpath_enqueue
 *
 * Enqueue a path onto the multipath list given the previous multipath
 * list entry
 */
static void bgp_info_mpath_enqueue(struct bgp_info *prev_info,
				   struct bgp_info *binfo)
{
	struct bgp_info_mpath *prev, *mpath;

	prev = bgp_info_mpath_get(prev_info);
	mpath = bgp_info_mpath_get(binfo);
	if (!prev || !mpath)
		return;

	mpath->mp_next = prev->mp_next;
	mpath->mp_prev = prev;
	if (prev->mp_next)
		prev->mp_next->mp_prev = mpath;
	prev->mp_next = mpath;

	SET_FLAG(binfo->flags, BGP_INFO_MULTIPATH);
}

/*
 * bgp_info_mpath_dequeue
 *
 * Remove a path from the multipath list
 */
void bgp_info_mpath_dequeue(struct bgp_info *binfo)
{
	struct bgp_info_mpath *mpath = binfo->mpath;
	if (!mpath)
		return;
	if (mpath->mp_prev)
		mpath->mp_prev->mp_next = mpath->mp_next;
	if (mpath->mp_next)
		mpath->mp_next->mp_prev = mpath->mp_prev;
	mpath->mp_next = mpath->mp_prev = NULL;
	UNSET_FLAG(binfo->flags, BGP_INFO_MULTIPATH);
}

/*
 * bgp_info_mpath_next
 *
 * Given a bgp_info, return the next multipath entry
 */
struct bgp_info *bgp_info_mpath_next(struct bgp_info *binfo)
{
	if (!binfo->mpath || !binfo->mpath->mp_next)
		return NULL;
	return binfo->mpath->mp_next->mp_info;
}

/*
 * bgp_info_mpath_first
 *
 * Given bestpath bgp_info, return the first multipath entry.
 */
struct bgp_info *bgp_info_mpath_first(struct bgp_info *binfo)
{
	return bgp_info_mpath_next(binfo);
}

/*
 * bgp_info_mpath_count
 *
 * Given the bestpath bgp_info, return the number of multipath entries
 */
u_int32_t bgp_info_mpath_count(struct bgp_info *binfo)
{
	if (!binfo->mpath)
		return 0;
	return binfo->mpath->mp_count;
}

/*
 * bgp_info_mpath_count_set
 *
 * Sets the count of multipaths into bestpath's mpath element
 */
static void bgp_info_mpath_count_set(struct bgp_info *binfo, u_int32_t count)
{
	struct bgp_info_mpath *mpath;
	if (!count && !binfo->mpath)
		return;
	mpath = bgp_info_mpath_get(binfo);
	if (!mpath)
		return;
	mpath->mp_count = count;
}

/*
 * bgp_info_mpath_attr
 *
 * Given bestpath bgp_info, return aggregated attribute set used
 * for advertising the multipath route
 */
struct attr *bgp_info_mpath_attr(struct bgp_info *binfo)
{
	if (!binfo->mpath)
		return NULL;
	return binfo->mpath->mp_attr;
}

/*
 * bgp_info_mpath_attr_set
 *
 * Sets the aggregated attribute into bestpath's mpath element
 */
static void bgp_info_mpath_attr_set(struct bgp_info *binfo, struct attr *attr)
{
	struct bgp_info_mpath *mpath;
	if (!attr && !binfo->mpath)
		return;
	mpath = bgp_info_mpath_get(binfo);
	if (!mpath)
		return;
	mpath->mp_attr = attr;
}

/*
 * bgp_info_mpath_update
 *
 * Compare and sync up the multipath list with the mp_list generated by
 * bgp_best_selection
 */
void bgp_info_mpath_update(struct bgp_node *rn, struct bgp_info *new_best,
			   struct bgp_info *old_best, struct list *mp_list,
			   struct bgp_maxpaths_cfg *mpath_cfg)
{
	u_int16_t maxpaths, mpath_count, old_mpath_count;
	struct listnode *mp_node, *mp_next_node;
	struct bgp_info *cur_mpath, *new_mpath, *next_mpath, *prev_mpath;
	int mpath_changed, debug;
	char pfx_buf[PREFIX2STR_BUFFER], nh_buf[2][INET6_ADDRSTRLEN];
	char path_buf[PATH_ADDPATH_STR_BUFFER];

	mpath_changed = 0;
	maxpaths = multipath_num;
	mpath_count = 0;
	cur_mpath = NULL;
	old_mpath_count = 0;
	prev_mpath = new_best;
	mp_node = listhead(mp_list);
	debug = bgp_debug_bestpath(&rn->p);

	if (debug)
		prefix2str(&rn->p, pfx_buf, sizeof(pfx_buf));

	if (new_best) {
		mpath_count++;
		if (new_best != old_best)
			bgp_info_mpath_dequeue(new_best);
		maxpaths = (new_best->peer->sort == BGP_PEER_IBGP)
				   ? mpath_cfg->maxpaths_ibgp
				   : mpath_cfg->maxpaths_ebgp;
	}

	if (old_best) {
		cur_mpath = bgp_info_mpath_first(old_best);
		old_mpath_count = bgp_info_mpath_count(old_best);
		bgp_info_mpath_count_set(old_best, 0);
		bgp_info_mpath_dequeue(old_best);
	}

	if (debug)
		zlog_debug(
			"%s: starting mpath update, newbest %s num candidates %d old-mpath-count %d",
			pfx_buf, new_best ? new_best->peer->host : "NONE",
			listcount(mp_list), old_mpath_count);

	/*
	 * We perform an ordered walk through both lists in parallel.
	 * The reason for the ordered walk is that if there are paths
	 * that were previously multipaths and are still multipaths, the walk
	 * should encounter them in both lists at the same time. Otherwise
	 * there will be paths that are in one list or another, and we
	 * will deal with these separately.
	 *
	 * Note that new_best might be somewhere in the mp_list, so we need
	 * to skip over it
	 */
	while (mp_node || cur_mpath) {
		struct bgp_info *tmp_info;

		/*
		 * We can bail out of this loop if all existing paths on the
		 * multipath list have been visited (for cleanup purposes) and
		 * the maxpath requirement is fulfulled
		 */
		if (!cur_mpath && (mpath_count >= maxpaths))
			break;

		mp_next_node = mp_node ? listnextnode(mp_node) : NULL;
		next_mpath = cur_mpath ? bgp_info_mpath_next(cur_mpath) : NULL;
		tmp_info = mp_node ? listgetdata(mp_node) : NULL;

		if (debug)
			zlog_debug(
				"%s: comparing candidate %s with existing mpath %s",
				pfx_buf,
				tmp_info ? tmp_info->peer->host : "NONE",
				cur_mpath ? cur_mpath->peer->host : "NONE");

		/*
		 * If equal, the path was a multipath and is still a multipath.
		 * Insert onto new multipath list if maxpaths allows.
		 */
		if (mp_node && (listgetdata(mp_node) == cur_mpath)) {
			list_delete_node(mp_list, mp_node);
			bgp_info_mpath_dequeue(cur_mpath);
			if ((mpath_count < maxpaths)
			    && bgp_info_nexthop_cmp(prev_mpath, cur_mpath)) {
				bgp_info_mpath_enqueue(prev_mpath, cur_mpath);
				prev_mpath = cur_mpath;
				mpath_count++;
				if (debug) {
					bgp_info_path_with_addpath_rx_str(
						cur_mpath, path_buf);
					zlog_debug(
						"%s: %s is still multipath, cur count %d",
						pfx_buf, path_buf, mpath_count);
				}
			} else {
				mpath_changed = 1;
				if (debug) {
					bgp_info_path_with_addpath_rx_str(
						cur_mpath, path_buf);
					zlog_debug(
						"%s: remove mpath %s nexthop %s, cur count %d",
						pfx_buf, path_buf,
						inet_ntop(AF_INET,
							  &cur_mpath->attr
								   ->nexthop,
							  nh_buf[0],
							  sizeof(nh_buf[0])),
						mpath_count);
				}
			}
			mp_node = mp_next_node;
			cur_mpath = next_mpath;
			continue;
		}

		if (cur_mpath
		    && (!mp_node
			|| (bgp_info_mpath_cmp(cur_mpath, listgetdata(mp_node))
			    < 0))) {
			/*
			 * If here, we have an old multipath and either the
			 * mp_list
			 * is finished or the next mp_node points to a later
			 * multipath, so we need to purge this path from the
			 * multipath list
			 */
			bgp_info_mpath_dequeue(cur_mpath);
			mpath_changed = 1;
			if (debug) {
				bgp_info_path_with_addpath_rx_str(cur_mpath,
								  path_buf);
				zlog_debug(
					"%s: remove mpath %s nexthop %s, cur count %d",
					pfx_buf, path_buf,
					inet_ntop(AF_INET,
						  &cur_mpath->attr->nexthop,
						  nh_buf[0], sizeof(nh_buf[0])),
					mpath_count);
			}
			cur_mpath = next_mpath;
		} else {
			/*
			 * If here, we have a path on the mp_list that was not
			 * previously
			 * a multipath (due to non-equivalance or maxpaths
			 * exceeded),
			 * or the matching multipath is sorted later in the
			 * multipath
			 * list. Before we enqueue the path on the new multipath
			 * list,
			 * make sure its not on the old_best multipath list or
			 * referenced
			 * via next_mpath:
			 * - If next_mpath points to this new path, update
			 * next_mpath to
			 *   point to the multipath after this one
			 * - Dequeue the path from the multipath list just to
			 * make sure
			 */
			new_mpath = listgetdata(mp_node);
			list_delete_node(mp_list, mp_node);
			if ((mpath_count < maxpaths) && (new_mpath != new_best)
			    && bgp_info_nexthop_cmp(prev_mpath, new_mpath)) {
				if (new_mpath == next_mpath)
					bgp_info_mpath_next(new_mpath);
				bgp_info_mpath_dequeue(new_mpath);

				bgp_info_mpath_enqueue(prev_mpath, new_mpath);
				prev_mpath = new_mpath;
				mpath_changed = 1;
				mpath_count++;
				if (debug) {
					bgp_info_path_with_addpath_rx_str(
						new_mpath, path_buf);
					zlog_debug(
						"%s: add mpath %s nexthop %s, cur count %d",
						pfx_buf, path_buf,
						inet_ntop(AF_INET,
							  &new_mpath->attr
								   ->nexthop,
							  nh_buf[0],
							  sizeof(nh_buf[0])),
						mpath_count);
				}
			}
			mp_node = mp_next_node;
		}
	}

	if (new_best) {
		if (debug)
			zlog_debug(
				"%s: New mpath count (incl newbest) %d mpath-change %s",
				pfx_buf, mpath_count,
				mpath_changed ? "YES" : "NO");

		bgp_info_mpath_count_set(new_best, mpath_count - 1);
		if (mpath_changed
		    || (bgp_info_mpath_count(new_best) != old_mpath_count))
			SET_FLAG(new_best->flags, BGP_INFO_MULTIPATH_CHG);
	}
}

/*
 * bgp_mp_dmed_deselect
 *
 * Clean up multipath information for BGP_INFO_DMED_SELECTED path that
 * is not selected as best path
 */
void bgp_mp_dmed_deselect(struct bgp_info *dmed_best)
{
	struct bgp_info *mpinfo, *mpnext;

	if (!dmed_best)
		return;

	for (mpinfo = bgp_info_mpath_first(dmed_best); mpinfo;
	     mpinfo = mpnext) {
		mpnext = bgp_info_mpath_next(mpinfo);
		bgp_info_mpath_dequeue(mpinfo);
	}

	bgp_info_mpath_count_set(dmed_best, 0);
	UNSET_FLAG(dmed_best->flags, BGP_INFO_MULTIPATH_CHG);
	assert(bgp_info_mpath_first(dmed_best) == 0);
}

/*
 * bgp_info_mpath_aggregate_update
 *
 * Set the multipath aggregate attribute. We need to see if the
 * aggregate has changed and then set the ATTR_CHANGED flag on the
 * bestpath info so that a peer update will be generated. The
 * change is detected by generating the current attribute,
 * interning it, and then comparing the interned pointer with the
 * current value. We can skip this generate/compare step if there
 * is no change in multipath selection and no attribute change in
 * any multipath.
 */
void bgp_info_mpath_aggregate_update(struct bgp_info *new_best,
				     struct bgp_info *old_best)
{
	struct bgp_info *mpinfo;
	struct aspath *aspath;
	struct aspath *asmerge;
	struct attr *new_attr, *old_attr;
	u_char origin;
	struct community *community, *commerge;
	struct ecommunity *ecomm, *ecommerge;
	struct lcommunity *lcomm, *lcommerge;
	struct attr attr = {0};

	if (old_best && (old_best != new_best)
	    && (old_attr = bgp_info_mpath_attr(old_best))) {
		bgp_attr_unintern(&old_attr);
		bgp_info_mpath_attr_set(old_best, NULL);
	}

	if (!new_best)
		return;

	if (!bgp_info_mpath_count(new_best)) {
		if ((new_attr = bgp_info_mpath_attr(new_best))) {
			bgp_attr_unintern(&new_attr);
			bgp_info_mpath_attr_set(new_best, NULL);
			SET_FLAG(new_best->flags, BGP_INFO_ATTR_CHANGED);
		}
		return;
	}

	bgp_attr_dup(&attr, new_best->attr);

	if (new_best->peer && bgp_flag_check(new_best->peer->bgp,
					     BGP_FLAG_MULTIPATH_RELAX_AS_SET)) {

		/* aggregate attribute from multipath constituents */
		aspath = aspath_dup(attr.aspath);
		origin = attr.origin;
		community =
			attr.community ? community_dup(attr.community) : NULL;
		ecomm = (attr.ecommunity) ? ecommunity_dup(attr.ecommunity)
					  : NULL;
		lcomm = (attr.lcommunity) ? lcommunity_dup(attr.lcommunity)
					  : NULL;

		for (mpinfo = bgp_info_mpath_first(new_best); mpinfo;
		     mpinfo = bgp_info_mpath_next(mpinfo)) {
			asmerge =
				aspath_aggregate(aspath, mpinfo->attr->aspath);
			aspath_free(aspath);
			aspath = asmerge;

			if (origin < mpinfo->attr->origin)
				origin = mpinfo->attr->origin;

			if (mpinfo->attr->community) {
				if (community) {
					commerge = community_merge(
						community,
						mpinfo->attr->community);
					community =
						community_uniq_sort(commerge);
					community_free(commerge);
				} else
					community = community_dup(
						mpinfo->attr->community);
			}

			if (mpinfo->attr->ecommunity) {
				if (ecomm) {
					ecommerge = ecommunity_merge(
						ecomm,
						mpinfo->attr->ecommunity);
					ecomm = ecommunity_uniq_sort(ecommerge);
					ecommunity_free(&ecommerge);
				} else
					ecomm = ecommunity_dup(
						mpinfo->attr->ecommunity);
			}
			if (mpinfo->attr->lcommunity) {
				if (lcomm) {
					lcommerge = lcommunity_merge(
						lcomm,
						mpinfo->attr->lcommunity);
					lcomm = lcommunity_uniq_sort(lcommerge);
					lcommunity_free(&lcommerge);
				} else
					lcomm = lcommunity_dup(
						mpinfo->attr->lcommunity);
			}
		}

		attr.aspath = aspath;
		attr.origin = origin;
		if (community) {
			attr.community = community;
			attr.flag |= ATTR_FLAG_BIT(BGP_ATTR_COMMUNITIES);
		}
		if (ecomm) {
			attr.ecommunity = ecomm;
			attr.flag |= ATTR_FLAG_BIT(BGP_ATTR_EXT_COMMUNITIES);
		}

		/* Zap multipath attr nexthop so we set nexthop to self */
		attr.nexthop.s_addr = 0;
		memset(&attr.mp_nexthop_global, 0, sizeof(struct in6_addr));

		/* TODO: should we set ATOMIC_AGGREGATE and AGGREGATOR? */
	}

	new_attr = bgp_attr_intern(&attr);

	if (new_attr != bgp_info_mpath_attr(new_best)) {
		if ((old_attr = bgp_info_mpath_attr(new_best)))
			bgp_attr_unintern(&old_attr);
		bgp_info_mpath_attr_set(new_best, new_attr);
		SET_FLAG(new_best->flags, BGP_INFO_ATTR_CHANGED);
	} else
		bgp_attr_unintern(&new_attr);
}