[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(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((int)*p)) {
		p++;
		str++;
	}

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

	/* Community value. */
	if (isdigit((int)*p)) {
		int separator = 0;
		int digit = 0;
		uint32_t globaladmin = 0;
		uint32_t localdata1 = 0;
		uint32_t localdata2 = 0;

		while (isdigit((int)*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;

	while ((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;
		}
	}
	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. */
d62a17ae	304	unsigned int lcommunity_hash_make(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. */
	362	while (isspace((int)*p)) {
	363	p++;
	364	str++;
	365	}
	366
	367	/* Check the end of the line. */
	368	if (*p == '\0')
	369	return NULL;
	370
	371	/* Community value. */
	372	if (isdigit((int)*p)) {
	373	int separator = 0;
	374	int digit = 0;
d7c0a89a QY	375	uint32_t globaladmin = 0;
	376	uint32_t localdata1 = 0;
	377	uint32_t localdata2 = 0;
d62a17ae	378
	379	while (isdigit((int)p) \|\| p == ':') {
	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
	442	while ((str = lcommunity_gettoken(str, &lval, &token))) {
	443	switch (token) {
	444	case lcommunity_token_val:
	445	if (lcom == NULL)
	446	lcom = lcommunity_new();
	447	lcommunity_add_val(lcom, &lval);
	448	break;
	449	case lcommunity_token_unknown:
	450	default:
	451	if (lcom)
	452	lcommunity_free(&lcom);
	453	return NULL;
	454	}
	455	}
	456	return lcom;
57d187bc JS	457	}
57d187bc JS	458
d7c0a89a	459	int lcommunity_include(struct lcommunity lcom, uint8_t ptr)
57d187bc	460	{
d62a17ae	461	int i;
d7c0a89a	462	uint8_t *lcom_ptr;
d62a17ae	463
d62a17ae	464	for (i = 0; i < lcom->size; i++) {
3ac053e6	465	lcom_ptr = lcom->val + (i * LCOMMUNITY_SIZE);
d62a17ae	466	if (memcmp(ptr, lcom_ptr, LCOMMUNITY_SIZE) == 0)
	467	return 1;
	468	}
	469	return 0;
57d187bc JS	470	}
57d187bc JS	471
d62a17ae	472	int lcommunity_match(const struct lcommunity *lcom1,
d62a17ae	473	const struct lcommunity *lcom2)
57d187bc	474	{
d62a17ae	475	int i = 0;
	476	int j = 0;
	477
	478	if (lcom1 == NULL && lcom2 == NULL)
	479	return 1;
	480
	481	if (lcom1 == NULL \|\| lcom2 == NULL)
	482	return 0;
	483
	484	if (lcom1->size < lcom2->size)
	485	return 0;
	486
	487	/* Every community on com2 needs to be on com1 for this to match */
	488	while (i < lcom1->size && j < lcom2->size) {
996c9314 LB	489	if (memcmp(lcom1->val + (i * LCOMMUNITY_SIZE),
996c9314 LB	490	lcom2->val + (j * LCOMMUNITY_SIZE), LCOMMUNITY_SIZE)
d62a17ae	491	== 0)
	492	j++;
	493	i++;
	494	}
	495
	496	if (j == lcom2->size)
	497	return 1;
	498	else
	499	return 0;
57d187bc JS	500	}
	501
	502	/* Delete one lcommunity. */
d7c0a89a	503	void lcommunity_del_val(struct lcommunity lcom, uint8_t ptr)
57d187bc	504	{
d62a17ae	505	int i = 0;
	506	int c = 0;
	507
	508	if (!lcom->val)
	509	return;
	510
	511	while (i < lcom->size) {
	512	if (memcmp(lcom->val + i * LCOMMUNITY_SIZE, ptr,
	513	LCOMMUNITY_SIZE)
	514	== 0) {
	515	c = lcom->size - i - 1;
	516
	517	if (c > 0)
	518	memmove(lcom->val + i * LCOMMUNITY_SIZE,
	519	lcom->val + (i + 1) * LCOMMUNITY_SIZE,
	520	c * LCOMMUNITY_SIZE);
	521
	522	lcom->size--;
	523
	524	if (lcom->size > 0)
	525	lcom->val =
996c9314 LB	526	XREALLOC(MTYPE_LCOMMUNITY_VAL,
996c9314 LB	527	lcom->val, lcom_length(lcom));
d62a17ae	528	else {
600d7ff8	529	XFREE(MTYPE_LCOMMUNITY_VAL, lcom->val);
d62a17ae	530	lcom->val = NULL;
	531	}
	532	return;
	533	}
	534	i++;
57d187bc	535	}
57d187bc	536	}
4c99b6c2 NT	537
	538	static struct lcommunity *bgp_aggr_lcommunity_lookup(
	539	struct bgp_aggregate *aggregate,
	540	struct lcommunity *lcommunity)
	541	{
	542	return hash_lookup(aggregate->lcommunity_hash, lcommunity);
	543	}
	544
	545	static void bgp_aggr_lcommunty_hash_alloc(void p)
	546	{
	547	struct lcommunity ref = (struct lcommunity )p;
	548	struct lcommunity *lcommunity = NULL;
	549
	550	lcommunity = lcommunity_dup(ref);
	551	return lcommunity;
	552	}
	553
	554	static void bgp_aggr_lcommunity_prepare(struct hash_backet hb, void arg)
	555	{
	556	struct lcommunity *lcommerge = NULL;
	557	struct lcommunity *hb_lcommunity = hb->data;
	558	struct lcommunity **aggr_lcommunity = arg;
	559
	560	if (*aggr_lcommunity) {
	561	lcommerge = lcommunity_merge(*aggr_lcommunity, hb_lcommunity);
	562	*aggr_lcommunity = lcommunity_uniq_sort(lcommerge);
	563	lcommunity_free(&lcommerge);
	564	} else
	565	*aggr_lcommunity = lcommunity_dup(hb_lcommunity);
	566	}
	567
	568	void bgp_aggr_lcommunity_remove(void *arg)
	569	{
	570	struct lcommunity *lcommunity = arg;
	571
	572	lcommunity_free(&lcommunity);
	573	}
	574
	575	void bgp_compute_aggregate_lcommunity(struct bgp_aggregate *aggregate,
	576	struct lcommunity *lcommunity)
	577	{
	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);
	597
	598	/* Re-compute aggregate's lcommunity.
	599	*/
	600	if (aggregate->lcommunity)
601	lcommunity_free(&aggregate->lcommunity);
602
603	hash_iterate(aggregate->lcommunity_hash,
604	bgp_aggr_lcommunity_prepare,
605	&aggregate->lcommunity);
606	}
607
608	/* Increment refernce counter.
609	*/
610	aggr_lcommunity->refcnt++;
611	}
612
613	void bgp_remove_lcommunity_from_aggregate(struct bgp_aggregate *aggregate,
614	struct lcommunity *lcommunity)
615	{
616	struct lcommunity *aggr_lcommunity = NULL;
617	struct lcommunity *ret_lcomm = NULL;
618
619	if ((aggregate == NULL) \|\| (lcommunity == NULL))
620	return;
621
622	if (aggregate->lcommunity_hash == NULL)
623	return;
624
625	/* Look-up the lcommunity in the hash.
626	*/
627	aggr_lcommunity = bgp_aggr_lcommunity_lookup(aggregate, lcommunity);
628	if (aggr_lcommunity) {
629	aggr_lcommunity->refcnt--;
630
631	if (aggr_lcommunity->refcnt == 0) {
632	ret_lcomm = hash_release(aggregate->lcommunity_hash,
633	aggr_lcommunity);
634	lcommunity_free(&ret_lcomm);
635
636	lcommunity_free(&aggregate->lcommunity);
637
638	/* Compute aggregate's lcommunity.
639	*/
640	hash_iterate(aggregate->lcommunity_hash,
641	bgp_aggr_lcommunity_prepare,
642	&aggregate->lcommunity);
643	}
644	}
645	}