[mirror_frr.git] / bgpd / bgp_lcommunity.c

/* BGP Large Communities Attribute
 *
 * Copyright (C) 2016 Keyur Patel <keyur@arrcus.com>
 *
 * This file is part of FRRouting (FRR).
 *
 * FRR 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.
 *
 * FRR 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 "prefix.h"
#include "command.h"
#include "filter.h"
#include "jhash.h"
#include "stream.h"

#include "bgpd/bgpd.h"
#include "bgpd/bgp_lcommunity.h"
#include "bgpd/bgp_community_alias.h"
#include "bgpd/bgp_aspath.h"

/* Hash of community attribute. */
static struct hash *lcomhash;

/* Allocate a new lcommunities.  */
static struct lcommunity *lcommunity_new(void)
{
	return XCALLOC(MTYPE_LCOMMUNITY, sizeof(struct lcommunity));
}

/* Allocate lcommunities.  */
void lcommunity_free(struct lcommunity **lcom)
{
	if (!(*lcom))
		return;

	XFREE(MTYPE_LCOMMUNITY_VAL, (*lcom)->val);
	XFREE(MTYPE_LCOMMUNITY_STR, (*lcom)->str);
	if ((*lcom)->json)
		json_object_free((*lcom)->json);
	XFREE(MTYPE_LCOMMUNITY, *lcom);
}

static void lcommunity_hash_free(struct lcommunity *lcom)
{
	lcommunity_free(&lcom);
}

/* Add a new Large Communities value to Large Communities
   Attribute structure.  When the value is already exists in the
   structure, we don't add the value.  Newly added value is sorted by
   numerical order.  When the value is added to the structure return 1
   else return 0.  */
static bool lcommunity_add_val(struct lcommunity *lcom,
			       struct lcommunity_val *lval)
{
	uint8_t *p;
	int ret;
	int c;

	/* When this is fist value, just add it.  */
	if (lcom->val == NULL) {
		lcom->size++;
		lcom->val = XMALLOC(MTYPE_LCOMMUNITY_VAL, lcom_length(lcom));
		memcpy(lcom->val, lval->val, LCOMMUNITY_SIZE);
		return true;
	}

	/* If the value already exists in the structure return 0.  */
	c = 0;
	for (p = lcom->val; c < lcom->size; p += LCOMMUNITY_SIZE, c++) {
		ret = memcmp(p, lval->val, LCOMMUNITY_SIZE);
		if (ret == 0)
			return false;
		if (ret > 0)
			break;
	}

	/* Add the value to the structure with numerical sorting.  */
	lcom->size++;
	lcom->val =
		XREALLOC(MTYPE_LCOMMUNITY_VAL, lcom->val, lcom_length(lcom));

	memmove(lcom->val + (c + 1) * LCOMMUNITY_SIZE,
		lcom->val + c * LCOMMUNITY_SIZE,
		(lcom->size - 1 - c) * LCOMMUNITY_SIZE);
	memcpy(lcom->val + c * LCOMMUNITY_SIZE, lval->val, LCOMMUNITY_SIZE);

	return true;
}

/* This function takes pointer to Large Communites structure then
   create a new Large Communities structure by uniq and sort each
   Large Communities value.  */
struct lcommunity *lcommunity_uniq_sort(struct lcommunity *lcom)
{
	int i;
	struct lcommunity *new;
	struct lcommunity_val *lval;

	if (!lcom)
		return NULL;

	new = lcommunity_new();

	for (i = 0; i < lcom->size; i++) {
		lval = (struct lcommunity_val *)(lcom->val
						 + (i * LCOMMUNITY_SIZE));
		lcommunity_add_val(new, lval);
	}
	return new;
}

/* Parse Large Communites Attribute in BGP packet.  */
struct lcommunity *lcommunity_parse(uint8_t *pnt, unsigned short length)
{
	struct lcommunity tmp;
	struct lcommunity *new;

	/* Length check.  */
	if (length % LCOMMUNITY_SIZE)
		return NULL;

	/* Prepare tmporary structure for making a new Large Communities
	   Attribute.  */
	tmp.size = length / LCOMMUNITY_SIZE;
	tmp.val = pnt;

	/* Create a new Large Communities Attribute by uniq and sort each
	   Large Communities value  */
	new = lcommunity_uniq_sort(&tmp);

	return lcommunity_intern(new);
}

/* Duplicate the Large Communities Attribute structure.  */
struct lcommunity *lcommunity_dup(struct lcommunity *lcom)
{
	struct lcommunity *new;

	new = lcommunity_new();
	new->size = lcom->size;
	if (new->size) {
		new->val = XMALLOC(MTYPE_LCOMMUNITY_VAL, lcom_length(lcom));
		memcpy(new->val, lcom->val, lcom_length(lcom));
	} else
		new->val = NULL;
	return new;
}

/* Merge two Large Communities Attribute structure.  */
struct lcommunity *lcommunity_merge(struct lcommunity *lcom1,
				    struct lcommunity *lcom2)
{
	lcom1->val = XREALLOC(MTYPE_LCOMMUNITY_VAL, lcom1->val,
			      lcom_length(lcom1) + lcom_length(lcom2));

	memcpy(lcom1->val + lcom_length(lcom1), lcom2->val, lcom_length(lcom2));
	lcom1->size += lcom2->size;

	return lcom1;
}

