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         uint8_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(uint8_t *pnt, unsigned 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 = XREALLOC(MTYPE_LCOMMUNITY_VAL, lcom1->val,
 178                                       lcom_length(lcom1) + lcom_length(lcom2));
 179         else
 180                 lcom1->val = XMALLOC(MTYPE_LCOMMUNITY_VAL,
 181                                      lcom_length(lcom1) + lcom_length(lcom2));
 182
 183         memcpy(lcom1->val + lcom_length(lcom1), lcom2->val, lcom_length(lcom2));
 184         lcom1->size += lcom2->size;
 185
 186         return lcom1;
 187 }
 188
 189 /* Intern Large Communities Attribute.  */
 190 struct lcommunity *lcommunity_intern(struct lcommunity *lcom)
 191 {
 192         struct lcommunity *find;
 193
 194         assert(lcom->refcnt == 0);
 195
 196         find = (struct lcommunity *)hash_get(lcomhash, lcom, hash_alloc_intern);
 197
 198         if (find != lcom)
 199                 lcommunity_free(&lcom);
 200
 201         find->refcnt++;
 202
 203         if (!find->str)
 204                 find->str =
 205                         lcommunity_lcom2str(find, LCOMMUNITY_FORMAT_DISPLAY);
 206
 207         return find;
 208 }
 209
 210 /* Unintern Large Communities Attribute.  */
 211 void lcommunity_unintern(struct lcommunity **lcom)
 212 {
 213         struct lcommunity *ret;
 214
 215         if ((*lcom)->refcnt)
 216                 (*lcom)->refcnt--;
 217
 218         /* Pull off from hash.  */
 219         if ((*lcom)->refcnt == 0) {
 220                 /* Large community must be in the hash.  */
 221                 ret = (struct lcommunity *)hash_release(lcomhash, *lcom);
 222                 assert(ret != NULL);
 223
 224                 lcommunity_free(lcom);
 225         }
 226 }
 227
 228 /* Utility function to make hash key.  */
 229 unsigned int lcommunity_hash_make(void *arg)
 230 {
 231         const struct lcommunity *lcom = arg;
 232         int size = lcom_length(lcom);
 233
 234         return jhash(lcom->val, size, 0xab125423);
 235 }
 236
 237 /* Compare two Large Communities Attribute structure.  */
 238 int lcommunity_cmp(const void *arg1, const void *arg2)
 239 {
 240         const struct lcommunity *lcom1 = arg1;
 241         const struct lcommunity *lcom2 = arg2;
 242
 243         return (lcom1->size == lcom2->size
 244                 && memcmp(lcom1->val, lcom2->val, lcom_length(lcom1)) == 0);
 245 }
 246
 247 /* Return communities hash.  */
 248 struct hash *lcommunity_hash(void)
 249 {
 250         return lcomhash;
 251 }
 252
 253 /* Initialize Large Comminities related hash. */
 254 void lcommunity_init(void)
 255 {
 256         lcomhash = hash_create(lcommunity_hash_make, lcommunity_cmp,
 257                                "BGP lcommunity hash");
 258 }
 259
 260 void lcommunity_finish(void)
 261 {
 262         hash_clean(lcomhash, (void (*)(void *))lcommunity_hash_free);
 263         hash_free(lcomhash);
 264         lcomhash = NULL;
 265 }
 266
 267 /* Large Communities token enum. */
 268 enum lcommunity_token {
 269         lcommunity_token_unknown = 0,
 270         lcommunity_token_val,
 271 };
 272
 273 /* Get next Large Communities token from the string. */
 274 static const char *lcommunity_gettoken(const char *str,
 275                                        struct lcommunity_val *lval,
 276                                        enum lcommunity_token *token)
 277 {
 278         const char *p = str;
 279
 280         /* Skip white space. */
 281         while (isspace((int)*p)) {
 282                 p++;
 283                 str++;
 284         }
 285
 286         /* Check the end of the line. */
 287         if (*p == '\0')
 288                 return NULL;
 289
 290         /* Community value. */
 291         if (isdigit((int)*p)) {
 292                 int separator = 0;
 293                 int digit = 0;
 294                 uint32_t globaladmin = 0;
 295                 uint32_t localdata1 = 0;
 296                 uint32_t localdata2 = 0;
 297
 298                 while (isdigit((int)*p) || *p == ':') {
 299                         if (*p == ':') {
 300                                 if (separator == 2) {
 301                                         *token = lcommunity_token_unknown;
 302                                         return NULL;
 303                                 } else {
 304                                         separator++;
 305                                         digit = 0;
 306                                         if (separator == 1) {
 307                                                 globaladmin = localdata2;
 308                                         } else {
 309                                                 localdata1 = localdata2;
 310                                         }
 311                                         localdata2 = 0;
 312                                 }
 313                         } else {
 314                                 digit = 1;
 315                                 localdata2 *= 10;
 316                                 localdata2 += (*p - '0');
 317                         }
 318                         p++;
 319                 }
 320                 if (!digit) {
 321                         *token = lcommunity_token_unknown;
 322                         return NULL;
 323                 }
 324
 325                 /*
 326                  * Copy the large comm.
 327                  */
 328                 lval->val[0] = (globaladmin >> 24) & 0xff;
 329                 lval->val[1] = (globaladmin >> 16) & 0xff;
 330                 lval->val[2] = (globaladmin >> 8) & 0xff;
 331                 lval->val[3] = globaladmin & 0xff;
 332                 lval->val[4] = (localdata1 >> 24) & 0xff;
 333                 lval->val[5] = (localdata1 >> 16) & 0xff;
 334                 lval->val[6] = (localdata1 >> 8) & 0xff;
 335                 lval->val[7] = localdata1 & 0xff;
 336                 lval->val[8] = (localdata2 >> 24) & 0xff;
 337                 lval->val[9] = (localdata2 >> 16) & 0xff;
 338                 lval->val[10] = (localdata2 >> 8) & 0xff;
 339                 lval->val[11] = localdata2 & 0xff;
 340
 341                 *token = lcommunity_token_val;
 342                 return p;
 343         }
 344         *token = lcommunity_token_unknown;
 345         return p;
 346 }
 347
 348 /*
 349   Convert string to large community attribute.
 350   When type is already known, please specify both str and type.
 351
 352   When string includes keyword for each large community value.
 353   Please specify keyword_included as non-zero value.
 354 */
 355 struct lcommunity *lcommunity_str2com(const char *str)
 356 {
 357         struct lcommunity *lcom = NULL;
 358         enum lcommunity_token token = lcommunity_token_unknown;
 359         struct lcommunity_val lval;
 360
 361         while ((str = lcommunity_gettoken(str, &lval, &token))) {
 362                 switch (token) {
 363                 case lcommunity_token_val:
 364                         if (lcom == NULL)
 365                                 lcom = lcommunity_new();
 366                         lcommunity_add_val(lcom, &lval);
 367                         break;
 368                 case lcommunity_token_unknown:
 369                 default:
 370                         if (lcom)
 371                                 lcommunity_free(&lcom);
 372                         return NULL;
 373                 }
 374         }
 375         return lcom;
 376 }
 377
 378 int lcommunity_include(struct lcommunity *lcom, uint8_t *ptr)
 379 {
 380         int i;
 381         uint8_t *lcom_ptr;
 382
 383         for (i = 0; i < lcom->size; i++) {
 384                 lcom_ptr = lcom->val + (i * LCOMMUNITY_SIZE);
 385                 if (memcmp(ptr, lcom_ptr, LCOMMUNITY_SIZE) == 0)
 386                         return 1;
 387         }
 388         return 0;
 389 }
 390
 391 /* Convert large community attribute to string.
 392    The large coms will be in 65535:65531:0 format.
 393 */
 394 char *lcommunity_lcom2str(struct lcommunity *lcom, int format)
 395 {
 396         int i;
 397         uint8_t *pnt;
 398 #define LCOMMUNITY_STR_DEFAULT_LEN  40
 399         int str_size;
 400         int str_pnt;
 401         char *str_buf;
 402         int len = 0;
 403         int first = 1;
 404         uint32_t globaladmin, localdata1, localdata2;
 405
 406         if (lcom->size == 0) {
 407                 str_buf = XMALLOC(MTYPE_LCOMMUNITY_STR, 1);
 408                 str_buf[0] = '\0';
 409                 return str_buf;
 410         }
 411
 412         /* Prepare buffer.  */
 413         str_buf = XMALLOC(MTYPE_LCOMMUNITY_STR, LCOMMUNITY_STR_DEFAULT_LEN + 1);
 414         str_size = LCOMMUNITY_STR_DEFAULT_LEN + 1;
 415         str_pnt = 0;
 416
 417         for (i = 0; i < lcom->size; i++) {
 418                 /* Make it sure size is enough.  */
 419                 while (str_pnt + LCOMMUNITY_STR_DEFAULT_LEN >= str_size) {
 420                         str_size *= 2;
 421                         str_buf = XREALLOC(MTYPE_LCOMMUNITY_STR, str_buf,
 422                                            str_size);
 423                 }
 424
 425                 /* Space between each value.  */
 426                 if (!first)
 427                         str_buf[str_pnt++] = ' ';
 428
 429                 pnt = lcom->val + (i * LCOMMUNITY_SIZE);
 430
 431                 pnt = ptr_get_be32(pnt, &globaladmin);
 432                 pnt = ptr_get_be32(pnt, &localdata1);
 433                 pnt = ptr_get_be32(pnt, &localdata2);
 434                 (void)pnt; /* consume value */
 435
 436                 len = sprintf(str_buf + str_pnt, "%u:%u:%u", globaladmin,
 437                               localdata1, localdata2);
 438                 str_pnt += len;
 439                 first = 0;
 440         }
 441         return str_buf;
 442 }
 443
 444 int lcommunity_match(const struct lcommunity *lcom1,
 445                      const struct lcommunity *lcom2)
 446 {
 447         int i = 0;
 448         int j = 0;
 449
 450         if (lcom1 == NULL && lcom2 == NULL)
 451                 return 1;
 452
 453         if (lcom1 == NULL || lcom2 == NULL)
 454                 return 0;
 455
 456         if (lcom1->size < lcom2->size)
 457                 return 0;
 458
 459         /* Every community on com2 needs to be on com1 for this to match */
 460         while (i < lcom1->size && j < lcom2->size) {
 461                 if (memcmp(lcom1->val + (i * LCOMMUNITY_SIZE),
 462                            lcom2->val + (j * LCOMMUNITY_SIZE), LCOMMUNITY_SIZE)
 463                     == 0)
 464                         j++;
 465                 i++;
 466         }
 467
 468         if (j == lcom2->size)
 469                 return 1;
 470         else
 471                 return 0;
 472 }
 473
 474 /* Delete one lcommunity. */
 475 void lcommunity_del_val(struct lcommunity *lcom, uint8_t *ptr)
 476 {
 477         int i = 0;
 478         int c = 0;
 479
 480         if (!lcom->val)
 481                 return;
 482
 483         while (i < lcom->size) {
 484                 if (memcmp(lcom->val + i * LCOMMUNITY_SIZE, ptr,
 485                            LCOMMUNITY_SIZE)
 486                     == 0) {
 487                         c = lcom->size - i - 1;
 488
 489                         if (c > 0)
 490                                 memmove(lcom->val + i * LCOMMUNITY_SIZE,
 491                                         lcom->val + (i + 1) * LCOMMUNITY_SIZE,
 492                                         c * LCOMMUNITY_SIZE);
 493
 494                         lcom->size--;
 495
 496                         if (lcom->size > 0)
 497                                 lcom->val =
 498                                         XREALLOC(MTYPE_LCOMMUNITY_VAL,
 499                                                  lcom->val, lcom_length(lcom));
 500                         else {
 501                                 XFREE(MTYPE_LCOMMUNITY_VAL, lcom->val);
 502                                 lcom->val = NULL;
 503                         }
 504                         return;
 505                 }
 506                 i++;
 507         }
 508 }