bgpd/bgp_lcommunity.c

   1 /* BGP Large Communities Attribute
   2
   3 Copyright (C) 2016 Keyur Patel <keyur@arrcus.com>
   4
   5 This file is part of GNU Zebra.
   6
   7 GNU Zebra is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 2, or (at your option) any
  10 later version.
  11
  12 GNU Zebra is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU Zebra; see the file COPYING.  If not, write to the Free
  19 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include <zebra.h>
  23
  24 #include "hash.h"
  25 #include "memory.h"
  26 #include "prefix.h"
  27 #include "command.h"
  28 #include "filter.h"
  29
  30 #include "bgpd/bgpd.h"
  31 #include "bgpd/bgp_lcommunity.h"
  32 #include "bgpd/bgp_aspath.h"
  33
  34 /* Hash of community attribute. */
  35 static struct hash *lcomhash;
  36
  37 /* Allocate a new lcommunities.  */
  38 static struct lcommunity *
  39 lcommunity_new (void)
  40 {
  41   return (struct lcommunity *) XCALLOC (MTYPE_LCOMMUNITY,
  42                                         sizeof (struct lcommunity));
  43 }
  44
  45 /* Allocate lcommunities.  */
  46 void
  47 lcommunity_free (struct lcommunity **lcom)
  48 {
  49   if ((*lcom)->val)
  50     XFREE (MTYPE_LCOMMUNITY_VAL, (*lcom)->val);
  51   if ((*lcom)->str)
  52     XFREE (MTYPE_LCOMMUNITY_STR, (*lcom)->str);
  53   XFREE (MTYPE_LCOMMUNITY, *lcom);
  54   lcom = NULL;
  55 }
  56
  57 /* Add a new Large Communities value to Large Communities
  58    Attribute structure.  When the value is already exists in the
  59    structure, we don't add the value.  Newly added value is sorted by
  60    numerical order.  When the value is added to the structure return 1
  61    else return 0.  */
  62 static int
  63 lcommunity_add_val (struct lcommunity *lcom, struct lcommunity_val *lval)
  64 {
  65   u_int8_t *p;
  66   int ret;
  67   int c;
  68
  69   /* When this is fist value, just add it.  */
  70   if (lcom->val == NULL)
  71     {
  72       lcom->size++;
  73       lcom->val = XMALLOC (MTYPE_LCOMMUNITY_VAL, lcom_length (lcom));
  74       memcpy (lcom->val, lval->val, LCOMMUNITY_SIZE);
  75       return 1;
  76     }
  77
  78   /* If the value already exists in the structure return 0.  */
  79   c = 0;
  80   for (p = lcom->val; c < lcom->size; p += LCOMMUNITY_SIZE, c++)
  81     {
  82       ret = memcmp (p, lval->val, LCOMMUNITY_SIZE);
  83       if (ret == 0)
  84         return 0;
  85       if (ret > 0)
  86         break;
  87     }
  88
  89   /* Add the value to the structure with numerical sorting.  */
  90   lcom->size++;
  91   lcom->val = XREALLOC (MTYPE_LCOMMUNITY_VAL, lcom->val, lcom_length (lcom));
  92
  93   memmove (lcom->val + (c + 1) * LCOMMUNITY_SIZE,
  94            lcom->val + c * LCOMMUNITY_SIZE,
  95            (lcom->size - 1 - c) * LCOMMUNITY_SIZE);
  96   memcpy (lcom->val + c * LCOMMUNITY_SIZE, lval->val, LCOMMUNITY_SIZE);
  97
  98   return 1;
  99 }
 100
 101 /* This function takes pointer to Large Communites strucutre then
 102    create a new Large Communities structure by uniq and sort each
 103    Large Communities value.  */
 104 struct lcommunity *
 105 lcommunity_uniq_sort (struct lcommunity *lcom)
 106 {
 107   int i;
 108   struct lcommunity *new;
 109   struct lcommunity_val *lval;
 110
 111   if (! lcom)
 112     return NULL;
 113
 114   new = lcommunity_new ();
 115
 116   for (i = 0; i < lcom->size; i++)
 117     {
 118       lval = (struct lcommunity_val *) (lcom->val + (i * LCOMMUNITY_SIZE));
 119       lcommunity_add_val (new, lval);
 120     }
 121   return new;
 122 }
 123
 124 /* Parse Large Communites Attribute in BGP packet.  */
 125 struct lcommunity *
 126 lcommunity_parse (u_int8_t *pnt, u_short length)
 127 {
 128   struct lcommunity tmp;
 129   struct lcommunity *new;
 130
 131   /* Length check.  */
 132   if (length % LCOMMUNITY_SIZE)
 133     return NULL;
 134
 135   /* Prepare tmporary structure for making a new Large Communities
 136      Attribute.  */
 137   tmp.size = length / LCOMMUNITY_SIZE;
 138   tmp.val = pnt;
 139
 140   /* Create a new Large Communities Attribute by uniq and sort each
 141      Large Communities value  */
 142   new = lcommunity_uniq_sort (&tmp);
 143
 144   return lcommunity_intern (new);
 145 }
 146
 147 /* Duplicate the Large Communities Attribute structure.  */
 148 struct lcommunity *
 149 lcommunity_dup (struct lcommunity *lcom)
 150 {
 151   struct lcommunity *new;
 152
 153   new = XCALLOC (MTYPE_LCOMMUNITY, sizeof (struct lcommunity));
 154   new->size = lcom->size;
 155   if (new->size)
 156     {
 157       new->val = XMALLOC (MTYPE_LCOMMUNITY_VAL, lcom->size * LCOMMUNITY_SIZE);
 158       memcpy (new->val, lcom->val, lcom->size * LCOMMUNITY_SIZE);
 159     }
 160   else
 161     new->val = NULL;
 162   return new;
 163 }
 164
 165 /* Retrun string representation of communities attribute. */
 166 char *
 167 lcommunity_str (struct lcommunity *lcom)
 168 {
 169   if (! lcom->str)
 170     lcom->str = lcommunity_lcom2str (lcom, LCOMMUNITY_FORMAT_DISPLAY);
 171   return lcom->str;
 172 }
 173
 174 /* Merge two Large Communities Attribute structure.  */
 175 struct lcommunity *
 176 lcommunity_merge (struct lcommunity *lcom1, struct lcommunity *lcom2)
 177 {
 178   if (lcom1->val)
 179     lcom1->val = XREALLOC (MTYPE_LCOMMUNITY_VAL, lcom1->val,
 180                            (lcom1->size + lcom2->size) * LCOMMUNITY_SIZE);
 181   else
 182     lcom1->val = XMALLOC (MTYPE_LCOMMUNITY_VAL,
 183                           (lcom1->size + lcom2->size) * LCOMMUNITY_SIZE);
 184
 185   memcpy (lcom1->val + (lcom1->size * LCOMMUNITY_SIZE),
 186           lcom2->val, lcom2->size * LCOMMUNITY_SIZE);
 187   lcom1->size += lcom2->size;
 188
 189   return lcom1;
 190 }
 191
 192 /* Intern Large Communities Attribute.  */
 193 struct lcommunity *
 194 lcommunity_intern (struct lcommunity *lcom)
 195 {
 196   struct lcommunity *find;
 197
 198   assert (lcom->refcnt == 0);
 199
 200   find = (struct lcommunity *) hash_get (lcomhash, lcom, hash_alloc_intern);
 201
 202   if (find != lcom)
 203     lcommunity_free (&lcom);
 204
 205   find->refcnt++;
 206
 207   if (! find->str)
 208     find->str = lcommunity_lcom2str (find, LCOMMUNITY_FORMAT_DISPLAY);
 209
 210   return find;
 211 }
 212
 213 /* Unintern Large Communities Attribute.  */
 214 void
 215 lcommunity_unintern (struct lcommunity **lcom)
 216 {
 217   struct lcommunity *ret;
 218
 219   if ((*lcom)->refcnt)
 220     (*lcom)->refcnt--;
 221
 222   /* Pull off from hash.  */
 223   if ((*lcom)->refcnt == 0)
 224     {
 225       /* Large community must be in the hash.  */
 226       ret = (struct lcommunity *) hash_release (lcomhash, *lcom);
 227       assert (ret != NULL);
 228
 229       lcommunity_free (lcom);
 230     }
 231 }
 232
 233 /* Utility function to make hash key.  */
 234 unsigned int
 235 lcommunity_hash_make (void *arg)
 236 {
 237   const struct lcommunity *lcom = arg;
 238   int size = lcom->size * LCOMMUNITY_SIZE;
 239   u_int8_t *pnt = lcom->val;
 240   unsigned int key = 0;
 241   int c;
 242
 243   for (c = 0; c < size; c += LCOMMUNITY_SIZE)
 244     {
 245       key += pnt[c];
 246       key += pnt[c + 1];
 247       key += pnt[c + 2];
 248       key += pnt[c + 3];
 249       key += pnt[c + 4];
 250       key += pnt[c + 5];
 251       key += pnt[c + 6];
 252       key += pnt[c + 7];
 253       key += pnt[c + 8];
 254       key += pnt[c + 9];
 255       key += pnt[c + 10];
 256       key += pnt[c + 11];
 257     }
 258
 259   return key;
 260 }
 261
 262 /* Compare two Large Communities Attribute structure.  */
 263 int
 264 lcommunity_cmp (const void *arg1, const void *arg2)
 265 {
 266   const struct lcommunity *lcom1 = arg1;
 267   const struct lcommunity *lcom2 = arg2;
 268
 269   return (lcom1->size == lcom2->size
 270           && memcmp (lcom1->val, lcom2->val, lcom1->size * LCOMMUNITY_SIZE) == 0);
 271 }
 272
 273 /* Return communities hash.  */
 274 struct hash *
 275 lcommunity_hash (void)
 276 {
 277   return lcomhash;
 278 }
 279
 280 /* Initialize Large Comminities related hash. */
 281 void
 282 lcommunity_init (void)
 283 {
 284   lcomhash = hash_create (lcommunity_hash_make, lcommunity_cmp);
 285 }
 286
 287 void
 288 lcommunity_finish (void)
 289 {
 290   hash_free (lcomhash);
 291   lcomhash = NULL;
 292 }
 293
 294 /* Large Communities token enum. */
 295 enum lcommunity_token
 296 {
 297   lcommunity_token_unknown = 0,
 298   lcommunity_token_val,
 299 };
 300
 301 /* Get next Large Communities token from the string. */
 302 static const char *
 303 lcommunity_gettoken (const char *str, struct lcommunity_val *lval,
 304                      enum lcommunity_token *token)
 305 {
 306   const char *p = str;
 307
 308   /* Skip white space. */
 309   while (isspace ((int) *p))
 310     {
 311       p++;
 312       str++;
 313     }
 314
 315   /* Check the end of the line. */
 316   if (*p == '\0')
 317     return NULL;
 318
 319   /* Community value. */
 320   if (isdigit ((int) *p))
 321     {
 322       int separator = 0;
 323       int digit = 0;
 324       u_int32_t globaladmin = 0;
 325       u_int32_t localdata1 = 0;
 326       u_int32_t localdata2 = 0;
 327
 328       while (isdigit ((int) *p) || *p == ':')
 329         {
 330           if (*p == ':')
 331             {
 332               if (separator == 2)
 333                 {
 334                   *token = lcommunity_token_unknown;
 335                   return NULL;
 336                 }
 337               else
 338                 {
 339                   separator++;
 340                   digit = 0;
 341                   if (separator == 1) {
 342                     globaladmin = localdata2;
 343                   } else {
 344                     localdata1 = localdata2;
 345                   }
 346                   localdata2 = 0;
 347                 }
 348             }
 349           else
 350             {
 351               digit = 1;
 352               localdata2 *= 10;
 353               localdata2 += (*p - '0');
 354             }
 355           p++;
 356         }
 357       if (! digit)
 358         {
 359           *token = lcommunity_token_unknown;
 360           return NULL;
 361         }
 362
 363       /*
 364        * Copy the large comm.
 365        */
 366       lval->val[0] = (globaladmin >> 24) & 0xff;
 367       lval->val[1] = (globaladmin >> 16) & 0xff;
 368       lval->val[2] = (globaladmin >> 8) & 0xff;
 369       lval->val[3] = globaladmin & 0xff;
 370       lval->val[4] = (localdata1 >> 24) & 0xff;
 371       lval->val[5] = (localdata1 >> 16) & 0xff;
 372       lval->val[6] = (localdata1 >> 8) & 0xff;
 373       lval->val[7] = localdata1 & 0xff;
 374       lval->val[8] = (localdata2 >> 24) & 0xff;
 375       lval->val[9] = (localdata2 >> 16) & 0xff;
 376       lval->val[10] = (localdata2 >> 8) & 0xff;
 377       lval->val[11] = localdata2 & 0xff;
 378
 379       *token = lcommunity_token_val;
 380       return p;
 381     }
 382   *token = lcommunity_token_unknown;
 383   return p;
 384 }
 385
 386 /*
 387   Convert string to large community attribute.
 388   When type is already known, please specify both str and type.
 389
 390   When string includes keyword for each large community value.
 391   Please specify keyword_included as non-zero value.
 392 */
 393 struct lcommunity *
 394 lcommunity_str2com (const char *str)
 395 {
 396     struct lcommunity *lcom = NULL;
 397     enum lcommunity_token token = lcommunity_token_unknown;
 398     struct lcommunity_val lval;
 399
 400     while ((str = lcommunity_gettoken (str, &lval, &token)))
 401     {
 402         switch (token)
 403         {
 404             case lcommunity_token_val:
 405                 if (lcom == NULL)
 406                     lcom = lcommunity_new ();
 407                 lcommunity_add_val (lcom, &lval);
 408                 break;
 409             case lcommunity_token_unknown:
 410             default:
 411                 if (lcom)
 412                     lcommunity_free (&lcom);
 413                 return NULL;
 414         }
 415     }
 416     return lcom;
 417 }
 418
 419 int
 420 lcommunity_include (struct lcommunity *lcom, u_char *ptr)
 421 {
 422   int i;
 423   u_char *lcom_ptr;
 424
 425   for (i = 0; i < lcom->size; i++) {
 426     lcom_ptr = lcom->val + (i * LCOMMUNITY_SIZE);
 427     if (memcmp (ptr, lcom_ptr, LCOMMUNITY_SIZE) == 0)
 428       return 1;
 429   }
 430   return 0;
 431 }
 432
 433 /* Convert large community attribute to string.
 434    The large coms will be in 65535:65531:0 format.
 435 */
 436 char *
 437 lcommunity_lcom2str (struct lcommunity *lcom, int format)
 438 {
 439   int i;
 440   u_int8_t *pnt;
 441 #define LCOMMUNITY_STR_DEFAULT_LEN  40
 442   int str_size;
 443   int str_pnt;
 444   char *str_buf;
 445   int len = 0;
 446   int first = 1;
 447   u_int32_t  globaladmin, localdata1, localdata2;
 448
 449   if (lcom->size == 0)
 450     {
 451       str_buf = XMALLOC (MTYPE_LCOMMUNITY_STR, 1);
 452       str_buf[0] = '\0';
 453       return str_buf;
 454     }
 455
 456   /* Prepare buffer.  */
 457   str_buf = XMALLOC (MTYPE_LCOMMUNITY_STR, LCOMMUNITY_STR_DEFAULT_LEN + 1);
 458   str_size = LCOMMUNITY_STR_DEFAULT_LEN + 1;
 459   str_pnt = 0;
 460
 461   for (i = 0; i < lcom->size; i++)
 462     {
 463       /* Make it sure size is enough.  */
 464       while (str_pnt + LCOMMUNITY_STR_DEFAULT_LEN >= str_size)
 465         {
 466           str_size *= 2;
 467           str_buf = XREALLOC (MTYPE_LCOMMUNITY_STR, str_buf, str_size);
 468         }
 469
 470       /* Space between each value.  */
 471       if (! first)
 472         str_buf[str_pnt++] = ' ';
 473
 474       pnt = lcom->val + (i * 12);
 475
 476       globaladmin = (*pnt++ << 24);
 477       globaladmin |= (*pnt++ << 16);
 478       globaladmin |= (*pnt++ << 8);
 479       globaladmin |= (*pnt++);
 480
 481       localdata1 = (*pnt++ << 24);
 482       localdata1 |= (*pnt++ << 16);
 483       localdata1 |= (*pnt++ << 8);
 484       localdata1 |= (*pnt++);
 485
 486       localdata2 = (*pnt++ << 24);
 487       localdata2 |= (*pnt++ << 16);
 488       localdata2 |= (*pnt++ << 8);
 489       localdata2 |= (*pnt++);
 490
 491       len = sprintf( str_buf + str_pnt, "%u:%u:%u", globaladmin,
 492                      localdata1, localdata2);
 493       str_pnt += len;
 494       first = 0;
 495     }
 496   return str_buf;
 497 }
 498
 499 int
 500 lcommunity_match (const struct lcommunity *lcom1,
 501                   const struct lcommunity *lcom2)
 502 {
 503   int i = 0;
 504   int j = 0;
 505
 506   if (lcom1 == NULL && lcom2 == NULL)
 507     return 1;
 508
 509   if (lcom1 == NULL || lcom2 == NULL)
 510     return 0;
 511
 512   if (lcom1->size < lcom2->size)
 513     return 0;
 514
 515   /* Every community on com2 needs to be on com1 for this to match */
 516   while (i < lcom1->size && j < lcom2->size)
 517     {
 518       if (memcmp (lcom1->val + (i*12), lcom2->val + (j*12), LCOMMUNITY_SIZE) == 0)
 519         j++;
 520       i++;
 521     }
 522
 523   if (j == lcom2->size)
 524     return 1;
 525   else
 526     return 0;
 527 }
 528
 529 /* Delete one lcommunity. */
 530 void
 531 lcommunity_del_val (struct lcommunity *lcom, u_char *ptr)
 532 {
 533   int i = 0;
 534   int c = 0;
 535
 536   if (! lcom->val)
 537     return;
 538
 539   while (i < lcom->size)
 540     {
 541       if (memcmp (lcom->val + i*LCOMMUNITY_SIZE, ptr, LCOMMUNITY_SIZE) == 0)
 542         {
 543           c = lcom->size -i -1;
 544
 545           if (c > 0)
 546             memmove (lcom->val + i*LCOMMUNITY_SIZE, lcom->val + (i + 1)*LCOMMUNITY_SIZE, c * LCOMMUNITY_SIZE);
 547
 548           lcom->size--;
 549
 550           if (lcom->size > 0)
 551             lcom->val = XREALLOC (MTYPE_COMMUNITY_VAL, lcom->val,
 552                                  lcom_length (lcom));
 553           else
 554             {
 555               XFREE (MTYPE_COMMUNITY_VAL, lcom->val);
 556               lcom->val = NULL;
 557             }
 558           return;
 559         }
 560       i++;
 561     }
 562 }