static void set_lcommunity_string(struct lcommunity *lcom, bool make_json,
				  bool translate_alias)
{
	int i;
	int len;
	char *str_buf;
	const uint8_t *pnt;
	uint32_t global, local1, local2;
	json_object *json_lcommunity_list = NULL;
	json_object *json_string = NULL;

	/* 3 32-bit integers, 2 colons, and a space */
#define LCOMMUNITY_STRLEN (10 * 3 + 2 + 1)

	if (!lcom)
		return;

	if (make_json) {
		lcom->json = json_object_new_object();
		json_lcommunity_list = json_object_new_array();
	}

	if (lcom->size == 0) {
		str_buf = XCALLOC(MTYPE_LCOMMUNITY_STR, 1);

		if (make_json) {
			json_object_string_add(lcom->json, "string", "");
			json_object_object_add(lcom->json, "list",
					       json_lcommunity_list);
		}

		lcom->str = str_buf;
		return;
	}

	/* 1 space + lcom->size lcom strings + null terminator */
	size_t str_buf_sz = BUFSIZ;
	str_buf = XCALLOC(MTYPE_LCOMMUNITY_STR, str_buf_sz);

	for (i = 0; i < lcom->size; i++) {
		if (i > 0)
			strlcat(str_buf, " ", str_buf_sz);

		pnt = lcom->val + (i * LCOMMUNITY_SIZE);
		pnt = ptr_get_be32(pnt, &global);
		pnt = ptr_get_be32(pnt, &local1);
		pnt = ptr_get_be32(pnt, &local2);
		(void)pnt;

		char lcsb[LCOMMUNITY_STRLEN + 1];

		snprintf(lcsb, sizeof(lcsb), "%u:%u:%u", global, local1,
			 local2);

		const char *com2alias =
			translate_alias ? bgp_community2alias(lcsb) : lcsb;

		len = strlcat(str_buf, com2alias, str_buf_sz);
		assert((unsigned int)len < str_buf_sz);

		if (make_json) {
			json_string = json_object_new_string(com2alias);
			json_object_array_add(json_lcommunity_list,
					      json_string);
		}
	}

	if (make_json) {
		json_object_string_add(lcom->json, "string", str_buf);
		json_object_object_add(lcom->json, "list",
				       json_lcommunity_list);
	}

	lcom->str = str_buf;
}

/* Intern Large Communities Attribute.  */
struct lcommunity *lcommunity_intern(struct lcommunity *lcom)
{
	struct lcommunity *find;

	assert(lcom->refcnt == 0);

	find = (struct lcommunity *)hash_get(lcomhash, lcom, hash_alloc_intern);

	if (find != lcom)
		lcommunity_free(&lcom);

	find->refcnt++;

	if (!find->str)
		set_lcommunity_string(find, false, true);

	return find;
}

/* Unintern Large Communities Attribute.  */
void lcommunity_unintern(struct lcommunity **lcom)
{
	struct lcommunity *ret;

	if (!*lcom)
		return;

	if ((*lcom)->refcnt)
		(*lcom)->refcnt--;

	/* Pull off from hash.  */
	if ((*lcom)->refcnt == 0) {
		/* Large community must be in the hash.  */
		ret = (struct lcommunity *)hash_release(lcomhash, *lcom);
		assert(ret != NULL);

		lcommunity_free(lcom);
	}
}

/* Return string representation of lcommunities attribute. */
char *lcommunity_str(struct lcommunity *lcom, bool make_json,
		     bool translate_alias)
{
	if (!lcom)
		return NULL;

	if (make_json && !lcom->json && lcom->str)
		XFREE(MTYPE_LCOMMUNITY_STR, lcom->str);

	if (!lcom->str)
		set_lcommunity_string(lcom, make_json, translate_alias);

	return lcom->str;
}

/* Utility function to make hash key.  */
unsigned int lcommunity_hash_make(const void *arg)
{
	const struct lcommunity *lcom = arg;
	int size = lcom_length(lcom);

	return jhash(lcom->val, size, 0xab125423);
}

/* Compare two Large Communities Attribute structure.  */
bool lcommunity_cmp(const void *arg1, const void *arg2)
{
	const struct lcommunity *lcom1 = arg1;
	const struct lcommunity *lcom2 = arg2;

	if (lcom1 == NULL && lcom2 == NULL)
		return true;

	if (lcom1 == NULL || lcom2 == NULL)
		return false;

	return (lcom1->size == lcom2->size
		&& memcmp(lcom1->val, lcom2->val, lcom_length(lcom1)) == 0);
}

/* Return communities hash.  */
struct hash *lcommunity_hash(void)
{
	return lcomhash;
}

/* Initialize Large Comminities related hash. */
void lcommunity_init(void)
{
	lcomhash = hash_create(lcommunity_hash_make, lcommunity_cmp,
			       "BGP lcommunity hash");
}

void lcommunity_finish(void)
{
	hash_clean(lcomhash, (void (*)(void *))lcommunity_hash_free);
	hash_free(lcomhash);
	lcomhash = NULL;
}

/* Get next Large Communities token from the string.
 * Assumes str is space-delimeted and describes 0 or more
 * valid large communities
 */
static const char *lcommunity_gettoken(const char *str,
				       struct lcommunity_val *lval)
{
	const char *p = str;

	/* Skip white space. */
	while (isspace((unsigned char)*p)) {
		p++;
		str++;
	}

	/* Check the end of the line. */
	if (*p == '\0')
		return NULL;

	/* Community value. */
	int separator = 0;
	int digit = 0;
	uint32_t globaladmin = 0;
	uint32_t localdata1 = 0;
	uint32_t localdata2 = 0;

	while (*p && *p != ' ') {
		/* large community valid chars */
		assert(isdigit((unsigned char)*p) || *p == ':');

		if (*p == ':') {
			separator++;
			digit = 0;
			if (separator == 1) {
				globaladmin = localdata2;
			} else {
				localdata1 = localdata2;
			}
			localdata2 = 0;
		} else {
			digit = 1;
			/* left shift the accumulated value and add current
			 * digit
			 */
			localdata2 *= 10;
			localdata2 += (*p - '0');
		}
		p++;
	}

	/* Assert str was a valid large community */
	assert(separator == 2 && digit == 1);

	/*
	 * Copy the large comm.
	 */
	lval->val[0] = (globaladmin >> 24) & 0xff;
	lval->val[1] = (globaladmin >> 16) & 0xff;
	lval->val[2] = (globaladmin >> 8) & 0xff;
	lval->val[3] = globaladmin & 0xff;
	lval->val[4] = (localdata1 >> 24) & 0xff;
	lval->val[5] = (localdata1 >> 16) & 0xff;
	lval->val[6] = (localdata1 >> 8) & 0xff;
	lval->val[7] = localdata1 & 0xff;
	lval->val[8] = (localdata2 >> 24) & 0xff;
	lval->val[9] = (localdata2 >> 16) & 0xff;
	lval->val[10] = (localdata2 >> 8) & 0xff;
	lval->val[11] = localdata2 & 0xff;

	return p;
}

