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