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 bool lcommunity_cmp(const void *arg1, const void *arg2)
 317 {
 318         const struct lcommunity *lcom1 = arg1;
 319         const struct lcommunity *lcom2 = arg2;
 320
 321         if (lcom1 == NULL && lcom2 == NULL)
 322                 return 1;
 323
 324         if (lcom1 == NULL || lcom2 == NULL)
 325                 return 0;
 326
 327         return (lcom1->size == lcom2->size
 328                 && memcmp(lcom1->val, lcom2->val, lcom_length(lcom1)) == 0);
 329 }
 330
 331 /* Return communities hash.  */
 332 struct hash *lcommunity_hash(void)
 333 {
 334         return lcomhash;
 335 }
 336
 337 /* Initialize Large Comminities related hash. */
 338 void lcommunity_init(void)
 339 {
 340         lcomhash = hash_create(lcommunity_hash_make, lcommunity_cmp,
 341                                "BGP lcommunity hash");
 342 }
 343
 344 void lcommunity_finish(void)
 345 {
 346         hash_clean(lcomhash, (void (*)(void *))lcommunity_hash_free);
 347         hash_free(lcomhash);
 348         lcomhash = NULL;
 349 }
 350
 351 /* Large Communities token enum. */
 352 enum lcommunity_token {
 353         lcommunity_token_unknown = 0,
 354         lcommunity_token_val,
 355 };
 356
 357 /* Get next Large Communities token from the string. */
 358 static const char *lcommunity_gettoken(const char *str,
 359                                        struct lcommunity_val *lval,
 360                                        enum lcommunity_token *token)
 361 {
 362         const char *p = str;
 363
 364         /* Skip white space. */
 365         while (isspace((int)*p)) {
 366                 p++;
 367                 str++;
 368         }
 369
 370         /* Check the end of the line. */
 371         if (*p == '\0')
 372                 return NULL;
 373
 374         /* Community value. */
 375         if (isdigit((int)*p)) {
 376                 int separator = 0;
 377                 int digit = 0;
 378                 uint32_t globaladmin = 0;
 379                 uint32_t localdata1 = 0;
 380                 uint32_t localdata2 = 0;
 381
 382                 while (isdigit((int)*p) || *p == ':') {
 383                         if (*p == ':') {
 384                                 if (separator == 2) {
 385                                         *token = lcommunity_token_unknown;
 386                                         return NULL;
 387                                 } else {
 388                                         separator++;
 389                                         digit = 0;
 390                                         if (separator == 1) {
 391                                                 globaladmin = localdata2;
 392                                         } else {
 393                                                 localdata1 = localdata2;
 394                                         }
 395                                         localdata2 = 0;
 396                                 }
 397                         } else {
 398                                 digit = 1;
 399                                 localdata2 *= 10;
 400                                 localdata2 += (*p - '0');
 401                         }
 402                         p++;
 403                 }
 404                 if (!digit) {
 405                         *token = lcommunity_token_unknown;
 406                         return NULL;
 407                 }
 408
 409                 /*
 410                  * Copy the large comm.
 411                  */
 412                 lval->val[0] = (globaladmin >> 24) & 0xff;
 413                 lval->val[1] = (globaladmin >> 16) & 0xff;
 414                 lval->val[2] = (globaladmin >> 8) & 0xff;
 415                 lval->val[3] = globaladmin & 0xff;
 416                 lval->val[4] = (localdata1 >> 24) & 0xff;
 417                 lval->val[5] = (localdata1 >> 16) & 0xff;
 418                 lval->val[6] = (localdata1 >> 8) & 0xff;
 419                 lval->val[7] = localdata1 & 0xff;
 420                 lval->val[8] = (localdata2 >> 24) & 0xff;
 421                 lval->val[9] = (localdata2 >> 16) & 0xff;
 422                 lval->val[10] = (localdata2 >> 8) & 0xff;
 423                 lval->val[11] = localdata2 & 0xff;
 424
 425                 *token = lcommunity_token_val;
 426                 return p;
 427         }
 428         *token = lcommunity_token_unknown;
 429         return p;
 430 }
 431
 432 /*
 433   Convert string to large community attribute.
 434   When type is already known, please specify both str and type.
 435
 436   When string includes keyword for each large community value.
 437   Please specify keyword_included as non-zero value.
 438 */
 439 struct lcommunity *lcommunity_str2com(const char *str)
 440 {
 441         struct lcommunity *lcom = NULL;
 442         enum lcommunity_token token = lcommunity_token_unknown;
 443         struct lcommunity_val lval;
 444
 445         while ((str = lcommunity_gettoken(str, &lval, &token))) {
 446                 switch (token) {
 447                 case lcommunity_token_val:
 448                         if (lcom == NULL)
 449                                 lcom = lcommunity_new();
 450                         lcommunity_add_val(lcom, &lval);
 451                         break;
 452                 case lcommunity_token_unknown:
 453                 default:
 454                         if (lcom)
 455                                 lcommunity_free(&lcom);
 456                         return NULL;
 457                 }
 458         }
 459         return lcom;
 460 }
 461
 462 int lcommunity_include(struct lcommunity *lcom, uint8_t *ptr)
 463 {
 464         int i;
 465         uint8_t *lcom_ptr;
 466
 467         for (i = 0; i < lcom->size; i++) {
 468                 lcom_ptr = lcom->val + (i * LCOMMUNITY_SIZE);
 469                 if (memcmp(ptr, lcom_ptr, LCOMMUNITY_SIZE) == 0)
 470                         return 1;
 471         }
 472         return 0;
 473 }
 474
 475 int lcommunity_match(const struct lcommunity *lcom1,
 476                      const struct lcommunity *lcom2)
 477 {
 478         int i = 0;
 479         int j = 0;
 480
 481         if (lcom1 == NULL && lcom2 == NULL)
 482                 return 1;
 483
 484         if (lcom1 == NULL || lcom2 == NULL)
 485                 return 0;
 486
 487         if (lcom1->size < lcom2->size)
 488                 return 0;
 489
 490         /* Every community on com2 needs to be on com1 for this to match */
 491         while (i < lcom1->size && j < lcom2->size) {
 492                 if (memcmp(lcom1->val + (i * LCOMMUNITY_SIZE),
 493                            lcom2->val + (j * LCOMMUNITY_SIZE), LCOMMUNITY_SIZE)
 494                     == 0)
 495                         j++;
 496                 i++;
 497         }
 498
 499         if (j == lcom2->size)
 500                 return 1;
 501         else
 502                 return 0;
 503 }
 504
 505 /* Delete one lcommunity. */
 506 void lcommunity_del_val(struct lcommunity *lcom, uint8_t *ptr)
 507 {
 508         int i = 0;
 509         int c = 0;
 510
 511         if (!lcom->val)
 512                 return;
 513
 514         while (i < lcom->size) {
 515                 if (memcmp(lcom->val + i * LCOMMUNITY_SIZE, ptr,
 516                            LCOMMUNITY_SIZE)
 517                     == 0) {
 518                         c = lcom->size - i - 1;
 519
 520                         if (c > 0)
 521                                 memmove(lcom->val + i * LCOMMUNITY_SIZE,
 522                                         lcom->val + (i + 1) * LCOMMUNITY_SIZE,
 523                                         c * LCOMMUNITY_SIZE);
 524
 525                         lcom->size--;
 526
 527                         if (lcom->size > 0)
 528                                 lcom->val =
 529                                         XREALLOC(MTYPE_LCOMMUNITY_VAL,
 530                                                  lcom->val, lcom_length(lcom));
 531                         else {
 532                                 XFREE(MTYPE_LCOMMUNITY_VAL, lcom->val);
 533                                 lcom->val = NULL;
 534                         }
 535                         return;
 536                 }
 537                 i++;
 538         }
 539 }