/*
  Convert string to large community attribute.
  When type is already known, please specify both str and type.

  When string includes keyword for each large community value.
  Please specify keyword_included as non-zero value.
*/
struct lcommunity *lcommunity_str2com(const char *str)
{
	struct lcommunity *lcom = NULL;
	struct lcommunity_val lval;

	if (!lcommunity_list_valid(str, LARGE_COMMUNITY_LIST_STANDARD))
		return NULL;

	do {
		str = lcommunity_gettoken(str, &lval);
		if (lcom == NULL)
			lcom = lcommunity_new();
		lcommunity_add_val(lcom, &lval);
	} while (str);

	return lcom;
}

bool lcommunity_include(struct lcommunity *lcom, uint8_t *ptr)
{
	int i;
	uint8_t *lcom_ptr;

	for (i = 0; i < lcom->size; i++) {
		lcom_ptr = lcom->val + (i * LCOMMUNITY_SIZE);
		if (memcmp(ptr, lcom_ptr, LCOMMUNITY_SIZE) == 0)
			return true;
	}
	return false;
}

bool lcommunity_match(const struct lcommunity *lcom1,
		      const struct lcommunity *lcom2)
{
	int i = 0;
	int j = 0;

	if (lcom1 == NULL && lcom2 == NULL)
		return true;

	if (lcom1 == NULL || lcom2 == NULL)
		return false;

	if (lcom1->size < lcom2->size)
		return false;

	/* Every community on com2 needs to be on com1 for this to match */
	while (i < lcom1->size && j < lcom2->size) {
		if (memcmp(lcom1->val + (i * LCOMMUNITY_SIZE),
			   lcom2->val + (j * LCOMMUNITY_SIZE), LCOMMUNITY_SIZE)
		    == 0)
			j++;
		i++;
	}

	if (j == lcom2->size)
		return true;
	else
		return false;
}

/* Delete one lcommunity. */
void lcommunity_del_val(struct lcommunity *lcom, uint8_t *ptr)
{
	int i = 0;
	int c = 0;

	if (!lcom->val)
		return;

	while (i < lcom->size) {
		if (memcmp(lcom->val + i * LCOMMUNITY_SIZE, ptr,
			   LCOMMUNITY_SIZE)
		    == 0) {
			c = lcom->size - i - 1;

			if (c > 0)
				memmove(lcom->val + i * LCOMMUNITY_SIZE,
					lcom->val + (i + 1) * LCOMMUNITY_SIZE,
					c * LCOMMUNITY_SIZE);

			lcom->size--;

			if (lcom->size > 0)
				lcom->val =
					XREALLOC(MTYPE_LCOMMUNITY_VAL,
						 lcom->val, lcom_length(lcom));
			else {
				XFREE(MTYPE_LCOMMUNITY_VAL, lcom->val);
			}
			return;
		}
		i++;
	}
}

static struct lcommunity *bgp_aggr_lcommunity_lookup(
						struct bgp_aggregate *aggregate,
						struct lcommunity *lcommunity)
{
	return hash_lookup(aggregate->lcommunity_hash, lcommunity);
}

static void *bgp_aggr_lcommunty_hash_alloc(void *p)
{
	struct lcommunity *ref = (struct lcommunity *)p;
	struct lcommunity *lcommunity = NULL;

	lcommunity = lcommunity_dup(ref);
	return lcommunity;
}

static void bgp_aggr_lcommunity_prepare(struct hash_bucket *hb, void *arg)
{
	struct lcommunity *hb_lcommunity = hb->data;
	struct lcommunity **aggr_lcommunity = arg;

	if (*aggr_lcommunity)
		*aggr_lcommunity = lcommunity_merge(*aggr_lcommunity,
						    hb_lcommunity);
	else
		*aggr_lcommunity = lcommunity_dup(hb_lcommunity);
}

void bgp_aggr_lcommunity_remove(void *arg)
{
	struct lcommunity *lcommunity = arg;

	lcommunity_free(&lcommunity);
}

void bgp_compute_aggregate_lcommunity(struct bgp_aggregate *aggregate,
				      struct lcommunity *lcommunity)
{

	bgp_compute_aggregate_lcommunity_hash(aggregate, lcommunity);
	bgp_compute_aggregate_lcommunity_val(aggregate);
}

void bgp_compute_aggregate_lcommunity_hash(struct bgp_aggregate *aggregate,
					   struct lcommunity *lcommunity)
{

	struct lcommunity *aggr_lcommunity = NULL;

	if ((aggregate == NULL) || (lcommunity == NULL))
		return;

	/* Create hash if not already created.
	 */
	if (aggregate->lcommunity_hash == NULL)
		aggregate->lcommunity_hash = hash_create(
					lcommunity_hash_make, lcommunity_cmp,
					"BGP Aggregator lcommunity hash");

	aggr_lcommunity = bgp_aggr_lcommunity_lookup(aggregate, lcommunity);
	if (aggr_lcommunity == NULL) {
		/* Insert lcommunity into hash.
		 */
		aggr_lcommunity = hash_get(aggregate->lcommunity_hash,
					   lcommunity,
					   bgp_aggr_lcommunty_hash_alloc);
	}

	/* Increment reference counter.
	 */
	aggr_lcommunity->refcnt++;
}

void bgp_compute_aggregate_lcommunity_val(struct bgp_aggregate *aggregate)
{
	struct lcommunity *lcommerge = NULL;

	if (aggregate == NULL)
		return;

	/* Re-compute aggregate's lcommunity.
	 */
	if (aggregate->lcommunity)
		lcommunity_free(&aggregate->lcommunity);
	if (aggregate->lcommunity_hash &&
	    aggregate->lcommunity_hash->count) {
		hash_iterate(aggregate->lcommunity_hash,
			     bgp_aggr_lcommunity_prepare,
			     &aggregate->lcommunity);
		lcommerge = aggregate->lcommunity;
		aggregate->lcommunity = lcommunity_uniq_sort(lcommerge);
		if (lcommerge)
			lcommunity_free(&lcommerge);
	}
}

void bgp_remove_lcommunity_from_aggregate(struct bgp_aggregate *aggregate,
					  struct lcommunity *lcommunity)
{
	struct lcommunity *aggr_lcommunity = NULL;
	struct lcommunity *ret_lcomm = NULL;

