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