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