	if ((!aggregate)
	    || (!aggregate->lcommunity_hash)
	    || (!lcommunity))
		return;

	/* Look-up the lcommunity in the hash.
	 */
	aggr_lcommunity = bgp_aggr_lcommunity_lookup(aggregate, lcommunity);
	if (aggr_lcommunity) {
		aggr_lcommunity->refcnt--;

		if (aggr_lcommunity->refcnt == 0) {
			ret_lcomm = hash_release(aggregate->lcommunity_hash,
						 aggr_lcommunity);
			lcommunity_free(&ret_lcomm);

			bgp_compute_aggregate_lcommunity_val(aggregate);

		}
	}
}

void bgp_remove_lcomm_from_aggregate_hash(struct bgp_aggregate *aggregate,
					  struct lcommunity *lcommunity)
{
	struct lcommunity *aggr_lcommunity = NULL;
	struct lcommunity *ret_lcomm = NULL;

	if ((!aggregate)
	    || (!aggregate->lcommunity_hash)
	    || (!lcommunity))
		return;

	/* Look-up the lcommunity in the hash.
	 */
	aggr_lcommunity = bgp_aggr_lcommunity_lookup(aggregate, lcommunity);
	if (aggr_lcommunity) {
		aggr_lcommunity->refcnt--;

		if (aggr_lcommunity->refcnt == 0) {
			ret_lcomm = hash_release(aggregate->lcommunity_hash,
						 aggr_lcommunity);
			lcommunity_free(&ret_lcomm);
		}
	}
}
Commit	Line	Data
57d187bc	1	/* BGP Large Communities Attribute
2acb4ac2 DL	2	*
	3	* Copyright (C) 2016 Keyur Patel <keyur@arrcus.com>
	4	*
8678d638	5	* This file is part of FRRouting (FRR).
2acb4ac2 DL	6	*
	7	* FRR is free software; you can redistribute it and/or modify it under the
	8	* terms of the GNU General Public License as published by the Free Software
	9	* Foundation; either version 2, or (at your option) any later version.
	10	*
	11	* FRR is distributed in the hope that it will be useful, but WITHOUT ANY
	12	* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
	13	* FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
	14	* details.
	15	*
	16	* You should have received a copy of the GNU General Public License along
896014f4 DL	17	* with this program; see the file COPYING; if not, write to the Free Software
896014f4 DL	18	* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
2acb4ac2	19	*/
57d187bc JS	20
	21	#include <zebra.h>
	22
	23	#include "hash.h"
	24	#include "memory.h"
	25	#include "prefix.h"
	26	#include "command.h"
	27	#include "filter.h"
3f65c5b1	28	#include "jhash.h"
937652c6	29	#include "stream.h"
57d187bc JS	30
	31	#include "bgpd/bgpd.h"
	32	#include "bgpd/bgp_lcommunity.h"
ed0e57e3	33	#include "bgpd/bgp_community_alias.h"
57d187bc JS	34	#include "bgpd/bgp_aspath.h"
	35
	36	/* Hash of community attribute. */
	37	static struct hash *lcomhash;
	38
	39	/* Allocate a new lcommunities. */
d62a17ae	40	static struct lcommunity *lcommunity_new(void)
57d187bc	41	{
9f5dc319	42	return XCALLOC(MTYPE_LCOMMUNITY, sizeof(struct lcommunity));
57d187bc JS	43	}
	44
	45	/* Allocate lcommunities. */
d62a17ae	46	void lcommunity_free(struct lcommunity **lcom)
57d187bc	47	{
2c15754e JC	48	if (!(*lcom))
	49	return;
	50
0a22ddfb QY	51	XFREE(MTYPE_LCOMMUNITY_VAL, (*lcom)->val);
0a22ddfb QY	52	XFREE(MTYPE_LCOMMUNITY_STR, (*lcom)->str);
74a630b6 NT	53	if ((*lcom)->json)
74a630b6 NT	54	json_object_free((*lcom)->json);
d62a17ae	55	XFREE(MTYPE_LCOMMUNITY, *lcom);
57d187bc JS	56	}
57d187bc JS	57
d62a17ae	58	static void lcommunity_hash_free(struct lcommunity *lcom)
47350fd9	59	{
d62a17ae	60	lcommunity_free(&lcom);
47350fd9 DS	61	}
47350fd9 DS	62
57d187bc JS	63	/* Add a new Large Communities value to Large Communities
	64	Attribute structure. When the value is already exists in the
	65	structure, we don't add the value. Newly added value is sorted by
	66	numerical order. When the value is added to the structure return 1
	67	else return 0. */
3dc339cd DA	68	static bool lcommunity_add_val(struct lcommunity *lcom,
3dc339cd DA	69	struct lcommunity_val *lval)
57d187bc	70	{
d7c0a89a	71	uint8_t *p;
d62a17ae	72	int ret;
	73	int c;
	74
	75	/* When this is fist value, just add it. */
	76	if (lcom->val == NULL) {
	77	lcom->size++;
	78	lcom->val = XMALLOC(MTYPE_LCOMMUNITY_VAL, lcom_length(lcom));
	79	memcpy(lcom->val, lval->val, LCOMMUNITY_SIZE);
3dc339cd	80	return true;
d62a17ae	81	}
	82
	83	/* If the value already exists in the structure return 0. */
	84	c = 0;
	85	for (p = lcom->val; c < lcom->size; p += LCOMMUNITY_SIZE, c++) {
	86	ret = memcmp(p, lval->val, LCOMMUNITY_SIZE);
	87	if (ret == 0)
3dc339cd	88	return false;
d62a17ae	89	if (ret > 0)
	90	break;
	91	}
	92
	93	/* Add the value to the structure with numerical sorting. */
	94	lcom->size++;
	95	lcom->val =
	96	XREALLOC(MTYPE_LCOMMUNITY_VAL, lcom->val, lcom_length(lcom));
	97
	98	memmove(lcom->val + (c + 1) * LCOMMUNITY_SIZE,
	99	lcom->val + c * LCOMMUNITY_SIZE,
	100	(lcom->size - 1 - c) * LCOMMUNITY_SIZE);
	101	memcpy(lcom->val + c * LCOMMUNITY_SIZE, lval->val, LCOMMUNITY_SIZE);
	102
3dc339cd	103	return true;
57d187bc JS	104	}
57d187bc JS	105
544be979	106	/* This function takes pointer to Large Communites structure then
57d187bc JS	107	create a new Large Communities structure by uniq and sort each
57d187bc JS	108	Large Communities value. */
d62a17ae	109	struct lcommunity lcommunity_uniq_sort(struct lcommunity lcom)
57d187bc	110	{
d62a17ae	111	int i;
	112	struct lcommunity *new;
	113	struct lcommunity_val *lval;
57d187bc	114
d62a17ae	115	if (!lcom)
d62a17ae	116	return NULL;
57d187bc	117
d62a17ae	118	new = lcommunity_new();
57d187bc	119
d62a17ae	120	for (i = 0; i < lcom->size; i++) {
	121	lval = (struct lcommunity_val *)(lcom->val
	122	+ (i * LCOMMUNITY_SIZE));
	123	lcommunity_add_val(new, lval);
	124	}
	125	return new;
57d187bc JS	126	}
	127
	128	/* Parse Large Communites Attribute in BGP packet. */
