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