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