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", json_community_list);
 226                 }
 227                 com->str = str;
 228                 return;
 229         }
 230
 231         /* Memory allocation is time consuming work.  So we calculate
 232            required string length first.  */
 233         len = 0;
 234
 235         for (i = 0; i < com->size; i++) {
 236                 memcpy(&comval, com_nthval(com, i), sizeof(u_int32_t));
 237                 comval = ntohl(comval);
 238
 239                 switch (comval) {
 240                 case COMMUNITY_INTERNET:
 241                         len += strlen(" internet");
 242                         break;
 243                 case COMMUNITY_NO_EXPORT:
 244                         len += strlen(" no-export");
 245                         break;
 246                 case COMMUNITY_NO_ADVERTISE:
 247                         len += strlen(" no-advertise");
 248                         break;
 249                 case COMMUNITY_LOCAL_AS:
 250                         len += strlen(" local-AS");
 251                         break;
 252                 case COMMUNITY_GSHUT:
 253                         len += strlen(" graceful-shutdown");
 254                         break;
 255                 default:
 256                         len += strlen(" 65536:65535");
 257                         break;
 258                 }
 259         }
 260
 261         /* Allocate memory.  */
 262         str = pnt = XMALLOC(MTYPE_COMMUNITY_STR, len);
 263         first = 1;
 264
 265         /* Fill in string.  */
 266         for (i = 0; i < com->size; i++) {
 267                 memcpy(&comval, com_nthval(com, i), sizeof(u_int32_t));
 268                 comval = ntohl(comval);
 269
 270                 if (first)
 271                         first = 0;
 272                 else
 273                         *pnt++ = ' ';
 274
 275                 switch (comval) {
 276                 case COMMUNITY_INTERNET:
 277                         strcpy(pnt, "internet");
 278                         pnt += strlen("internet");
 279                         if (make_json) {
 280                                 json_string = json_object_new_string("internet");
 281                                 json_object_array_add(json_community_list, json_string);
 282                         }
 283                         break;
 284                 case COMMUNITY_NO_EXPORT:
 285                         strcpy(pnt, "no-export");
 286                         pnt += strlen("no-export");
 287                         if (make_json) {
 288                                 json_string = json_object_new_string("noExport");
 289                                 json_object_array_add(json_community_list, json_string);
 290                         }
 291                         break;
 292                 case COMMUNITY_NO_ADVERTISE:
 293                         strcpy(pnt, "no-advertise");
 294                         pnt += strlen("no-advertise");
 295                         if (make_json) {
 296                                 json_string = json_object_new_string("noAdvertise");
 297                                 json_object_array_add(json_community_list, json_string);
 298                         }
 299                         break;
 300                 case COMMUNITY_LOCAL_AS:
 301                         strcpy(pnt, "local-AS");
 302                         pnt += strlen("local-AS");
 303                         if (make_json) {
 304                                 json_string = json_object_new_string("localAs");
 305                                 json_object_array_add(json_community_list, json_string);
 306                         }
 307                         break;
 308                 case COMMUNITY_GSHUT:
 309                         strcpy(pnt, "graceful-shutdown");
 310                         pnt += strlen("graceful-shutdown");
 311                         if (make_json) {
 312                                 json_string = json_object_new_string("gracefulShutdown");
 313                                 json_object_array_add(json_community_list, json_string);
 314                         }
 315                         break;
 316                 default:
 317                         as = (comval >> 16) & 0xFFFF;
 318                         val = comval & 0xFFFF;
 319                         sprintf(pnt, "%u:%d", as, val);
 320                         if (make_json) {
 321                                 json_string = json_object_new_string(pnt);
 322                                 json_object_array_add(json_community_list, json_string);
 323                         }
 324                         pnt += strlen(pnt);
 325                         break;
 326                 }
 327         }
 328         *pnt = '\0';
 329
 330         if (make_json) {
 331                 json_object_string_add(com->json, "string", str);
 332                 json_object_object_add(com->json, "list", json_community_list);
 333         }
 334         com->str = str;
 335 }
 336
 337 /* Intern communities attribute.  */
 338 struct community *community_intern(struct community *com)
 339 {
 340         struct community *find;
 341
 342         /* Assert this community structure is not interned. */
 343         assert(com->refcnt == 0);
 344
 345         /* Lookup community hash. */
 346         find = (struct community *)hash_get(comhash, com, hash_alloc_intern);
 347
 348         /* Arguemnt com is allocated temporary.  So when it is not used in
 349            hash, it should be freed.  */
 350         if (find != com)
 351                 community_free(com);
 352
 353         /* Increment refrence counter.  */
 354         find->refcnt++;
 355
 356         /* Make string.  */
 357         if (!find->str)
 358                 set_community_string(find, false);
 359
 360         return find;
 361 }
 362
 363 /* Free community attribute. */
 364 void community_unintern(struct community **com)
 365 {
 366         struct community *ret;
 367
 368         if ((*com)->refcnt)
 369                 (*com)->refcnt--;
 370
 371         /* Pull off from hash.  */
 372         if ((*com)->refcnt == 0) {
 373                 /* Community value com must exist in hash. */
 374                 ret = (struct community *)hash_release(comhash, *com);
 375                 assert(ret != NULL);
 376
 377                 community_free(*com);
 378                 *com = NULL;
 379         }
 380 }
 381
 382 /* Create new community attribute. */
 383 struct community *community_parse(u_int32_t *pnt, u_short length)
 384 {
 385         struct community tmp;
 386         struct community *new;
 387
 388         /* If length is malformed return NULL. */
 389         if (length % 4)
 390                 return NULL;
 391
 392         /* Make temporary community for hash look up. */
 393         tmp.size = length / 4;
 394         tmp.val = pnt;
 395
 396         new = community_uniq_sort(&tmp);
 397
 398         return community_intern(new);
 399 }
 400
 401 struct community *community_dup(struct community *com)
 402 {
 403         struct community *new;
 404
 405         new = XCALLOC(MTYPE_COMMUNITY, sizeof(struct community));
 406         new->size = com->size;
 407         if (new->size) {
 408                 new->val = XMALLOC(MTYPE_COMMUNITY_VAL, com->size * 4);
 409                 memcpy(new->val, com->val, com->size * 4);
 410         } else
 411                 new->val = NULL;
 412         return new;
 413 }
 414
 415 /* Retrun string representation of communities attribute. */
 416 char *community_str(struct community *com, bool make_json)
 417 {
 418         if (!com)
 419                 return NULL;
 420
 421         if (make_json && !com->json && com->str)
 422                 XFREE(MTYPE_COMMUNITY_STR, com->str);
 423
 424         if (!com->str)
 425                 set_community_string(com, make_json);
 426         return com->str;
 427 }
 428
 429 /* Make hash value of community attribute. This function is used by
 430    hash package.*/
 431 unsigned int community_hash_make(struct community *com)
 432 {
 433         u_int32_t *pnt = (u_int32_t *)com->val;
 434
 435         return jhash2(pnt, com->size, 0x43ea96c1);
 436 }
 437
 438 int community_match(const struct community *com1, const struct community *com2)
 439 {
 440         int i = 0;
 441         int j = 0;
 442
 443         if (com1 == NULL && com2 == NULL)
 444                 return 1;
 445
 446         if (com1 == NULL || com2 == NULL)
 447                 return 0;
 448
 449         if (com1->size < com2->size)
 450                 return 0;
 451
 452         /* Every community on com2 needs to be on com1 for this to match */
 453         while (i < com1->size && j < com2->size) {
 454                 if (memcmp(com1->val + i, com2->val + j, sizeof(u_int32_t))
 455                     == 0)
 456                         j++;
 457                 i++;
 458         }
 459
 460         if (j == com2->size)
 461                 return 1;
 462         else
 463                 return 0;
 464 }
 465
 466 /* If two aspath have same value then return 1 else return 0. This
 467    function is used by hash package. */
 468 int community_cmp(const struct community *com1, const struct community *com2)
 469 {
 470         if (com1 == NULL && com2 == NULL)
 471                 return 1;
 472         if (com1 == NULL || com2 == NULL)
 473                 return 0;
 474
 475         if (com1->size == com2->size)
 476                 if (memcmp(com1->val, com2->val, com1->size * 4) == 0)
 477                         return 1;
 478         return 0;
 479 }
 480
 481 /* Add com2 to the end of com1. */
 482 struct community *community_merge(struct community *com1,
 483                                   struct community *com2)
 484 {
 485         if (com1->val)
 486                 com1->val = XREALLOC(MTYPE_COMMUNITY_VAL, com1->val,
 487                                      (com1->size + com2->size) * 4);
 488         else
 489                 com1->val = XMALLOC(MTYPE_COMMUNITY_VAL,
 490                                     (com1->size + com2->size) * 4);
 491
 492         memcpy(com1->val + com1->size, com2->val, com2->size * 4);
 493         com1->size += com2->size;
 494
 495         return com1;
 496 }
 497
 498 /* Community token enum. */
 499 enum community_token {
 500         community_token_val,
 501         community_token_no_export,
 502         community_token_no_advertise,
 503         community_token_local_as,
 504         community_token_gshut,
 505         community_token_unknown
 506 };
 507
 508 /* Get next community token from string. */
 509 static const char *
 510 community_gettoken(const char *buf, enum community_token *token, u_int32_t *val)
 511 {
 512         const char *p = buf;
 513
 514         /* Skip white space. */
 515         while (isspace((int)*p))
 516                 p++;
 517
 518         /* Check the end of the line. */
 519         if (*p == '\0')
 520                 return NULL;
 521
 522         /* Well known community string check. */
 523         if (isalpha((int)*p)) {
 524                 if (strncmp(p, "internet", strlen("internet")) == 0) {
 525                         *val = COMMUNITY_INTERNET;
 526                         *token = community_token_no_export;
 527                         p += strlen("internet");
 528                         return p;
 529                 }
 530                 if (strncmp(p, "no-export", strlen("no-export")) == 0) {
 531                         *val = COMMUNITY_NO_EXPORT;
 532                         *token = community_token_no_export;
 533                         p += strlen("no-export");
 534                         return p;
 535                 }
 536                 if (strncmp(p, "no-advertise", strlen("no-advertise")) == 0) {
 537                         *val = COMMUNITY_NO_ADVERTISE;
 538                         *token = community_token_no_advertise;
 539                         p += strlen("no-advertise");
 540                         return p;
 541                 }
 542                 if (strncmp(p, "local-AS", strlen("local-AS")) == 0) {
 543                         *val = COMMUNITY_LOCAL_AS;
 544                         *token = community_token_local_as;
 545                         p += strlen("local-AS");
 546                         return p;
 547                 }
 548                 if (strncmp(p, "graceful-shutdown", strlen("graceful-shutdown")) == 0) {
 549                         *val = COMMUNITY_GSHUT;
 550                         *token = community_token_gshut;
 551                         p += strlen("graceful-shutdown");
 552                         return p;
 553                 }
 554
 555                 /* Unknown string. */
 556                 *token = community_token_unknown;
 557                 return NULL;
 558         }
 559
 560         /* Community value. */
 561         if (isdigit((int)*p)) {
 562                 int separator = 0;
 563                 int digit = 0;
 564                 u_int32_t community_low = 0;
 565                 u_int32_t community_high = 0;
 566
 567                 while (isdigit((int)*p) || *p == ':') {
 568                         if (*p == ':') {
 569                                 if (separator) {
 570                                         *token = community_token_unknown;
 571                                         return NULL;
 572                                 } else {
 573                                         separator = 1;
 574                                         digit = 0;
 575
 576                                         if (community_low > UINT16_MAX) {
 577                                                 *token =
 578                                                         community_token_unknown;
 579                                                 return NULL;
 580                                         }
 581
 582                                         community_high = community_low << 16;
 583                                         community_low = 0;
 584                                 }
 585                         } else {
 586                                 digit = 1;
 587                                 community_low *= 10;
 588                                 community_low += (*p - '0');
 589                         }
 590                         p++;
 591                 }
 592                 if (!digit) {
 593                         *token = community_token_unknown;
 594                         return NULL;
 595                 }
 596
 597                 if (community_low > UINT16_MAX) {
 598                         *token = community_token_unknown;
 599                         return NULL;
 600                 }
 601
 602                 *val = community_high + community_low;
 603                 *token = community_token_val;
 604                 return p;
 605         }
 606         *token = community_token_unknown;
 607         return NULL;
 608 }
 609
 610 /* convert string to community structure */
 611 struct community *community_str2com(const char *str)
 612 {
 613         struct community *com = NULL;
 614         struct community *com_sort = NULL;
 615         u_int32_t val = 0;
 616         enum community_token token = community_token_unknown;
 617
 618         do {
 619                 str = community_gettoken(str, &token, &val);
 620
 621                 switch (token) {
 622                 case community_token_val:
 623                 case community_token_no_export:
 624                 case community_token_no_advertise:
 625                 case community_token_local_as:
 626                 case community_token_gshut:
 627                         if (com == NULL) {
 628                                 com = community_new();
 629                                 com->json = NULL;
 630                         }
 631                         community_add_val(com, val);
 632                         break;
 633                 case community_token_unknown:
 634                 default:
 635                         if (com)
 636                                 community_free(com);
 637                         return NULL;
 638                 }
 639         } while (str);
 640
 641         if (!com)
 642                 return NULL;
 643
 644         com_sort = community_uniq_sort(com);
 645         community_free(com);
 646
 647         return com_sort;
 648 }
 649
 650 /* Return communities hash entry count.  */
 651 unsigned long community_count(void)
 652 {
 653         return comhash->count;
 654 }
 655
 656 /* Return communities hash.  */
 657 struct hash *community_hash(void)
 658 {
 659         return comhash;
 660 }
 661
 662 /* Initialize comminity related hash. */
 663 void community_init(void)
 664 {
 665         comhash = hash_create(
 666                 (unsigned int (*)(void *))community_hash_make,
 667                 (int (*)(const void *, const void *))community_cmp,
 668                 "BGP Community Hash");
 669 }
 670
 671 void community_finish(void)
 672 {
 673         hash_free(comhash);
 674         comhash = NULL;
 675 }