[mirror_frr.git] / bgpd / bgp_lcommunity.c

/* BGP Large Communities Attribute
 *
 * Copyright (C) 2016 Keyur Patel <keyur@arrcus.com>
 *
 * This file is part of FreeRangeRouting (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_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)
{
	XFREE(MTYPE_LCOMMUNITY_VAL, (*lcom)->val);
	XFREE(MTYPE_LCOMMUNITY_STR, (*lcom)->str);
	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 int 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 1;
	}

	/* 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 0;
		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 1;
}

/* This function takes pointer to Large Communites strucutre 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)
{
	if (lcom1->val)
		lcom1->val = XREALLOC(MTYPE_LCOMMUNITY_VAL, lcom1->val,
				      lcom_length(lcom1) + lcom_length(lcom2));
	else
		lcom1->val = XMALLOC(MTYPE_LCOMMUNITY_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)
{
	int i;
	int len;
	bool first = true;
	char *str_buf;
	char *str_pnt;
	uint8_t *pnt;
	uint32_t global, local1, local2;
	json_object *json_lcommunity_list = NULL;
	json_object *json_string = NULL;

#define LCOMMUNITY_STR_DEFAULT_LEN 32

	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 = XMALLOC(MTYPE_LCOMMUNITY_STR, 1);
		str_buf[0] = '\0';

		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;
	}

	str_buf = str_pnt =
		XMALLOC(MTYPE_LCOMMUNITY_STR,
			(LCOMMUNITY_STR_DEFAULT_LEN * lcom->size) + 1);

	for (i = 0; i < lcom->size; i++) {
		if (first)
			first = false;
		else
			*str_pnt++ = ' ';

		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;

		len = sprintf(str_pnt, "%u:%u:%u", global, local1, local2);
		if (make_json) {
			json_string = json_object_new_string(str_pnt);
			json_object_array_add(json_lcommunity_list,
					      json_string);
		}

		str_pnt += len;
	}

	str_buf =
		XREALLOC(MTYPE_LCOMMUNITY_STR, str_buf, str_pnt - str_buf + 1);

	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);

	return find;
}

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

	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);
	}
}

/* Retrun string representation of communities attribute. */
char *lcommunity_str(struct lcommunity *lcom, bool make_json)
{
	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);

	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;
}

/* Large Communities token enum. */
enum lcommunity_token {
	lcommunity_token_unknown = 0,
	lcommunity_token_val,
};

/* Get next Large Communities token from the string. */
static const char *lcommunity_gettoken(const char *str,
				       struct lcommunity_val *lval,
				       enum lcommunity_token *token)
{
	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. */
	if (isdigit((unsigned char)*p)) {
		int separator = 0;
		int digit = 0;
		uint32_t globaladmin = 0;
		uint32_t localdata1 = 0;
		uint32_t localdata2 = 0;

		while (isdigit((unsigned char)*p) || *p == ':') {
			if (*p == ':') {
				if (separator == 2) {
					*token = lcommunity_token_unknown;
					return NULL;
				} else {
					separator++;
					digit = 0;
					if (separator == 1) {
						globaladmin = localdata2;
					} else {
						localdata1 = localdata2;
					}
					localdata2 = 0;
				}
			} else {
				digit = 1;
				localdata2 *= 10;
				localdata2 += (*p - '0');
			}
			p++;
		}
		if (!digit) {
			*token = lcommunity_token_unknown;
			return NULL;
		}

		/*
		 * 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;

		*token = lcommunity_token_val;
		return p;
	}
	*token = lcommunity_token_unknown;
	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;
	enum lcommunity_token token = lcommunity_token_unknown;
	struct lcommunity_val lval;

	do {
		str = lcommunity_gettoken(str, &lval, &token);
		switch (token) {
		case lcommunity_token_val:
			if (lcom == NULL)
				lcom = lcommunity_new();
			lcommunity_add_val(lcom, &lval);
			break;
		case lcommunity_token_unknown:
		default:
			if (lcom)
				lcommunity_free(&lcom);
			return NULL;
		}
	} while (str);

	return lcom;
}

int 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 1;
	}
	return 0;
}

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

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

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

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

	/* 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 1;
	else
		return 0;
}

/* 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);
				lcom->val = NULL;
			}
			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_backet *hb, void *arg)
{
	struct lcommunity *lcommerge = NULL;
	struct lcommunity *hb_lcommunity = hb->data;
	struct lcommunity **aggr_lcommunity = arg;

	if (*aggr_lcommunity) {
		lcommerge = lcommunity_merge(*aggr_lcommunity, hb_lcommunity);
		*aggr_lcommunity = lcommunity_uniq_sort(lcommerge);
		lcommunity_free(&lcommerge);
	} 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)
{
	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);

		/* Re-compute aggregate's lcommunity.
		 */
		if (aggregate->lcommunity)
			lcommunity_free(&aggregate->lcommunity);

		hash_iterate(aggregate->lcommunity_hash,
			     bgp_aggr_lcommunity_prepare,
			     &aggregate->lcommunity);
	}

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

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 == NULL) || (lcommunity == NULL))
		return;

	if (aggregate->lcommunity_hash == NULL)
		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);

			lcommunity_free(&aggregate->lcommunity);

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