bgpd/bgp_lcommunity.c

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