d7c0a89a	129	struct lcommunity lcommunity_parse(uint8_t pnt, unsigned short length)
57d187bc	130	{
d62a17ae	131	struct lcommunity tmp;
d62a17ae	132	struct lcommunity *new;
57d187bc	133
d62a17ae	134	/* Length check. */
	135	if (length % LCOMMUNITY_SIZE)
	136	return NULL;
57d187bc	137
d62a17ae	138	/* Prepare tmporary structure for making a new Large Communities
	139	Attribute. */
	140	tmp.size = length / LCOMMUNITY_SIZE;
	141	tmp.val = pnt;
57d187bc	142
d62a17ae	143	/* Create a new Large Communities Attribute by uniq and sort each
	144	Large Communities value */
	145	new = lcommunity_uniq_sort(&tmp);
57d187bc	146
d62a17ae	147	return lcommunity_intern(new);
57d187bc JS	148	}
	149
	150	/* Duplicate the Large Communities Attribute structure. */
d62a17ae	151	struct lcommunity lcommunity_dup(struct lcommunity lcom)
57d187bc	152	{
d62a17ae	153	struct lcommunity *new;
d62a17ae	154
cb0c2da3	155	new = lcommunity_new();
d62a17ae	156	new->size = lcom->size;
d62a17ae	157	if (new->size) {
79dab4b7 NK	158	new->val = XMALLOC(MTYPE_LCOMMUNITY_VAL, lcom_length(lcom));
79dab4b7 NK	159	memcpy(new->val, lcom->val, lcom_length(lcom));
d62a17ae	160	} else
	161	new->val = NULL;
	162	return new;
57d187bc JS	163	}
57d187bc JS	164
57d187bc	165	/* Merge two Large Communities Attribute structure. */
d62a17ae	166	struct lcommunity lcommunity_merge(struct lcommunity lcom1,
d62a17ae	167	struct lcommunity *lcom2)
57d187bc	168	{
0b04fa0e DS	169	lcom1->val = XREALLOC(MTYPE_LCOMMUNITY_VAL, lcom1->val,
0b04fa0e DS	170	lcom_length(lcom1) + lcom_length(lcom2));
d62a17ae	171
79dab4b7	172	memcpy(lcom1->val + lcom_length(lcom1), lcom2->val, lcom_length(lcom2));
d62a17ae	173	lcom1->size += lcom2->size;
	174
	175	return lcom1;
57d187bc JS	176	}
57d187bc JS	177
c0945b78 DA	178	static void set_lcommunity_string(struct lcommunity *lcom, bool make_json,
c0945b78 DA	179	bool translate_alias)
8d9b8ed9 PM	180	{
	181	int i;
	182	int len;
8d9b8ed9	183	char *str_buf;
1be1693e	184	const uint8_t *pnt;
8d9b8ed9 PM	185	uint32_t global, local1, local2;
	186	json_object *json_lcommunity_list = NULL;
	187	json_object *json_string = NULL;
	188
73bfd76d QY	189	/* 3 32-bit integers, 2 colons, and a space */
73bfd76d QY	190	#define LCOMMUNITY_STRLEN (10 * 3 + 2 + 1)
8d9b8ed9 PM	191
	192	if (!lcom)
	193	return;
	194
	195	if (make_json) {
	196	lcom->json = json_object_new_object();
	197	json_lcommunity_list = json_object_new_array();
	198	}
	199
	200	if (lcom->size == 0) {
73bfd76d	201	str_buf = XCALLOC(MTYPE_LCOMMUNITY_STR, 1);
8d9b8ed9 PM	202
	203	if (make_json) {
	204	json_object_string_add(lcom->json, "string", "");
	205	json_object_object_add(lcom->json, "list",
	206	json_lcommunity_list);
	207	}
	208
	209	lcom->str = str_buf;
	210	return;
	211	}
	212
73bfd76d	213	/* 1 space + lcom->size lcom strings + null terminator */
ed0e57e3	214	size_t str_buf_sz = BUFSIZ;
73bfd76d	215	str_buf = XCALLOC(MTYPE_LCOMMUNITY_STR, str_buf_sz);
8d9b8ed9 PM	216
8d9b8ed9 PM	217	for (i = 0; i < lcom->size; i++) {
73bfd76d QY	218	if (i > 0)
73bfd76d QY	219	strlcat(str_buf, " ", str_buf_sz);
8d9b8ed9 PM	220
	221	pnt = lcom->val + (i * LCOMMUNITY_SIZE);
	222	pnt = ptr_get_be32(pnt, &global);
	223	pnt = ptr_get_be32(pnt, &local1);
	224	pnt = ptr_get_be32(pnt, &local2);
	225	(void)pnt;
	226
73bfd76d QY	227	char lcsb[LCOMMUNITY_STRLEN + 1];
	228
	229	snprintf(lcsb, sizeof(lcsb), "%u:%u:%u", global, local1,
	230	local2);
	231
c0945b78 DA	232	const char *com2alias =
c0945b78 DA	233	translate_alias ? bgp_community2alias(lcsb) : lcsb;
d95a84e0 DA	234
d95a84e0 DA	235	len = strlcat(str_buf, com2alias, str_buf_sz);
73bfd76d QY	236	assert((unsigned int)len < str_buf_sz);
73bfd76d QY	237
8d9b8ed9	238	if (make_json) {
d95a84e0	239	json_string = json_object_new_string(com2alias);
8d9b8ed9 PM	240	json_object_array_add(json_lcommunity_list,
	241	json_string);
	242	}
8d9b8ed9 PM	243	}
8d9b8ed9 PM	244
8d9b8ed9 PM	245	if (make_json) {
	246	json_object_string_add(lcom->json, "string", str_buf);
	247	json_object_object_add(lcom->json, "list",
	248	json_lcommunity_list);
	249	}
	250
	251	lcom->str = str_buf;
	252	}
	253
