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