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 structure 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                                   bool translate_alias)
 180 {
 181         int i;
 182         int len;
 183         char *str_buf;
 184         const uint8_t *pnt;
 185         uint32_t global, local1, local2;
 186         json_object *json_lcommunity_list = NULL;
 187         json_object *json_string = NULL;
 188
 189         /* 3 32-bit integers, 2 colons, and a space */
 190 #define LCOMMUNITY_STRLEN (10 * 3 + 2 + 1)
 191
 192         if (!lcom)
 193                 return;
 194
 195         if (make_json) {
 196                 lcom->json = json_object_new_object();
 197                 json_lcommunity_list = json_object_new_array();
 198         }
 199
 200         if (lcom->size == 0) {
 201                 str_buf = XCALLOC(MTYPE_LCOMMUNITY_STR, 1);
 202
 203                 if (make_json) {
 204                         json_object_string_add(lcom->json, "string", "");
 205                         json_object_object_add(lcom->json, "list",
 206                                                json_lcommunity_list);
 207                 }
 208
 209                 lcom->str = str_buf;
 210                 return;
 211         }
 212
 213         /* 1 space + lcom->size lcom strings + null terminator */
 214         size_t str_buf_sz = BUFSIZ;
 215         str_buf = XCALLOC(MTYPE_LCOMMUNITY_STR, str_buf_sz);
 216
 217         for (i = 0; i < lcom->size; i++) {
 218                 if (i > 0)
 219                         strlcat(str_buf, " ", str_buf_sz);
 220
 221                 pnt = lcom->val + (i * LCOMMUNITY_SIZE);
 222                 pnt = ptr_get_be32(pnt, &global);
 223                 pnt = ptr_get_be32(pnt, &local1);
 224                 pnt = ptr_get_be32(pnt, &local2);
 225                 (void)pnt;
 226
 227                 char lcsb[LCOMMUNITY_STRLEN + 1];
 228
 229                 snprintf(lcsb, sizeof(lcsb), "%u:%u:%u", global, local1,
 230                          local2);
 231
 232                 const char *com2alias =
 233                         translate_alias ? bgp_community2alias(lcsb) : lcsb;
 234
 235                 len = strlcat(str_buf, com2alias, str_buf_sz);
 236                 assert((unsigned int)len < str_buf_sz);
 237
 238                 if (make_json) {
 239                         json_string = json_object_new_string(com2alias);
 240                         json_object_array_add(json_lcommunity_list,
 241                                               json_string);
 242                 }
 243         }
 244
 245         if (make_json) {
 246                 json_object_string_add(lcom->json, "string", str_buf);
 247                 json_object_object_add(lcom->json, "list",
 248                                        json_lcommunity_list);
 249         }
 250
 251         lcom->str = str_buf;
 252 }
 253
 254 /* Intern Large Communities Attribute.  */
 255 struct lcommunity *lcommunity_intern(struct lcommunity *lcom)
 256 {
 257         struct lcommunity *find;
 258
 259         assert(lcom->refcnt == 0);
 260
 261         find = (struct lcommunity *)hash_get(lcomhash, lcom, hash_alloc_intern);
 262
 263         if (find != lcom)
 264                 lcommunity_free(&lcom);
 265
 266         find->refcnt++;
 267
 268         if (!find->str)
 269                 set_lcommunity_string(find, false, true);
 270
 271         return find;
 272 }
 273
 274 /* Unintern Large Communities Attribute.  */
 275 void lcommunity_unintern(struct lcommunity **lcom)
 276 {
 277         struct lcommunity *ret;
 278
 279         if (!*lcom)
 280                 return;
 281
 282         if ((*lcom)->refcnt)
 283                 (*lcom)->refcnt--;
 284
 285         /* Pull off from hash.  */
 286         if ((*lcom)->refcnt == 0) {
 287                 /* Large community must be in the hash.  */
 288                 ret = (struct lcommunity *)hash_release(lcomhash, *lcom);
 289                 assert(ret != NULL);
 290
 291                 lcommunity_free(lcom);
 292         }
 293 }
 294
 295 /* Return string representation of lcommunities attribute. */
 296 char *lcommunity_str(struct lcommunity *lcom, bool make_json,
 297                      bool translate_alias)
 298 {
 299         if (!lcom)
 300                 return NULL;
 301
 302         if (make_json && !lcom->json && lcom->str)
 303                 XFREE(MTYPE_LCOMMUNITY_STR, lcom->str);
 304
 305         if (!lcom->str)
 306                 set_lcommunity_string(lcom, make_json, translate_alias);
 307
 308         return lcom->str;
 309 }
 310
 311 /* Utility function to make hash key.  */
 312 unsigned int lcommunity_hash_make(const void *arg)
 313 {
 314         const struct lcommunity *lcom = arg;
 315         int size = lcom_length(lcom);
 316
 317         return jhash(lcom->val, size, 0xab125423);
 318 }
 319
 320 /* Compare two Large Communities Attribute structure.  */
 321 bool lcommunity_cmp(const void *arg1, const void *arg2)
 322 {
 323         const struct lcommunity *lcom1 = arg1;
 324         const struct lcommunity *lcom2 = arg2;
 325
 326         if (lcom1 == NULL && lcom2 == NULL)
 327                 return true;
 328
 329         if (lcom1 == NULL || lcom2 == NULL)
 330                 return false;
 331
 332         return (lcom1->size == lcom2->size
 333                 && memcmp(lcom1->val, lcom2->val, lcom_length(lcom1)) == 0);
 334 }
 335
 336 /* Return communities hash.  */
 337 struct hash *lcommunity_hash(void)
 338 {
 339         return lcomhash;
 340 }
 341
 342 /* Initialize Large Comminities related hash. */
 343 void lcommunity_init(void)
 344 {
 345         lcomhash = hash_create(lcommunity_hash_make, lcommunity_cmp,
 346                                "BGP lcommunity hash");
 347 }
 348
 349 void lcommunity_finish(void)
 350 {
 351         hash_clean(lcomhash, (void (*)(void *))lcommunity_hash_free);
 352         hash_free(lcomhash);
 353         lcomhash = NULL;
 354 }
 355
 356 /* Get next Large Communities token from the string.
 357  * Assumes str is space-delimeted and describes 0 or more
 358  * valid large communities
 359  */
 360 static const char *lcommunity_gettoken(const char *str,
 361                                        struct lcommunity_val *lval)
 362 {
 363         const char *p = str;
 364
 365         /* Skip white space. */
 366         while (isspace((unsigned char)*p)) {
 367                 p++;
 368                 str++;
 369         }
 370
 371         /* Check the end of the line. */
 372         if (*p == '\0')
 373                 return NULL;
 374
 375         /* Community value. */
 376         int separator = 0;
 377         int digit = 0;
 378         uint32_t globaladmin = 0;
 379         uint32_t localdata1 = 0;
 380         uint32_t localdata2 = 0;
 381
 382         while (*p && *p != ' ') {
 383                 /* large community valid chars */
 384                 assert(isdigit((unsigned char)*p) || *p == ':');
 385
 386                 if (*p == ':') {
 387                         separator++;
 388                         digit = 0;
 389                         if (separator == 1) {
 390                                 globaladmin = localdata2;
 391                         } else {
 392                                 localdata1 = localdata2;
 393                         }
 394                         localdata2 = 0;
 395                 } else {
 396                         digit = 1;
 397                         /* left shift the accumulated value and add current
 398                          * digit
 399                          */
 400                         localdata2 *= 10;
 401                         localdata2 += (*p - '0');
 402                 }
 403                 p++;
 404         }
 405
 406         /* Assert str was a valid large community */
 407         assert(separator == 2 && digit == 1);
 408
 409         /*
 410          * Copy the large comm.
 411          */
 412         lval->val[0] = (globaladmin >> 24) & 0xff;
 413         lval->val[1] = (globaladmin >> 16) & 0xff;
 414         lval->val[2] = (globaladmin >> 8) & 0xff;
 415         lval->val[3] = globaladmin & 0xff;
 416         lval->val[4] = (localdata1 >> 24) & 0xff;
 417         lval->val[5] = (localdata1 >> 16) & 0xff;
 418         lval->val[6] = (localdata1 >> 8) & 0xff;
 419         lval->val[7] = localdata1 & 0xff;
 420         lval->val[8] = (localdata2 >> 24) & 0xff;
 421         lval->val[9] = (localdata2 >> 16) & 0xff;
 422         lval->val[10] = (localdata2 >> 8) & 0xff;
 423         lval->val[11] = localdata2 & 0xff;
 424
 425         return p;
 426 }
 427
 428 /*
 429   Convert string to large community attribute.
 430   When type is already known, please specify both str and type.
 431
 432   When string includes keyword for each large community value.
 433   Please specify keyword_included as non-zero value.
 434 */
 435 struct lcommunity *lcommunity_str2com(const char *str)
 436 {
 437         struct lcommunity *lcom = NULL;
 438         struct lcommunity_val lval;
 439
 440         if (!lcommunity_list_valid(str, LARGE_COMMUNITY_LIST_STANDARD))
 441                 return NULL;
 442
 443         do {
 444                 str = lcommunity_gettoken(str, &lval);
 445                 if (lcom == NULL)
 446                         lcom = lcommunity_new();
 447                 lcommunity_add_val(lcom, &lval);
 448         } while (str);
 449
 450         return lcom;
 451 }
 452
 453 bool lcommunity_include(struct lcommunity *lcom, uint8_t *ptr)
 454 {
 455         int i;
 456         uint8_t *lcom_ptr;
 457
 458         for (i = 0; i < lcom->size; i++) {
 459                 lcom_ptr = lcom->val + (i * LCOMMUNITY_SIZE);
 460                 if (memcmp(ptr, lcom_ptr, LCOMMUNITY_SIZE) == 0)
 461                         return true;
 462         }
 463         return false;
 464 }
 465
 466 bool lcommunity_match(const struct lcommunity *lcom1,
 467                       const struct lcommunity *lcom2)
 468 {
 469         int i = 0;
 470         int j = 0;
 471
 472         if (lcom1 == NULL && lcom2 == NULL)
 473                 return true;
 474
 475         if (lcom1 == NULL || lcom2 == NULL)
 476                 return false;
 477
 478         if (lcom1->size < lcom2->size)
 479                 return false;
 480
 481         /* Every community on com2 needs to be on com1 for this to match */
 482         while (i < lcom1->size && j < lcom2->size) {
 483                 if (memcmp(lcom1->val + (i * LCOMMUNITY_SIZE),
 484                            lcom2->val + (j * LCOMMUNITY_SIZE), LCOMMUNITY_SIZE)
 485                     == 0)
 486                         j++;
 487                 i++;
 488         }
 489
 490         if (j == lcom2->size)
 491                 return true;
 492         else
 493                 return false;
 494 }
 495
 496 /* Delete one lcommunity. */
 497 void lcommunity_del_val(struct lcommunity *lcom, uint8_t *ptr)
 498 {
 499         int i = 0;
 500         int c = 0;
 501
 502         if (!lcom->val)
 503                 return;
 504
 505         while (i < lcom->size) {
 506                 if (memcmp(lcom->val + i * LCOMMUNITY_SIZE, ptr,
 507                            LCOMMUNITY_SIZE)
 508                     == 0) {
 509                         c = lcom->size - i - 1;
 510
 511                         if (c > 0)
 512                                 memmove(lcom->val + i * LCOMMUNITY_SIZE,
 513                                         lcom->val + (i + 1) * LCOMMUNITY_SIZE,
 514                                         c * LCOMMUNITY_SIZE);
 515
 516                         lcom->size--;
 517
 518                         if (lcom->size > 0)
 519                                 lcom->val =
 520                                         XREALLOC(MTYPE_LCOMMUNITY_VAL,
 521                                                  lcom->val, lcom_length(lcom));
 522                         else {
 523                                 XFREE(MTYPE_LCOMMUNITY_VAL, lcom->val);
 524                         }
 525                         return;
 526                 }
 527                 i++;
 528         }
 529 }
 530
 531 static struct lcommunity *bgp_aggr_lcommunity_lookup(
 532                                                 struct bgp_aggregate *aggregate,
 533                                                 struct lcommunity *lcommunity)
 534 {
 535         return hash_lookup(aggregate->lcommunity_hash, lcommunity);
 536 }
 537
 538 static void *bgp_aggr_lcommunty_hash_alloc(void *p)
 539 {
 540         struct lcommunity *ref = (struct lcommunity *)p;
 541         struct lcommunity *lcommunity = NULL;
 542
 543         lcommunity = lcommunity_dup(ref);
 544         return lcommunity;
 545 }
 546
 547 static void bgp_aggr_lcommunity_prepare(struct hash_bucket *hb, void *arg)
 548 {
 549         struct lcommunity *hb_lcommunity = hb->data;
 550         struct lcommunity **aggr_lcommunity = arg;
 551
 552         if (*aggr_lcommunity)
 553                 *aggr_lcommunity = lcommunity_merge(*aggr_lcommunity,
 554                                                     hb_lcommunity);
 555         else
 556                 *aggr_lcommunity = lcommunity_dup(hb_lcommunity);
 557 }
 558
 559 void bgp_aggr_lcommunity_remove(void *arg)
 560 {
 561         struct lcommunity *lcommunity = arg;
 562
 563         lcommunity_free(&lcommunity);
 564 }
 565
 566 void bgp_compute_aggregate_lcommunity(struct bgp_aggregate *aggregate,
 567                                       struct lcommunity *lcommunity)
 568 {
 569
 570         bgp_compute_aggregate_lcommunity_hash(aggregate, lcommunity);
 571         bgp_compute_aggregate_lcommunity_val(aggregate);
 572 }
 573
 574 void bgp_compute_aggregate_lcommunity_hash(struct bgp_aggregate *aggregate,
 575                                            struct lcommunity *lcommunity)
 576 {
 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
 599         /* Increment reference counter.
 600          */
 601         aggr_lcommunity->refcnt++;
 602 }
 603
 604 void bgp_compute_aggregate_lcommunity_val(struct bgp_aggregate *aggregate)
 605 {
 606         struct lcommunity *lcommerge = NULL;
 607
 608         if (aggregate == NULL)
 609                 return;
 610
 611         /* Re-compute aggregate's lcommunity.
 612          */
 613         if (aggregate->lcommunity)
 614                 lcommunity_free(&aggregate->lcommunity);
 615         if (aggregate->lcommunity_hash &&
 616             aggregate->lcommunity_hash->count) {
 617                 hash_iterate(aggregate->lcommunity_hash,
 618                              bgp_aggr_lcommunity_prepare,
 619                              &aggregate->lcommunity);
 620                 lcommerge = aggregate->lcommunity;
 621                 aggregate->lcommunity = lcommunity_uniq_sort(lcommerge);
 622                 if (lcommerge)
 623                         lcommunity_free(&lcommerge);
 624         }
 625 }
 626
 627 void bgp_remove_lcommunity_from_aggregate(struct bgp_aggregate *aggregate,
 628                                           struct lcommunity *lcommunity)
 629 {
 630         struct lcommunity *aggr_lcommunity = NULL;
 631         struct lcommunity *ret_lcomm = NULL;
 632
 633         if ((!aggregate)
 634             || (!aggregate->lcommunity_hash)
 635             || (!lcommunity))
 636                 return;
 637
 638         /* Look-up the lcommunity in the hash.
 639          */
 640         aggr_lcommunity = bgp_aggr_lcommunity_lookup(aggregate, lcommunity);
 641         if (aggr_lcommunity) {
 642                 aggr_lcommunity->refcnt--;
 643
 644                 if (aggr_lcommunity->refcnt == 0) {
 645                         ret_lcomm = hash_release(aggregate->lcommunity_hash,
 646                                                  aggr_lcommunity);
 647                         lcommunity_free(&ret_lcomm);
 648
 649                         bgp_compute_aggregate_lcommunity_val(aggregate);
 650
 651                 }
 652         }
 653 }
 654
 655 void bgp_remove_lcomm_from_aggregate_hash(struct bgp_aggregate *aggregate,
 656                                           struct lcommunity *lcommunity)
 657 {
 658         struct lcommunity *aggr_lcommunity = NULL;
 659         struct lcommunity *ret_lcomm = NULL;
 660
 661         if ((!aggregate)
 662             || (!aggregate->lcommunity_hash)
 663             || (!lcommunity))
 664                 return;
 665
 666         /* Look-up the lcommunity in the hash.
 667          */
 668         aggr_lcommunity = bgp_aggr_lcommunity_lookup(aggregate, lcommunity);
 669         if (aggr_lcommunity) {
 670                 aggr_lcommunity->refcnt--;
 671
 672                 if (aggr_lcommunity->refcnt == 0) {
 673                         ret_lcomm = hash_release(aggregate->lcommunity_hash,
 674                                                  aggr_lcommunity);
 675                         lcommunity_free(&ret_lcomm);
 676                 }
 677         }
 678 }