57d187bc	254	/* Intern Large Communities Attribute. */
d62a17ae	255	struct lcommunity lcommunity_intern(struct lcommunity lcom)
57d187bc	256	{
d62a17ae	257	struct lcommunity *find;
57d187bc	258
d62a17ae	259	assert(lcom->refcnt == 0);
57d187bc	260
d62a17ae	261	find = (struct lcommunity *)hash_get(lcomhash, lcom, hash_alloc_intern);
57d187bc	262
d62a17ae	263	if (find != lcom)
d62a17ae	264	lcommunity_free(&lcom);
57d187bc	265
d62a17ae	266	find->refcnt++;
57d187bc	267
d62a17ae	268	if (!find->str)
c0945b78	269	set_lcommunity_string(find, false, true);
57d187bc	270
d62a17ae	271	return find;
57d187bc JS	272	}
	273
	274	/* Unintern Large Communities Attribute. */
d62a17ae	275	void lcommunity_unintern(struct lcommunity **lcom)
57d187bc	276	{
d62a17ae	277	struct lcommunity *ret;
57d187bc	278
1bcf3a96 DA	279	if (!*lcom)
	280	return;
	281
d62a17ae	282	if ((*lcom)->refcnt)
d62a17ae	283	(*lcom)->refcnt--;
57d187bc	284
d62a17ae	285	/* Pull off from hash. */
	286	if ((*lcom)->refcnt == 0) {
	287	/* Large community must be in the hash. */
	288	ret = (struct lcommunity )hash_release(lcomhash, lcom);
	289	assert(ret != NULL);
57d187bc	290
d62a17ae	291	lcommunity_free(lcom);
d62a17ae	292	}
57d187bc JS	293	}
57d187bc JS	294
639caccf	295	/* Return string representation of lcommunities attribute. */
c0945b78 DA	296	char lcommunity_str(struct lcommunity lcom, bool make_json,
c0945b78 DA	297	bool translate_alias)
8d9b8ed9 PM	298	{
	299	if (!lcom)
	300	return NULL;
	301
	302	if (make_json && !lcom->json && lcom->str)
	303	XFREE(MTYPE_LCOMMUNITY_STR, lcom->str);
	304
	305	if (!lcom->str)
c0945b78	306	set_lcommunity_string(lcom, make_json, translate_alias);
8d9b8ed9 PM	307
	308	return lcom->str;
	309	}
	310
57d187bc	311	/* Utility function to make hash key. */
d8b87afe	312	unsigned int lcommunity_hash_make(const void *arg)
57d187bc	313	{
d62a17ae	314	const struct lcommunity *lcom = arg;
79dab4b7	315	int size = lcom_length(lcom);
d62a17ae	316
3f65c5b1	317	return jhash(lcom->val, size, 0xab125423);
57d187bc JS	318	}
	319
	320	/* Compare two Large Communities Attribute structure. */
74df8d6d	321	bool lcommunity_cmp(const void arg1, const void arg2)
57d187bc	322	{
d62a17ae	323	const struct lcommunity *lcom1 = arg1;
d62a17ae	324	const struct lcommunity *lcom2 = arg2;
57d187bc	325
fbcdff82	326	if (lcom1 == NULL && lcom2 == NULL)
b08047f8	327	return true;
fbcdff82 RW	328
fbcdff82 RW	329	if (lcom1 == NULL \|\| lcom2 == NULL)
b08047f8	330	return false;
fbcdff82	331
d62a17ae	332	return (lcom1->size == lcom2->size
996c9314	333	&& memcmp(lcom1->val, lcom2->val, lcom_length(lcom1)) == 0);
57d187bc JS	334	}
	335
	336	/* Return communities hash. */
d62a17ae	337	struct hash *lcommunity_hash(void)
57d187bc	338	{
d62a17ae	339	return lcomhash;
57d187bc JS	340	}
	341
	342	/* Initialize Large Comminities related hash. */
d62a17ae	343	void lcommunity_init(void)
57d187bc	344	{
996c9314	345	lcomhash = hash_create(lcommunity_hash_make, lcommunity_cmp,
3f65c5b1	346	"BGP lcommunity hash");
57d187bc JS	347	}
57d187bc JS	348
d62a17ae	349	void lcommunity_finish(void)
57d187bc	350	{
d62a17ae	351	hash_clean(lcomhash, (void ()(void ))lcommunity_hash_free);
	352	hash_free(lcomhash);
	353	lcomhash = NULL;
57d187bc JS	354	}
57d187bc JS	355
c850908b WC	356	/* Get next Large Communities token from the string.
	357	* Assumes str is space-delimeted and describes 0 or more
	358	* valid large communities
	359	*/
