bgpd/bgp_community.c

   1 /* Community attribute related functions.
   2  * Copyright (C) 1998, 2001 Kunihiro Ishiguro
   3  *
   4  * This file is part of GNU Zebra.
   5  *
   6  * GNU Zebra is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the
   8  * Free Software Foundation; either version 2, or (at your option) any
   9  * later version.
  10  *
  11  * GNU Zebra is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more 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 "command.h"
  24 #include "hash.h"
  25 #include "memory.h"
  26 #include "jhash.h"
  27
  28 #include "bgpd/bgp_memory.h"
  29 #include "bgpd/bgp_community.h"
  30
  31 /* Hash of community attribute. */
  32 static struct hash *comhash;
  33
  34 /* Allocate a new communities value.  */
  35 static struct community *community_new(void)
  36 {
  37         return (struct community *)XCALLOC(MTYPE_COMMUNITY,
  38                                            sizeof(struct community));
  39 }
  40
  41 /* Free communities value.  */
  42 void community_free(struct community *com)
  43 {
  44         if (com->val)
  45                 XFREE(MTYPE_COMMUNITY_VAL, com->val);
  46         if (com->str)
  47                 XFREE(MTYPE_COMMUNITY_STR, com->str);
  48
  49         if (com->json) {
  50                 json_object_free(com->json);
  51                 com->json = NULL;
  52         }
  53
  54         XFREE(MTYPE_COMMUNITY, com);
  55 }
  56
  57 /* Add one community value to the community. */
  58 static void community_add_val(struct community *com, uint32_t val)
  59 {
  60         com->size++;
  61         if (com->val)
  62                 com->val = XREALLOC(MTYPE_COMMUNITY_VAL, com->val,
  63                                     com_length(com));
  64         else
  65                 com->val = XMALLOC(MTYPE_COMMUNITY_VAL, com_length(com));
  66
  67         val = htonl(val);
  68         memcpy(com_lastval(com), &val, sizeof(uint32_t));
  69 }
  70
  71 /* Delete one community. */
  72 void community_del_val(struct community *com, uint32_t *val)
  73 {
  74         int i = 0;
  75         int c = 0;
  76
  77         if (!com->val)
  78                 return;
  79
  80         while (i < com->size) {
  81                 if (memcmp(com->val + i, val, sizeof(uint32_t)) == 0) {
  82                         c = com->size - i - 1;
  83
  84                         if (c > 0)
  85                                 memmove(com->val + i, com->val + (i + 1),
  86                                         c * sizeof(*val));
  87
  88                         com->size--;
  89
  90                         if (com->size > 0)
  91                                 com->val = XREALLOC(MTYPE_COMMUNITY_VAL,
  92                                                     com->val, com_length(com));
  93                         else {
  94                                 XFREE(MTYPE_COMMUNITY_VAL, com->val);
  95                                 com->val = NULL;
  96                         }
  97                         return;
  98                 }
  99                 i++;
 100         }
 101 }
 102
 103 /* Delete all communities listed in com2 from com1 */
 104 struct community *community_delete(struct community *com1,
 105                                    struct community *com2)
 106 {
 107         int i = 0;
 108
 109         while (i < com2->size) {
 110                 community_del_val(com1, com2->val + i);
 111                 i++;
 112         }
 113
 114         return com1;
 115 }
 116
 117 /* Callback function from qsort(). */
 118 static int community_compare(const void *a1, const void *a2)
 119 {
 120         uint32_t v1;
 121         uint32_t v2;
 122
 123         memcpy(&v1, a1, sizeof(uint32_t));
 124         memcpy(&v2, a2, sizeof(uint32_t));
 125         v1 = ntohl(v1);
 126         v2 = ntohl(v2);
 127
 128         if (v1 < v2)
 129                 return -1;
 130         if (v1 > v2)
 131                 return 1;
 132         return 0;
 133 }
 134
 135 int community_include(struct community *com, uint32_t val)
 136 {
 137         int i;
 138
 139         val = htonl(val);
 140
 141         for (i = 0; i < com->size; i++)
 142                 if (memcmp(&val, com_nthval(com, i), sizeof(uint32_t)) == 0)
 143                         return 1;
 144
 145         return 0;
 146 }
 147
 148 uint32_t community_val_get(struct community *com, int i)
 149 {
 150         uint8_t *p;
 151         uint32_t val;
 152
 153         p = (uint8_t *)com->val;
 154         p += (i * 4);
 155
 156         memcpy(&val, p, sizeof(uint32_t));
 157
 158         return ntohl(val);
 159 }
 160
 161 /* Sort and uniq given community. */
 162 struct community *community_uniq_sort(struct community *com)
 163 {
 164         int i;
 165         struct community *new;
 166         uint32_t val;
 167
 168         if (!com)
 169                 return NULL;
 170
 171         new = community_new();
 172         new->json = NULL;
 173
 174         for (i = 0; i < com->size; i++) {
 175                 val = community_val_get(com, i);
 176
 177                 if (!community_include(new, val))
 178                         community_add_val(new, val);
 179         }
 180
 181         qsort(new->val, new->size, sizeof(uint32_t), community_compare);
 182
 183         return new;
 184 }
 185
 186 /* Convert communities attribute to string.
 187
 188    For Well-known communities value, below keyword is used.
 189
 190    0x0             "internet"
 191    0xFFFFFF01      "no-export"
 192    0xFFFFFF02      "no-advertise"
 193    0xFFFFFF03      "local-AS"
 194    0xFFFF0000      "graceful-shutdown"
 195
 196    For other values, "AS:VAL" format is used.  */
 197 static void set_community_string(struct community *com, bool make_json)
 198 {
 199         int i;
 200         char *str;
 201         char *pnt;
 202         int len;
 203         int first;
 204         uint32_t comval;
 205         uint16_t as;
 206         uint16_t val;
 207         json_object *json_community_list = NULL;
 208         json_object *json_string = NULL;
 209
 210         if (!com)
 211                 return;
 212
 213         if (make_json) {
 214                 com->json = json_object_new_object();
 215                 json_community_list = json_object_new_array();
 216         }
 217
 218         /* When communities attribute is empty.  */
 219         if (com->size == 0) {
 220                 str = XMALLOC(MTYPE_COMMUNITY_STR, 1);
 221                 str[0] = '\0';
 222
 223                 if (make_json) {
 224                         json_object_string_add(com->json, "string", "");
 225                         json_object_object_add(com->json, "list",
 226                                                json_community_list);
 227                 }
 228                 com->str = str;
 229                 return;
 230         }
 231
 232         /* Memory allocation is time consuming work.  So we calculate
 233            required string length first.  */
 234         len = 0;
 235
 236         for (i = 0; i < com->size; i++) {
 237                 memcpy(&comval, com_nthval(com, i), sizeof(uint32_t));
 238                 comval = ntohl(comval);
 239
 240                 switch (comval) {
 241                 case COMMUNITY_INTERNET:
 242                         len += strlen(" internet");
 243                         break;
 244                 case COMMUNITY_NO_EXPORT:
 245                         len += strlen(" no-export");
 246                         break;
 247                 case COMMUNITY_NO_ADVERTISE:
 248                         len += strlen(" no-advertise");
 249                         break;
 250                 case COMMUNITY_LOCAL_AS:
 251                         len += strlen(" local-AS");
 252                         break;
 253                 case COMMUNITY_GSHUT:
 254                         len += strlen(" graceful-shutdown");
 255                         break;
 256                 default:
 257                         len += strlen(" 65536:65535");
 258                         break;
 259                 }
 260         }
 261
 262         /* Allocate memory.  */
 263         str = pnt = XMALLOC(MTYPE_COMMUNITY_STR, len);
 264         first = 1;
 265
 266         /* Fill in string.  */
 267         for (i = 0; i < com->size; i++) {
 268                 memcpy(&comval, com_nthval(com, i), sizeof(uint32_t));
 269                 comval = ntohl(comval);
 270
 271                 if (first)
 272                         first = 0;
 273                 else
 274                         *pnt++ = ' ';
 275
 276                 switch (comval) {
 277                 case COMMUNITY_INTERNET:
 278                         strcpy(pnt, "internet");
 279                         pnt += strlen("internet");
 280                         if (make_json) {
 281                                 json_string =
 282                                         json_object_new_string("internet");
 283                                 json_object_array_add(json_community_list,
 284                                                       json_string);
 285                         }
 286                         break;
 287                 case COMMUNITY_NO_EXPORT:
 288                         strcpy(pnt, "no-export");
 289                         pnt += strlen("no-export");
 290                         if (make_json) {
 291                                 json_string =
 292                                         json_object_new_string("noExport");
 293                                 json_object_array_add(json_community_list,
 294                                                       json_string);
 295                         }
 296                         break;
 297                 case COMMUNITY_NO_ADVERTISE:
 298                         strcpy(pnt, "no-advertise");
 299                         pnt += strlen("no-advertise");
 300                         if (make_json) {
 301                                 json_string =
 302                                         json_object_new_string("noAdvertise");
 303                                 json_object_array_add(json_community_list,
 304                                                       json_string);
 305                         }
 306                         break;
 307                 case COMMUNITY_LOCAL_AS:
 308                         strcpy(pnt, "local-AS");
 309                         pnt += strlen("local-AS");
 310                         if (make_json) {
 311                                 json_string = json_object_new_string("localAs");
 312                                 json_object_array_add(json_community_list,
 313                                                       json_string);
 314                         }
 315                         break;
 316                 case COMMUNITY_GSHUT:
 317                         strcpy(pnt, "graceful-shutdown");
 318                         pnt += strlen("graceful-shutdown");
 319                         if (make_json) {
 320                                 json_string = json_object_new_string(
 321                                         "gracefulShutdown");
 322                                 json_object_array_add(json_community_list,
 323                                                       json_string);
 324                         }
 325                         break;
 326                 default:
 327                         as = (comval >> 16) & 0xFFFF;
 328                         val = comval & 0xFFFF;
 329                         sprintf(pnt, "%u:%d", as, val);
 330                         if (make_json) {
 331                                 json_string = json_object_new_string(pnt);
 332                                 json_object_array_add(json_community_list,
 333                                                       json_string);
 334                         }
 335                         pnt += strlen(pnt);
 336                         break;
 337                 }
 338         }
 339         *pnt = '\0';
 340
 341         if (make_json) {
 342                 json_object_string_add(com->json, "string", str);
 343                 json_object_object_add(com->json, "list", json_community_list);
 344         }
 345         com->str = str;
 346 }
 347
 348 /* Intern communities attribute.  */
 349 struct community *community_intern(struct community *com)
 350 {
 351         struct community *find;
 352
 353         /* Assert this community structure is not interned. */
 354         assert(com->refcnt == 0);
 355
 356         /* Lookup community hash. */
 357         find = (struct community *)hash_get(comhash, com, hash_alloc_intern);
 358
 359         /* Arguemnt com is allocated temporary.  So when it is not used in
 360            hash, it should be freed.  */
 361         if (find != com)
 362                 community_free(com);
 363
 364         /* Increment refrence counter.  */
 365         find->refcnt++;
 366
 367         /* Make string.  */
 368         if (!find->str)
 369                 set_community_string(find, false);
 370
 371         return find;
 372 }
 373
 374 /* Free community attribute. */
 375 void community_unintern(struct community **com)
 376 {
 377         struct community *ret;
 378
 379         if ((*com)->refcnt)
 380                 (*com)->refcnt--;
 381
 382         /* Pull off from hash.  */
 383         if ((*com)->refcnt == 0) {
 384                 /* Community value com must exist in hash. */
 385                 ret = (struct community *)hash_release(comhash, *com);
 386                 assert(ret != NULL);
 387
 388                 community_free(*com);
 389                 *com = NULL;
 390         }
 391 }
 392
 393 /* Create new community attribute. */
 394 struct community *community_parse(uint32_t *pnt, unsigned short length)
 395 {
 396         struct community tmp;
 397         struct community *new;
 398
 399         /* If length is malformed return NULL. */
 400         if (length % 4)
 401                 return NULL;
 402
 403         /* Make temporary community for hash look up. */
 404         tmp.size = length / 4;
 405         tmp.val = pnt;
 406
 407         new = community_uniq_sort(&tmp);
 408
 409         return community_intern(new);
 410 }
 411
 412 struct community *community_dup(struct community *com)
 413 {
 414         struct community *new;
 415
 416         new = XCALLOC(MTYPE_COMMUNITY, sizeof(struct community));
 417         new->size = com->size;
 418         if (new->size) {
 419                 new->val = XMALLOC(MTYPE_COMMUNITY_VAL, com->size * 4);
 420                 memcpy(new->val, com->val, com->size * 4);
 421         } else
 422                 new->val = NULL;
 423         return new;
 424 }
 425
 426 /* Retrun string representation of communities attribute. */
 427 char *community_str(struct community *com, bool make_json)
 428 {
 429         if (!com)
 430                 return NULL;
 431
 432         if (make_json && !com->json && com->str)
 433                 XFREE(MTYPE_COMMUNITY_STR, com->str);
 434
 435         if (!com->str)
 436                 set_community_string(com, make_json);
 437         return com->str;
 438 }
 439
 440 /* Make hash value of community attribute. This function is used by
 441    hash package.*/
 442 unsigned int community_hash_make(struct community *com)
 443 {
 444         uint32_t *pnt = (uint32_t *)com->val;
 445
 446         return jhash2(pnt, com->size, 0x43ea96c1);
 447 }
 448
 449 int community_match(const struct community *com1, const struct community *com2)
 450 {
 451         int i = 0;
 452         int j = 0;
 453
 454         if (com1 == NULL && com2 == NULL)
 455                 return 1;
 456
 457         if (com1 == NULL || com2 == NULL)
 458                 return 0;
 459
 460         if (com1->size < com2->size)
 461                 return 0;
 462
 463         /* Every community on com2 needs to be on com1 for this to match */
 464         while (i < com1->size && j < com2->size) {
 465                 if (memcmp(com1->val + i, com2->val + j, sizeof(uint32_t)) == 0)
 466                         j++;
 467                 i++;
 468         }
 469
 470         if (j == com2->size)
 471                 return 1;
 472         else
 473                 return 0;
 474 }
 475
 476 /* If two aspath have same value then return 1 else return 0. This
 477    function is used by hash package. */
 478 int community_cmp(const struct community *com1, const struct community *com2)
 479 {
 480         if (com1 == NULL && com2 == NULL)
 481                 return 1;
 482         if (com1 == NULL || com2 == NULL)
 483                 return 0;
 484
 485         if (com1->size == com2->size)
 486                 if (memcmp(com1->val, com2->val, com1->size * 4) == 0)
 487                         return 1;
 488         return 0;
 489 }
 490
 491 /* Add com2 to the end of com1. */
 492 struct community *community_merge(struct community *com1,
 493                                   struct community *com2)
 494 {
 495         if (com1->val)
 496                 com1->val = XREALLOC(MTYPE_COMMUNITY_VAL, com1->val,
 497                                      (com1->size + com2->size) * 4);
 498         else
 499                 com1->val = XMALLOC(MTYPE_COMMUNITY_VAL,
 500                                     (com1->size + com2->size) * 4);
 501
 502         memcpy(com1->val + com1->size, com2->val, com2->size * 4);
 503         com1->size += com2->size;
 504
 505         return com1;
 506 }
 507
 508 /* Community token enum. */
 509 enum community_token {
 510         community_token_val,
 511         community_token_no_export,
 512         community_token_no_advertise,
 513         community_token_local_as,
 514         community_token_gshut,
 515         community_token_unknown
 516 };
 517
 518 /* Get next community token from string. */
 519 static const char *
 520 community_gettoken(const char *buf, enum community_token *token, uint32_t *val)
 521 {
 522         const char *p = buf;
 523
 524         /* Skip white space. */
 525         while (isspace((int)*p))
 526                 p++;
 527
 528         /* Check the end of the line. */
 529         if (*p == '\0')
 530                 return NULL;
 531
 532         /* Well known community string check. */
 533         if (isalpha((int)*p)) {
 534                 if (strncmp(p, "internet", strlen("internet")) == 0) {
 535                         *val = COMMUNITY_INTERNET;
 536                         *token = community_token_no_export;
 537                         p += strlen("internet");
 538                         return p;
 539                 }
 540                 if (strncmp(p, "no-export", strlen("no-export")) == 0) {
 541                         *val = COMMUNITY_NO_EXPORT;
 542                         *token = community_token_no_export;
 543                         p += strlen("no-export");
 544                         return p;
 545                 }
 546                 if (strncmp(p, "no-advertise", strlen("no-advertise")) == 0) {
 547                         *val = COMMUNITY_NO_ADVERTISE;
 548                         *token = community_token_no_advertise;
 549                         p += strlen("no-advertise");
 550                         return p;
 551                 }
 552                 if (strncmp(p, "local-AS", strlen("local-AS")) == 0) {
 553                         *val = COMMUNITY_LOCAL_AS;
 554                         *token = community_token_local_as;
 555                         p += strlen("local-AS");
 556                         return p;
 557                 }
 558                 if (strncmp(p, "graceful-shutdown", strlen("graceful-shutdown"))
 559                     == 0) {
 560                         *val = COMMUNITY_GSHUT;
 561                         *token = community_token_gshut;
 562                         p += strlen("graceful-shutdown");
 563                         return p;
 564                 }
 565
 566                 /* Unknown string. */
 567                 *token = community_token_unknown;
 568                 return NULL;
 569         }
 570
 571         /* Community value. */
 572         if (isdigit((int)*p)) {
 573                 int separator = 0;
 574                 int digit = 0;
 575                 uint32_t community_low = 0;
 576                 uint32_t community_high = 0;
 577
 578                 while (isdigit((int)*p) || *p == ':') {
 579                         if (*p == ':') {
 580                                 if (separator) {
 581                                         *token = community_token_unknown;
 582                                         return NULL;
 583                                 } else {
 584                                         separator = 1;
 585                                         digit = 0;
 586
 587                                         if (community_low > UINT16_MAX) {
 588                                                 *token =
 589                                                         community_token_unknown;
 590                                                 return NULL;
 591                                         }
 592
 593                                         community_high = community_low << 16;
 594                                         community_low = 0;
 595                                 }
 596                         } else {
 597                                 digit = 1;
 598                                 community_low *= 10;
 599                                 community_low += (*p - '0');
 600                         }
 601                         p++;
 602                 }
 603                 if (!digit) {
 604                         *token = community_token_unknown;
 605                         return NULL;
 606                 }
 607
 608                 if (community_low > UINT16_MAX) {
 609                         *token = community_token_unknown;
 610                         return NULL;
 611                 }
 612
 613                 *val = community_high + community_low;
 614                 *token = community_token_val;
 615                 return p;
 616         }
 617         *token = community_token_unknown;
 618         return NULL;
 619 }
 620
 621 /* convert string to community structure */
 622 struct community *community_str2com(const char *str)
 623 {
 624         struct community *com = NULL;
 625         struct community *com_sort = NULL;
 626         uint32_t val = 0;
 627         enum community_token token = community_token_unknown;
 628
 629         do {
 630                 str = community_gettoken(str, &token, &val);
 631
 632                 switch (token) {
 633                 case community_token_val:
 634                 case community_token_no_export:
 635                 case community_token_no_advertise:
 636                 case community_token_local_as:
 637                 case community_token_gshut:
 638                         if (com == NULL) {
 639                                 com = community_new();
 640                                 com->json = NULL;
 641                         }
 642                         community_add_val(com, val);
 643                         break;
 644                 case community_token_unknown:
 645                 default:
 646                         if (com)
 647                                 community_free(com);
 648                         return NULL;
 649                 }
 650         } while (str);
 651
 652         if (!com)
 653                 return NULL;
 654
 655         com_sort = community_uniq_sort(com);
 656         community_free(com);
 657
 658         return com_sort;
 659 }
 660
 661 /* Return communities hash entry count.  */
 662 unsigned long community_count(void)
 663 {
 664         return comhash->count;
 665 }
 666
 667 /* Return communities hash.  */
 668 struct hash *community_hash(void)
 669 {
 670         return comhash;
 671 }
 672
 673 /* Initialize comminity related hash. */
 674 void community_init(void)
 675 {
 676         comhash =
 677                 hash_create((unsigned int (*)(void *))community_hash_make,
 678                             (int (*)(const void *, const void *))community_cmp,
 679                             "BGP Community Hash");
 680 }
 681
 682 void community_finish(void)
 683 {
 684         hash_free(comhash);
 685         comhash = NULL;
 686 }