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