d62a17ae	360	static const char lcommunity_gettoken(const char str,
c850908b	361	struct lcommunity_val *lval)
57d187bc	362	{
d62a17ae	363	const char *p = str;
	364
	365	/* Skip white space. */
fefa5e0f	366	while (isspace((unsigned char)*p)) {
d62a17ae	367	p++;
	368	str++;
	369	}
	370
	371	/* Check the end of the line. */
	372	if (*p == '\0')
	373	return NULL;
	374
	375	/* Community value. */
c850908b WC	376	int separator = 0;
	377	int digit = 0;
	378	uint32_t globaladmin = 0;
	379	uint32_t localdata1 = 0;
	380	uint32_t localdata2 = 0;
	381
	382	while (p && p != ' ') {
	383	/* large community valid chars */
	384	assert(isdigit((unsigned char)p) \|\| p == ':');
	385
	386	if (*p == ':') {
	387	separator++;
	388	digit = 0;
	389	if (separator == 1) {
	390	globaladmin = localdata2;
d62a17ae	391	} else {
c850908b	392	localdata1 = localdata2;
d62a17ae	393	}
c850908b WC	394	localdata2 = 0;
	395	} else {
	396	digit = 1;
	397	/* left shift the accumulated value and add current
	398	* digit
	399	*/
	400	localdata2 *= 10;
	401	localdata2 += (*p - '0');
57d187bc	402	}
c850908b	403	p++;
d62a17ae	404	}
c850908b WC	405
	406	/* Assert str was a valid large community */
	407	assert(separator == 2 && digit == 1);
	408
	409	/*
	410	* Copy the large comm.
	411	*/
	412	lval->val[0] = (globaladmin >> 24) & 0xff;
	413	lval->val[1] = (globaladmin >> 16) & 0xff;
	414	lval->val[2] = (globaladmin >> 8) & 0xff;
	415	lval->val[3] = globaladmin & 0xff;
	416	lval->val[4] = (localdata1 >> 24) & 0xff;
	417	lval->val[5] = (localdata1 >> 16) & 0xff;
	418	lval->val[6] = (localdata1 >> 8) & 0xff;
	419	lval->val[7] = localdata1 & 0xff;
	420	lval->val[8] = (localdata2 >> 24) & 0xff;
	421	lval->val[9] = (localdata2 >> 16) & 0xff;
	422	lval->val[10] = (localdata2 >> 8) & 0xff;
	423	lval->val[11] = localdata2 & 0xff;
	424
d62a17ae	425	return p;
57d187bc JS	426	}
	427
	428	/*
	429	Convert string to large community attribute.
	430	When type is already known, please specify both str and type.
	431
	432	When string includes keyword for each large community value.
	433	Please specify keyword_included as non-zero value.
	434	*/
d62a17ae	435	struct lcommunity lcommunity_str2com(const char str)
57d187bc	436	{
d62a17ae	437	struct lcommunity *lcom = NULL;
d62a17ae	438	struct lcommunity_val lval;
d62a17ae	439
c850908b WC	440	if (!lcommunity_list_valid(str, LARGE_COMMUNITY_LIST_STANDARD))
	441	return NULL;
	442
6aee3848	443	do {
c850908b WC	444	str = lcommunity_gettoken(str, &lval);
	445	if (lcom == NULL)
	446	lcom = lcommunity_new();
	447	lcommunity_add_val(lcom, &lval);
6aee3848 NT	448	} while (str);
6aee3848 NT	449
d62a17ae	450	return lcom;
57d187bc JS	451	}
57d187bc JS	452
3dc339cd	453	bool lcommunity_include(struct lcommunity lcom, uint8_t ptr)
57d187bc	454	{
d62a17ae	455	int i;
d7c0a89a	456	uint8_t *lcom_ptr;
d62a17ae	457
d62a17ae	458	for (i = 0; i < lcom->size; i++) {
3ac053e6	459	lcom_ptr = lcom->val + (i * LCOMMUNITY_SIZE);
d62a17ae	460	if (memcmp(ptr, lcom_ptr, LCOMMUNITY_SIZE) == 0)
3dc339cd	461	return true;
d62a17ae	462	}
3dc339cd	463	return false;
57d187bc JS	464	}
57d187bc JS	465
3dc339cd DA	466	bool lcommunity_match(const struct lcommunity *lcom1,
3dc339cd DA	467	const struct lcommunity *lcom2)
57d187bc	468	{
d62a17ae	469	int i = 0;
	470	int j = 0;
	471
	472	if (lcom1 == NULL && lcom2 == NULL)
3dc339cd	473	return true;
d62a17ae	474
d62a17ae	475	if (lcom1 == NULL \|\| lcom2 == NULL)
3dc339cd	476	return false;
d62a17ae	477
d62a17ae	478	if (lcom1->size < lcom2->size)
3dc339cd	479	return false;
d62a17ae	480
	481	/* Every community on com2 needs to be on com1 for this to match */
	482	while (i < lcom1->size && j < lcom2->size) {
996c9314 LB	483	if (memcmp(lcom1->val + (i * LCOMMUNITY_SIZE),
996c9314 LB	484	lcom2->val + (j * LCOMMUNITY_SIZE), LCOMMUNITY_SIZE)
d62a17ae	485	== 0)
	486	j++;
	487	i++;
	488	}
	489
	490	if (j == lcom2->size)
3dc339cd	491	return true;
d62a17ae	492	else
3dc339cd	493	return false;
57d187bc JS	494	}
	495
	496	/* Delete one lcommunity. */
d7c0a89a	497	void lcommunity_del_val(struct lcommunity lcom, uint8_t ptr)
57d187bc	498	{
d62a17ae	499	int i = 0;
	500	int c = 0;
	501
	502	if (!lcom->val)
	503	return;
	504
	505	while (i < lcom->size) {
	506	if (memcmp(lcom->val + i * LCOMMUNITY_SIZE, ptr,
	507	LCOMMUNITY_SIZE)
	508	== 0) {
	509	c = lcom->size - i - 1;
	510
	511	if (c > 0)
	512	memmove(lcom->val + i * LCOMMUNITY_SIZE,
	513	lcom->val + (i + 1) * LCOMMUNITY_SIZE,
	514	c * LCOMMUNITY_SIZE);
	515
	516	lcom->size--;
	517
	518	if (lcom->size > 0)
	519	lcom->val =
996c9314 LB	520	XREALLOC(MTYPE_LCOMMUNITY_VAL,
996c9314 LB	521	lcom->val, lcom_length(lcom));
d62a17ae	522	else {
600d7ff8	523	XFREE(MTYPE_LCOMMUNITY_VAL, lcom->val);
d62a17ae	524	}
	525	return;
	526	}
	527	i++;
57d187bc	528	}
57d187bc	529	}
4c99b6c2 NT	530
	531	static struct lcommunity *bgp_aggr_lcommunity_lookup(
	532	struct bgp_aggregate *aggregate,
	533	struct lcommunity *lcommunity)
	534	{
	535	return hash_lookup(aggregate->lcommunity_hash, lcommunity);
	536	}
	537
	538	static void bgp_aggr_lcommunty_hash_alloc(void p)
	539	{
	540	struct lcommunity ref = (struct lcommunity )p;
	541	struct lcommunity *lcommunity = NULL;
	542
	543	lcommunity = lcommunity_dup(ref);
	544	return lcommunity;
	545	}
	546
