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