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
)
184 uint32_t global
, local1
, local2
;
185 json_object
*json_lcommunity_list
= NULL
;
186 json_object
*json_string
= NULL
;
188 #define LCOMMUNITY_STR_DEFAULT_LEN 32
194 lcom
->json
= json_object_new_object();
195 json_lcommunity_list
= json_object_new_array();
198 if (lcom
->size
== 0) {
199 str_buf
= XMALLOC(MTYPE_LCOMMUNITY_STR
, 1);
203 json_object_string_add(lcom
->json
, "string", "");
204 json_object_object_add(lcom
->json
, "list",
205 json_lcommunity_list
);
213 XMALLOC(MTYPE_LCOMMUNITY_STR
,
214 (LCOMMUNITY_STR_DEFAULT_LEN
* lcom
->size
) + 1);
216 for (i
= 0; i
< lcom
->size
; i
++) {
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
);
228 len
= sprintf(str_pnt
, "%u:%u:%u", global
, local1
, local2
);
230 json_string
= json_object_new_string(str_pnt
);
231 json_object_array_add(json_lcommunity_list
,
239 XREALLOC(MTYPE_LCOMMUNITY_STR
, str_buf
, str_pnt
- str_buf
+ 1);
242 json_object_string_add(lcom
->json
, "string", str_buf
);
243 json_object_object_add(lcom
->json
, "list",
244 json_lcommunity_list
);
250 /* Intern Large Communities Attribute. */
251 struct lcommunity
*lcommunity_intern(struct lcommunity
*lcom
)
253 struct lcommunity
*find
;
255 assert(lcom
->refcnt
== 0);
257 find
= (struct lcommunity
*)hash_get(lcomhash
, lcom
, hash_alloc_intern
);
260 lcommunity_free(&lcom
);
265 set_lcommunity_string(find
, false);
270 /* Unintern Large Communities Attribute. */
271 void lcommunity_unintern(struct lcommunity
**lcom
)
273 struct lcommunity
*ret
;
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
);
284 lcommunity_free(lcom
);
288 /* Retrun string representation of communities attribute. */
289 char *lcommunity_str(struct lcommunity
*lcom
, bool make_json
)
294 if (make_json
&& !lcom
->json
&& lcom
->str
)
295 XFREE(MTYPE_LCOMMUNITY_STR
, lcom
->str
);
298 set_lcommunity_string(lcom
, make_json
);
303 /* Utility function to make hash key. */
304 unsigned int lcommunity_hash_make(void *arg
)
306 const struct lcommunity
*lcom
= arg
;
307 int size
= lcom_length(lcom
);
309 return jhash(lcom
->val
, size
, 0xab125423);
312 /* Compare two Large Communities Attribute structure. */
313 bool lcommunity_cmp(const void *arg1
, const void *arg2
)
315 const struct lcommunity
*lcom1
= arg1
;
316 const struct lcommunity
*lcom2
= arg2
;
318 if (lcom1
== NULL
&& lcom2
== NULL
)
321 if (lcom1
== NULL
|| lcom2
== NULL
)
324 return (lcom1
->size
== lcom2
->size
325 && memcmp(lcom1
->val
, lcom2
->val
, lcom_length(lcom1
)) == 0);
328 /* Return communities hash. */
329 struct hash
*lcommunity_hash(void)
334 /* Initialize Large Comminities related hash. */
335 void lcommunity_init(void)
337 lcomhash
= hash_create(lcommunity_hash_make
, lcommunity_cmp
,
338 "BGP lcommunity hash");
341 void lcommunity_finish(void)
343 hash_clean(lcomhash
, (void (*)(void *))lcommunity_hash_free
);
348 /* Large Communities token enum. */
349 enum lcommunity_token
{
350 lcommunity_token_unknown
= 0,
351 lcommunity_token_val
,
354 /* Get next Large Communities token from the string. */
355 static const char *lcommunity_gettoken(const char *str
,
356 struct lcommunity_val
*lval
,
357 enum lcommunity_token
*token
)
361 /* Skip white space. */
362 while (isspace((int)*p
)) {
367 /* Check the end of the line. */
371 /* Community value. */
372 if (isdigit((int)*p
)) {
375 uint32_t globaladmin
= 0;
376 uint32_t localdata1
= 0;
377 uint32_t localdata2
= 0;
379 while (isdigit((int)*p
) || *p
== ':') {
381 if (separator
== 2) {
382 *token
= lcommunity_token_unknown
;
387 if (separator
== 1) {
388 globaladmin
= localdata2
;
390 localdata1
= localdata2
;
397 localdata2
+= (*p
- '0');
402 *token
= lcommunity_token_unknown
;
407 * Copy the large comm.
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;
422 *token
= lcommunity_token_val
;
425 *token
= lcommunity_token_unknown
;
430 Convert string to large community attribute.
431 When type is already known, please specify both str and type.
433 When string includes keyword for each large community value.
434 Please specify keyword_included as non-zero value.
436 struct lcommunity
*lcommunity_str2com(const char *str
)
438 struct lcommunity
*lcom
= NULL
;
439 enum lcommunity_token token
= lcommunity_token_unknown
;
440 struct lcommunity_val lval
;
442 while ((str
= lcommunity_gettoken(str
, &lval
, &token
))) {
444 case lcommunity_token_val
:
446 lcom
= lcommunity_new();
447 lcommunity_add_val(lcom
, &lval
);
449 case lcommunity_token_unknown
:
452 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
*lcommerge
= NULL
;
557 struct lcommunity
*hb_lcommunity
= hb
->data
;
558 struct lcommunity
**aggr_lcommunity
= arg
;
560 if (*aggr_lcommunity
) {
561 lcommerge
= lcommunity_merge(*aggr_lcommunity
, hb_lcommunity
);
562 *aggr_lcommunity
= lcommunity_uniq_sort(lcommerge
);
563 lcommunity_free(&lcommerge
);
565 *aggr_lcommunity
= lcommunity_dup(hb_lcommunity
);
568 void bgp_aggr_lcommunity_remove(void *arg
)
570 struct lcommunity
*lcommunity
= arg
;
572 lcommunity_free(&lcommunity
);
575 void bgp_compute_aggregate_lcommunity(struct bgp_aggregate
*aggregate
,
576 struct lcommunity
*lcommunity
)
578 struct lcommunity
*aggr_lcommunity
= NULL
;
580 if ((aggregate
== NULL
) || (lcommunity
== NULL
))
583 /* Create hash if not already created.
585 if (aggregate
->lcommunity_hash
== NULL
)
586 aggregate
->lcommunity_hash
= hash_create(
587 lcommunity_hash_make
, lcommunity_cmp
,
588 "BGP Aggregator lcommunity hash");
590 aggr_lcommunity
= bgp_aggr_lcommunity_lookup(aggregate
, lcommunity
);
591 if (aggr_lcommunity
== NULL
) {
592 /* Insert lcommunity into hash.
594 aggr_lcommunity
= hash_get(aggregate
->lcommunity_hash
,
596 bgp_aggr_lcommunty_hash_alloc
);
598 /* Re-compute aggregate's lcommunity.
600 if (aggregate
->lcommunity
)
601 lcommunity_free(&aggregate
->lcommunity
);
603 hash_iterate(aggregate
->lcommunity_hash
,
604 bgp_aggr_lcommunity_prepare
,
605 &aggregate
->lcommunity
);
608 /* Increment refernce counter.
610 aggr_lcommunity
->refcnt
++;
613 void bgp_remove_lcommunity_from_aggregate(struct bgp_aggregate
*aggregate
,
614 struct lcommunity
*lcommunity
)
616 struct lcommunity
*aggr_lcommunity
= NULL
;
617 struct lcommunity
*ret_lcomm
= NULL
;
619 if ((aggregate
== NULL
) || (lcommunity
== NULL
))
622 if (aggregate
->lcommunity_hash
== NULL
)
625 /* Look-up the lcommunity in the hash.
627 aggr_lcommunity
= bgp_aggr_lcommunity_lookup(aggregate
, lcommunity
);
628 if (aggr_lcommunity
) {
629 aggr_lcommunity
->refcnt
--;
631 if (aggr_lcommunity
->refcnt
== 0) {
632 ret_lcomm
= hash_release(aggregate
->lcommunity_hash
,
634 lcommunity_free(&ret_lcomm
);
636 lcommunity_free(&aggregate
->lcommunity
);
638 /* Compute aggregate's lcommunity.
640 hash_iterate(aggregate
->lcommunity_hash
,
641 bgp_aggr_lcommunity_prepare
,
642 &aggregate
->lcommunity
);