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