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, u_int32_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(u_int32_t));
  69 }
  70
  71 /* Delete one community. */
  72 void community_del_val(struct community *com, u_int32_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(u_int32_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         u_int32_t v1;
 121         u_int32_t v2;
 122
 123         memcpy(&v1, a1, sizeof(u_int32_t));
 124         memcpy(&v2, a2, sizeof(u_int32_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, u_int32_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(u_int32_t)) == 0)
 143                         return 1;
 144
 145         return 0;
 146 }
 147
 148 u_int32_t community_val_get(struct community *com, int i)
 149 {
 150         u_char *p;
 151         u_int32_t val;
 152
 153         p = (u_char *)com->val;
 154         p += (i * 4);
 155
 156         memcpy(&val, p, sizeof(u_int32_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         u_int32_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(u_int32_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         u_int32_t comval;
 205         u_int16_t as;
 206         u_int16_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(u_int32_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(u_int32_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(u_int32_t *pnt, u_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         u_int32_t *pnt = (u_int32_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(u_int32_t))
 466                     == 0)
 467                         j++;
 468                 i++;
 469         }
 470
 471         if (j == com2->size)
 472                 return 1;
 473         else
 474                 return 0;
 475 }
 476
 477 /* If two aspath have same value then return 1 else return 0. This
 478    function is used by hash package. */
 479 int community_cmp(const struct community *com1, const struct community *com2)
 480 {
 481         if (com1 == NULL && com2 == NULL)
 482                 return 1;
 483         if (com1 == NULL || com2 == NULL)
 484                 return 0;
 485
 486         if (com1->size == com2->size)
 487                 if (memcmp(com1->val, com2->val, com1->size * 4) == 0)
 488                         return 1;
 489         return 0;
 490 }
 491
 492 /* Add com2 to the end of com1. */
 493 struct community *community_merge(struct community *com1,
 494                                   struct community *com2)
 495 {
 496         if (com1->val)
 497                 com1->val = XREALLOC(MTYPE_COMMUNITY_VAL, com1->val,
 498                                      (com1->size + com2->size) * 4);
 499         else
 500                 com1->val = XMALLOC(MTYPE_COMMUNITY_VAL,
 501                                     (com1->size + com2->size) * 4);
 502
 503         memcpy(com1->val + com1->size, com2->val, com2->size * 4);
 504         com1->size += com2->size;
 505
 506         return com1;
 507 }
 508
 509 /* Community token enum. */
 510 enum community_token {
 511         community_token_val,
 512         community_token_no_export,
 513         community_token_no_advertise,
 514         community_token_local_as,
 515         community_token_gshut,
 516         community_token_unknown
 517 };
 518
 519 /* Get next community token from string. */
 520 static const char *
 521 community_gettoken(const char *buf, enum community_token *token, u_int32_t *val)
 522 {
 523         const char *p = buf;
 524
 525         /* Skip white space. */
 526         while (isspace((int)*p))
 527                 p++;
 528
 529         /* Check the end of the line. */
 530         if (*p == '\0')
 531                 return NULL;
 532
 533         /* Well known community string check. */
 534         if (isalpha((int)*p)) {
 535                 if (strncmp(p, "internet", strlen("internet")) == 0) {
 536                         *val = COMMUNITY_INTERNET;
 537                         *token = community_token_no_export;
 538                         p += strlen("internet");
 539                         return p;
 540                 }
 541                 if (strncmp(p, "no-export", strlen("no-export")) == 0) {
 542                         *val = COMMUNITY_NO_EXPORT;
 543                         *token = community_token_no_export;
 544                         p += strlen("no-export");
 545                         return p;
 546                 }
 547                 if (strncmp(p, "no-advertise", strlen("no-advertise")) == 0) {
 548                         *val = COMMUNITY_NO_ADVERTISE;
 549                         *token = community_token_no_advertise;
 550                         p += strlen("no-advertise");
 551                         return p;
 552                 }
 553                 if (strncmp(p, "local-AS", strlen("local-AS")) == 0) {
 554                         *val = COMMUNITY_LOCAL_AS;
 555                         *token = community_token_local_as;
 556                         p += strlen("local-AS");
 557                         return p;
 558                 }
 559                 if (strncmp(p, "graceful-shutdown", strlen("graceful-shutdown"))
 560                     == 0) {
 561                         *val = COMMUNITY_GSHUT;
 562                         *token = community_token_gshut;
 563                         p += strlen("graceful-shutdown");
 564                         return p;
 565                 }
 566
 567                 /* Unknown string. */
 568                 *token = community_token_unknown;
 569                 return NULL;
 570         }
 571
 572         /* Community value. */
 573         if (isdigit((int)*p)) {
 574                 int separator = 0;
 575                 int digit = 0;
 576                 u_int32_t community_low = 0;
 577                 u_int32_t community_high = 0;
 578
 579                 while (isdigit((int)*p) || *p == ':') {
 580                         if (*p == ':') {
 581                                 if (separator) {
 582                                         *token = community_token_unknown;
 583                                         return NULL;
 584                                 } else {
 585                                         separator = 1;
 586                                         digit = 0;
 587
 588                                         if (community_low > UINT16_MAX) {
 589                                                 *token =
 590                                                         community_token_unknown;
 591                                                 return NULL;
 592                                         }
 593
 594                                         community_high = community_low << 16;
 595                                         community_low = 0;
 596                                 }
 597                         } else {
 598                                 digit = 1;
 599                                 community_low *= 10;
 600                                 community_low += (*p - '0');
 601                         }
 602                         p++;
 603                 }
 604                 if (!digit) {
 605                         *token = community_token_unknown;
 606                         return NULL;
 607                 }
 608
 609                 if (community_low > UINT16_MAX) {
 610                         *token = community_token_unknown;
 611                         return NULL;
 612                 }
 613
 614                 *val = community_high + community_low;
 615                 *token = community_token_val;
 616                 return p;
 617         }
 618         *token = community_token_unknown;
 619         return NULL;
 620 }
 621
 622 /* convert string to community structure */
 623 struct community *community_str2com(const char *str)
 624 {
 625         struct community *com = NULL;
 626         struct community *com_sort = NULL;
 627         u_int32_t val = 0;
 628         enum community_token token = community_token_unknown;
 629
 630         do {
 631                 str = community_gettoken(str, &token, &val);
 632
 633                 switch (token) {
 634                 case community_token_val:
 635                 case community_token_no_export:
 636                 case community_token_no_advertise:
 637                 case community_token_local_as:
 638                 case community_token_gshut:
 639                         if (com == NULL) {
 640                                 com = community_new();
 641                                 com->json = NULL;
 642                         }
 643                         community_add_val(com, val);
 644                         break;
 645                 case community_token_unknown:
 646                 default:
 647                         if (com)
 648                                 community_free(com);
 649                         return NULL;
 650                 }
 651         } while (str);
 652
 653         if (!com)
 654                 return NULL;
 655
 656         com_sort = community_uniq_sort(com);
 657         community_free(com);
 658
 659         return com_sort;
 660 }
 661
 662 /* Return communities hash entry count.  */
 663 unsigned long community_count(void)
 664 {
 665         return comhash->count;
 666 }
 667
 668 /* Return communities hash.  */
 669 struct hash *community_hash(void)
 670 {
 671         return comhash;
 672 }
 673
 674 /* Initialize comminity related hash. */
 675 void community_init(void)
 676 {
 677         comhash =
 678                 hash_create((unsigned int (*)(void *))community_hash_make,
 679                             (int (*)(const void *, const void *))community_cmp,
 680                             "BGP Community Hash");
 681 }
 682
 683 void community_finish(void)
 684 {
 685         hash_free(comhash);
 686         comhash = NULL;
 687 }