1 /* BGP Large Communities Attribute
3 * Copyright (C) 2016 Keyur Patel <keyur@arrcus.com>
5 * This file is part of FreeRangeRouting (FRR).
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.
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
16 * You should have received a copy of the GNU General Public License along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
31 #include "bgpd/bgpd.h"
32 #include "bgpd/bgp_lcommunity.h"
33 #include "bgpd/bgp_aspath.h"
35 /* Hash of community attribute. */
36 static struct hash
*lcomhash
;
38 /* Allocate a new lcommunities. */
39 static struct lcommunity
*lcommunity_new(void)
41 return XCALLOC(MTYPE_LCOMMUNITY
, sizeof(struct lcommunity
));
44 /* Allocate lcommunities. */
45 void lcommunity_free(struct lcommunity
**lcom
)
47 XFREE(MTYPE_LCOMMUNITY_VAL
, (*lcom
)->val
);
48 XFREE(MTYPE_LCOMMUNITY_STR
, (*lcom
)->str
);
49 XFREE(MTYPE_LCOMMUNITY
, *lcom
);
52 static void lcommunity_hash_free(struct lcommunity
*lcom
)
54 lcommunity_free(&lcom
);
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
62 static int lcommunity_add_val(struct lcommunity
*lcom
,
63 struct lcommunity_val
*lval
)
69 /* When this is fist value, just add it. */
70 if (lcom
->val
== NULL
) {
72 lcom
->val
= XMALLOC(MTYPE_LCOMMUNITY_VAL
, lcom_length(lcom
));
73 memcpy(lcom
->val
, lval
->val
, LCOMMUNITY_SIZE
);
77 /* If the value already exists in the structure return 0. */
79 for (p
= lcom
->val
; c
< lcom
->size
; p
+= LCOMMUNITY_SIZE
, c
++) {
80 ret
= memcmp(p
, lval
->val
, LCOMMUNITY_SIZE
);
87 /* Add the value to the structure with numerical sorting. */
90 XREALLOC(MTYPE_LCOMMUNITY_VAL
, lcom
->val
, lcom_length(lcom
));
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
);
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. */
103 struct lcommunity
*lcommunity_uniq_sort(struct lcommunity
*lcom
)
106 struct lcommunity
*new;
107 struct lcommunity_val
*lval
;
112 new = lcommunity_new();
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
);
122 /* Parse Large Communites Attribute in BGP packet. */
123 struct lcommunity
*lcommunity_parse(uint8_t *pnt
, unsigned short length
)
125 struct lcommunity tmp
;
126 struct lcommunity
*new;
129 if (length
% LCOMMUNITY_SIZE
)
132 /* Prepare tmporary structure for making a new Large Communities
134 tmp
.size
= length
/ LCOMMUNITY_SIZE
;
137 /* Create a new Large Communities Attribute by uniq and sort each
138 Large Communities value */
139 new = lcommunity_uniq_sort(&tmp
);
141 return lcommunity_intern(new);
144 /* Duplicate the Large Communities Attribute structure. */
145 struct lcommunity
*lcommunity_dup(struct lcommunity
*lcom
)
147 struct lcommunity
*new;
149 new = lcommunity_new();
150 new->size
= lcom
->size
;
152 new->val
= XMALLOC(MTYPE_LCOMMUNITY_VAL
, lcom_length(lcom
));
153 memcpy(new->val
, lcom
->val
, lcom_length(lcom
));
159 /* Merge two Large Communities Attribute structure. */
160 struct lcommunity
*lcommunity_merge(struct lcommunity
*lcom1
,
161 struct lcommunity
*lcom2
)
164 lcom1
->val
= XREALLOC(MTYPE_LCOMMUNITY_VAL
, lcom1
->val
,
165 lcom_length(lcom1
) + lcom_length(lcom2
));
167 lcom1
->val
= XMALLOC(MTYPE_LCOMMUNITY_VAL
,
168 lcom_length(lcom1
) + lcom_length(lcom2
));
170 memcpy(lcom1
->val
+ lcom_length(lcom1
), lcom2
->val
, lcom_length(lcom2
));
171 lcom1
->size
+= lcom2
->size
;
176 static void set_lcommunity_string(struct lcommunity
*lcom
, bool make_json
)
182 uint32_t global
, local1
, local2
;
183 json_object
*json_lcommunity_list
= NULL
;
184 json_object
*json_string
= NULL
;
186 /* 3 32-bit integers, 2 colons, and a space */
187 #define LCOMMUNITY_STRLEN (10 * 3 + 2 + 1)
193 lcom
->json
= json_object_new_object();
194 json_lcommunity_list
= json_object_new_array();
197 if (lcom
->size
== 0) {
198 str_buf
= XCALLOC(MTYPE_LCOMMUNITY_STR
, 1);
201 json_object_string_add(lcom
->json
, "string", "");
202 json_object_object_add(lcom
->json
, "list",
203 json_lcommunity_list
);
210 /* 1 space + lcom->size lcom strings + null terminator */
211 size_t str_buf_sz
= (LCOMMUNITY_STRLEN
* lcom
->size
) + 2;
212 str_buf
= XCALLOC(MTYPE_LCOMMUNITY_STR
, str_buf_sz
);
214 for (i
= 0; i
< lcom
->size
; i
++) {
216 strlcat(str_buf
, " ", str_buf_sz
);
218 pnt
= lcom
->val
+ (i
* LCOMMUNITY_SIZE
);
219 pnt
= ptr_get_be32(pnt
, &global
);
220 pnt
= ptr_get_be32(pnt
, &local1
);
221 pnt
= ptr_get_be32(pnt
, &local2
);
224 char lcsb
[LCOMMUNITY_STRLEN
+ 1];
226 snprintf(lcsb
, sizeof(lcsb
), "%u:%u:%u", global
, local1
,
229 len
= strlcat(str_buf
, lcsb
, str_buf_sz
);
230 assert((unsigned int)len
< str_buf_sz
);
233 json_string
= json_object_new_string(lcsb
);
234 json_object_array_add(json_lcommunity_list
,
240 json_object_string_add(lcom
->json
, "string", str_buf
);
241 json_object_object_add(lcom
->json
, "list",
242 json_lcommunity_list
);
248 /* Intern Large Communities Attribute. */
249 struct lcommunity
*lcommunity_intern(struct lcommunity
*lcom
)
251 struct lcommunity
*find
;
253 assert(lcom
->refcnt
== 0);
255 find
= (struct lcommunity
*)hash_get(lcomhash
, lcom
, hash_alloc_intern
);
258 lcommunity_free(&lcom
);
263 set_lcommunity_string(find
, false);
268 /* Unintern Large Communities Attribute. */
269 void lcommunity_unintern(struct lcommunity
**lcom
)
271 struct lcommunity
*ret
;
276 /* Pull off from hash. */
277 if ((*lcom
)->refcnt
== 0) {
278 /* Large community must be in the hash. */
279 ret
= (struct lcommunity
*)hash_release(lcomhash
, *lcom
);
282 lcommunity_free(lcom
);
286 /* Retrun string representation of communities attribute. */
287 char *lcommunity_str(struct lcommunity
*lcom
, bool make_json
)
292 if (make_json
&& !lcom
->json
&& lcom
->str
)
293 XFREE(MTYPE_LCOMMUNITY_STR
, lcom
->str
);
296 set_lcommunity_string(lcom
, make_json
);
301 /* Utility function to make hash key. */
302 unsigned int lcommunity_hash_make(const void *arg
)
304 const struct lcommunity
*lcom
= arg
;
305 int size
= lcom_length(lcom
);
307 return jhash(lcom
->val
, size
, 0xab125423);
310 /* Compare two Large Communities Attribute structure. */
311 bool lcommunity_cmp(const void *arg1
, const void *arg2
)
313 const struct lcommunity
*lcom1
= arg1
;
314 const struct lcommunity
*lcom2
= arg2
;
316 if (lcom1
== NULL
&& lcom2
== NULL
)
319 if (lcom1
== NULL
|| lcom2
== NULL
)
322 return (lcom1
->size
== lcom2
->size
323 && memcmp(lcom1
->val
, lcom2
->val
, lcom_length(lcom1
)) == 0);
326 /* Return communities hash. */
327 struct hash
*lcommunity_hash(void)
332 /* Initialize Large Comminities related hash. */
333 void lcommunity_init(void)
335 lcomhash
= hash_create(lcommunity_hash_make
, lcommunity_cmp
,
336 "BGP lcommunity hash");
339 void lcommunity_finish(void)
341 hash_clean(lcomhash
, (void (*)(void *))lcommunity_hash_free
);
346 /* Large Communities token enum. */
347 enum lcommunity_token
{
348 lcommunity_token_unknown
= 0,
349 lcommunity_token_val
,
352 /* Get next Large Communities token from the string. */
353 static const char *lcommunity_gettoken(const char *str
,
354 struct lcommunity_val
*lval
,
355 enum lcommunity_token
*token
)
359 /* Skip white space. */
360 while (isspace((unsigned char)*p
)) {
365 /* Check the end of the line. */
369 /* Community value. */
370 if (isdigit((unsigned char)*p
)) {
373 uint32_t globaladmin
= 0;
374 uint32_t localdata1
= 0;
375 uint32_t localdata2
= 0;
377 while (isdigit((unsigned char)*p
) || *p
== ':') {
379 if (separator
== 2) {
380 *token
= lcommunity_token_unknown
;
385 if (separator
== 1) {
386 globaladmin
= localdata2
;
388 localdata1
= localdata2
;
395 localdata2
+= (*p
- '0');
400 *token
= lcommunity_token_unknown
;
405 * Copy the large comm.
407 lval
->val
[0] = (globaladmin
>> 24) & 0xff;
408 lval
->val
[1] = (globaladmin
>> 16) & 0xff;
409 lval
->val
[2] = (globaladmin
>> 8) & 0xff;
410 lval
->val
[3] = globaladmin
& 0xff;
411 lval
->val
[4] = (localdata1
>> 24) & 0xff;
412 lval
->val
[5] = (localdata1
>> 16) & 0xff;
413 lval
->val
[6] = (localdata1
>> 8) & 0xff;
414 lval
->val
[7] = localdata1
& 0xff;
415 lval
->val
[8] = (localdata2
>> 24) & 0xff;
416 lval
->val
[9] = (localdata2
>> 16) & 0xff;
417 lval
->val
[10] = (localdata2
>> 8) & 0xff;
418 lval
->val
[11] = localdata2
& 0xff;
420 *token
= lcommunity_token_val
;
423 *token
= lcommunity_token_unknown
;
428 Convert string to large community attribute.
429 When type is already known, please specify both str and type.
431 When string includes keyword for each large community value.
432 Please specify keyword_included as non-zero value.
434 struct lcommunity
*lcommunity_str2com(const char *str
)
436 struct lcommunity
*lcom
= NULL
;
437 enum lcommunity_token token
= lcommunity_token_unknown
;
438 struct lcommunity_val lval
;
441 str
= lcommunity_gettoken(str
, &lval
, &token
);
443 case lcommunity_token_val
:
445 lcom
= lcommunity_new();
446 lcommunity_add_val(lcom
, &lval
);
448 case lcommunity_token_unknown
:
451 lcommunity_free(&lcom
);
459 int lcommunity_include(struct lcommunity
*lcom
, uint8_t *ptr
)
464 for (i
= 0; i
< lcom
->size
; i
++) {
465 lcom_ptr
= lcom
->val
+ (i
* LCOMMUNITY_SIZE
);
466 if (memcmp(ptr
, lcom_ptr
, LCOMMUNITY_SIZE
) == 0)
472 int lcommunity_match(const struct lcommunity
*lcom1
,
473 const struct lcommunity
*lcom2
)
478 if (lcom1
== NULL
&& lcom2
== NULL
)
481 if (lcom1
== NULL
|| lcom2
== NULL
)
484 if (lcom1
->size
< lcom2
->size
)
487 /* Every community on com2 needs to be on com1 for this to match */
488 while (i
< lcom1
->size
&& j
< lcom2
->size
) {
489 if (memcmp(lcom1
->val
+ (i
* LCOMMUNITY_SIZE
),
490 lcom2
->val
+ (j
* LCOMMUNITY_SIZE
), LCOMMUNITY_SIZE
)
496 if (j
== lcom2
->size
)
502 /* Delete one lcommunity. */
503 void lcommunity_del_val(struct lcommunity
*lcom
, uint8_t *ptr
)
511 while (i
< lcom
->size
) {
512 if (memcmp(lcom
->val
+ i
* LCOMMUNITY_SIZE
, ptr
,
515 c
= lcom
->size
- i
- 1;
518 memmove(lcom
->val
+ i
* LCOMMUNITY_SIZE
,
519 lcom
->val
+ (i
+ 1) * LCOMMUNITY_SIZE
,
520 c
* LCOMMUNITY_SIZE
);
526 XREALLOC(MTYPE_LCOMMUNITY_VAL
,
527 lcom
->val
, lcom_length(lcom
));
529 XFREE(MTYPE_LCOMMUNITY_VAL
, lcom
->val
);
538 static struct lcommunity
*bgp_aggr_lcommunity_lookup(
539 struct bgp_aggregate
*aggregate
,
540 struct lcommunity
*lcommunity
)
542 return hash_lookup(aggregate
->lcommunity_hash
, lcommunity
);
545 static void *bgp_aggr_lcommunty_hash_alloc(void *p
)
547 struct lcommunity
*ref
= (struct lcommunity
*)p
;
548 struct lcommunity
*lcommunity
= NULL
;
550 lcommunity
= lcommunity_dup(ref
);
554 static void bgp_aggr_lcommunity_prepare(struct hash_backet
*hb
, void *arg
)
556 struct lcommunity
*hb_lcommunity
= hb
->data
;
557 struct lcommunity
**aggr_lcommunity
= arg
;
559 if (*aggr_lcommunity
)
560 *aggr_lcommunity
= lcommunity_merge(*aggr_lcommunity
,
563 *aggr_lcommunity
= lcommunity_dup(hb_lcommunity
);
566 void bgp_aggr_lcommunity_remove(void *arg
)
568 struct lcommunity
*lcommunity
= arg
;
570 lcommunity_free(&lcommunity
);
573 void bgp_compute_aggregate_lcommunity(struct bgp_aggregate
*aggregate
,
574 struct lcommunity
*lcommunity
)
577 bgp_compute_aggregate_lcommunity_hash(aggregate
, lcommunity
);
578 bgp_compute_aggregate_lcommunity_val(aggregate
);
581 void bgp_compute_aggregate_lcommunity_hash(struct bgp_aggregate
*aggregate
,
582 struct lcommunity
*lcommunity
)
585 struct lcommunity
*aggr_lcommunity
= NULL
;
587 if ((aggregate
== NULL
) || (lcommunity
== NULL
))
590 /* Create hash if not already created.
592 if (aggregate
->lcommunity_hash
== NULL
)
593 aggregate
->lcommunity_hash
= hash_create(
594 lcommunity_hash_make
, lcommunity_cmp
,
595 "BGP Aggregator lcommunity hash");
597 aggr_lcommunity
= bgp_aggr_lcommunity_lookup(aggregate
, lcommunity
);
598 if (aggr_lcommunity
== NULL
) {
599 /* Insert lcommunity into hash.
601 aggr_lcommunity
= hash_get(aggregate
->lcommunity_hash
,
603 bgp_aggr_lcommunty_hash_alloc
);
606 /* Increment reference counter.
608 aggr_lcommunity
->refcnt
++;
611 void bgp_compute_aggregate_lcommunity_val(struct bgp_aggregate
*aggregate
)
613 struct lcommunity
*lcommerge
= NULL
;
615 if (aggregate
== NULL
)
618 /* Re-compute aggregate's lcommunity.
620 if (aggregate
->lcommunity
)
621 lcommunity_free(&aggregate
->lcommunity
);
622 if (aggregate
->lcommunity_hash
&&
623 aggregate
->lcommunity_hash
->count
) {
624 hash_iterate(aggregate
->lcommunity_hash
,
625 bgp_aggr_lcommunity_prepare
,
626 &aggregate
->lcommunity
);
627 lcommerge
= aggregate
->lcommunity
;
628 aggregate
->lcommunity
= lcommunity_uniq_sort(lcommerge
);
630 lcommunity_free(&lcommerge
);
634 void bgp_remove_lcommunity_from_aggregate(struct bgp_aggregate
*aggregate
,
635 struct lcommunity
*lcommunity
)
637 struct lcommunity
*aggr_lcommunity
= NULL
;
638 struct lcommunity
*ret_lcomm
= NULL
;
641 || (!aggregate
->lcommunity_hash
)
645 /* Look-up the lcommunity in the hash.
647 aggr_lcommunity
= bgp_aggr_lcommunity_lookup(aggregate
, lcommunity
);
648 if (aggr_lcommunity
) {
649 aggr_lcommunity
->refcnt
--;
651 if (aggr_lcommunity
->refcnt
== 0) {
652 ret_lcomm
= hash_release(aggregate
->lcommunity_hash
,
654 lcommunity_free(&ret_lcomm
);
656 bgp_compute_aggregate_lcommunity_val(aggregate
);
662 void bgp_remove_lcomm_from_aggregate_hash(struct bgp_aggregate
*aggregate
,
663 struct lcommunity
*lcommunity
)
665 struct lcommunity
*aggr_lcommunity
= NULL
;
666 struct lcommunity
*ret_lcomm
= NULL
;
669 || (!aggregate
->lcommunity_hash
)
673 /* Look-up the lcommunity in the hash.
675 aggr_lcommunity
= bgp_aggr_lcommunity_lookup(aggregate
, lcommunity
);
676 if (aggr_lcommunity
) {
677 aggr_lcommunity
->refcnt
--;
679 if (aggr_lcommunity
->refcnt
== 0) {
680 ret_lcomm
= hash_release(aggregate
->lcommunity_hash
,
682 lcommunity_free(&ret_lcomm
);