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