7f5818fb	547	static void bgp_aggr_lcommunity_prepare(struct hash_bucket hb, void arg)
4c99b6c2	548	{
4c99b6c2 NT	549	struct lcommunity *hb_lcommunity = hb->data;
	550	struct lcommunity **aggr_lcommunity = arg;
	551
f1eb1f05	552	if (*aggr_lcommunity)
	553	aggr_lcommunity = lcommunity_merge(aggr_lcommunity,
	554	hb_lcommunity);
	555	else
4c99b6c2 NT	556	*aggr_lcommunity = lcommunity_dup(hb_lcommunity);
	557	}
	558
	559	void bgp_aggr_lcommunity_remove(void *arg)
	560	{
	561	struct lcommunity *lcommunity = arg;
	562
	563	lcommunity_free(&lcommunity);
	564	}
	565
	566	void bgp_compute_aggregate_lcommunity(struct bgp_aggregate *aggregate,
	567	struct lcommunity *lcommunity)
	568	{
f1eb1f05	569
	570	bgp_compute_aggregate_lcommunity_hash(aggregate, lcommunity);
	571	bgp_compute_aggregate_lcommunity_val(aggregate);
	572	}
	573
	574	void bgp_compute_aggregate_lcommunity_hash(struct bgp_aggregate *aggregate,
	575	struct lcommunity *lcommunity)
	576	{
	577
4c99b6c2 NT	578	struct lcommunity *aggr_lcommunity = NULL;
	579
	580	if ((aggregate == NULL) \|\| (lcommunity == NULL))
	581	return;
	582
	583	/* Create hash if not already created.
	584	*/
	585	if (aggregate->lcommunity_hash == NULL)
	586	aggregate->lcommunity_hash = hash_create(
	587	lcommunity_hash_make, lcommunity_cmp,
	588	"BGP Aggregator lcommunity hash");
	589
	590	aggr_lcommunity = bgp_aggr_lcommunity_lookup(aggregate, lcommunity);
	591	if (aggr_lcommunity == NULL) {
	592	/* Insert lcommunity into hash.
	593	*/
	594	aggr_lcommunity = hash_get(aggregate->lcommunity_hash,
	595	lcommunity,
	596	bgp_aggr_lcommunty_hash_alloc);
f1eb1f05	597	}
4c99b6c2	598
f1eb1f05	599	/* Increment reference counter.
	600	*/
	601	aggr_lcommunity->refcnt++;
	602	}
	603
	604	void bgp_compute_aggregate_lcommunity_val(struct bgp_aggregate *aggregate)
	605	{
	606	struct lcommunity *lcommerge = NULL;
	607
	608	if (aggregate == NULL)
	609	return;
4c99b6c2	610
f1eb1f05	611	/* Re-compute aggregate's lcommunity.
	612	*/
	613	if (aggregate->lcommunity)
	614	lcommunity_free(&aggregate->lcommunity);
	615	if (aggregate->lcommunity_hash &&
	616	aggregate->lcommunity_hash->count) {
4c99b6c2 NT	617	hash_iterate(aggregate->lcommunity_hash,
	618	bgp_aggr_lcommunity_prepare,
	619	&aggregate->lcommunity);
f1eb1f05	620	lcommerge = aggregate->lcommunity;
	621	aggregate->lcommunity = lcommunity_uniq_sort(lcommerge);
	622	if (lcommerge)
	623	lcommunity_free(&lcommerge);
4c99b6c2	624	}
4c99b6c2 NT	625	}
	626
	627	void bgp_remove_lcommunity_from_aggregate(struct bgp_aggregate *aggregate,
	628	struct lcommunity *lcommunity)
	629	{
	630	struct lcommunity *aggr_lcommunity = NULL;
	631	struct lcommunity *ret_lcomm = NULL;
	632
f1eb1f05	633	if ((!aggregate)
	634	\|\| (!aggregate->lcommunity_hash)
	635	\|\| (!lcommunity))
4c99b6c2 NT	636	return;
	637
	638	/* Look-up the lcommunity in the hash.
	639	*/
	640	aggr_lcommunity = bgp_aggr_lcommunity_lookup(aggregate, lcommunity);
	641	if (aggr_lcommunity) {
	642	aggr_lcommunity->refcnt--;
	643
	644	if (aggr_lcommunity->refcnt == 0) {
	645	ret_lcomm = hash_release(aggregate->lcommunity_hash,
	646	aggr_lcommunity);
	647	lcommunity_free(&ret_lcomm);
	648
f1eb1f05	649	bgp_compute_aggregate_lcommunity_val(aggregate);
	650
	651	}
	652	}
	653	}
	654
	655	void bgp_remove_lcomm_from_aggregate_hash(struct bgp_aggregate *aggregate,
	656	struct lcommunity *lcommunity)
	657	{
	658	struct lcommunity *aggr_lcommunity = NULL;
	659	struct lcommunity *ret_lcomm = NULL;
4c99b6c2	660
f1eb1f05	661	if ((!aggregate)
	662	\|\| (!aggregate->lcommunity_hash)
	663	\|\| (!lcommunity))
	664	return;
	665
	666	/* Look-up the lcommunity in the hash.
	667	*/
	668	aggr_lcommunity = bgp_aggr_lcommunity_lookup(aggregate, lcommunity);
	669	if (aggr_lcommunity) {
	670	aggr_lcommunity->refcnt--;
	671
	672	if (aggr_lcommunity->refcnt == 0) {
	673	ret_lcomm = hash_release(aggregate->lcommunity_hash,
	674	aggr_lcommunity);
	675	lcommunity_free(&ret_lcomm);
4c99b6c2 NT	676	}
	677	}
	678	}