bgpd/bgp_lcommunity.c

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