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