lib/nexthop.c

   1 /* A generic nexthop structure
   2  * Copyright (C) 2013 Cumulus Networks, Inc.
   3  *
   4  * This file is part of Quagga.
   5  *
   6  * Quagga is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the
   8  * Free Software Foundation; either version 2, or (at your option) any
   9  * later version.
  10  *
  11  * Quagga is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more 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 #include <zebra.h>
  21
  22 #include "prefix.h"
  23 #include "table.h"
  24 #include "memory.h"
  25 #include "command.h"
  26 #include "log.h"
  27 #include "sockunion.h"
  28 #include "linklist.h"
  29 #include "prefix.h"
  30 #include "nexthop.h"
  31 #include "mpls.h"
  32 #include "jhash.h"
  33 #include "printfrr.h"
  34 #include "vrf.h"
  35 #include "nexthop_group.h"
  36
  37 DEFINE_MTYPE_STATIC(LIB, NEXTHOP, "Nexthop");
  38 DEFINE_MTYPE_STATIC(LIB, NH_LABEL, "Nexthop label");
  39 DEFINE_MTYPE_STATIC(LIB, NH_SRV6, "Nexthop srv6");
  40
  41 static int _nexthop_labels_cmp(const struct nexthop *nh1,
  42                                const struct nexthop *nh2)
  43 {
  44         const struct mpls_label_stack *nhl1 = NULL;
  45         const struct mpls_label_stack *nhl2 = NULL;
  46
  47         nhl1 = nh1->nh_label;
  48         nhl2 = nh2->nh_label;
  49
  50         /* No labels is a match */
  51         if (!nhl1 && !nhl2)
  52                 return 0;
  53
  54         if (nhl1 && !nhl2)
  55                 return 1;
  56
  57         if (nhl2 && !nhl1)
  58                 return -1;
  59
  60         if (nhl1->num_labels > nhl2->num_labels)
  61                 return 1;
  62
  63         if (nhl1->num_labels < nhl2->num_labels)
  64                 return -1;
  65
  66         return memcmp(nhl1->label, nhl2->label,
  67                       (nhl1->num_labels * sizeof(mpls_label_t)));
  68 }
  69
  70 static int _nexthop_srv6_cmp(const struct nexthop *nh1,
  71                              const struct nexthop *nh2)
  72 {
  73         int ret = 0;
  74
  75         if (!nh1->nh_srv6 && !nh2->nh_srv6)
  76                 return 0;
  77
  78         if (nh1->nh_srv6 && !nh2->nh_srv6)
  79                 return 1;
  80
  81         if (!nh1->nh_srv6 && nh2->nh_srv6)
  82                 return -1;
  83
  84         if (nh1->nh_srv6->seg6local_action > nh2->nh_srv6->seg6local_action)
  85                 return 1;
  86
  87         if (nh2->nh_srv6->seg6local_action < nh1->nh_srv6->seg6local_action)
  88                 return -1;
  89
  90         ret = memcmp(&nh1->nh_srv6->seg6local_ctx,
  91                      &nh2->nh_srv6->seg6local_ctx,
  92                      sizeof(struct seg6local_context));
  93         if (ret != 0)
  94                 return ret;
  95
  96         ret = memcmp(&nh1->nh_srv6->seg6_segs,
  97                      &nh2->nh_srv6->seg6_segs,
  98                      sizeof(struct in6_addr));
  99
 100         return ret;
 101 }
 102
 103 int nexthop_g_addr_cmp(enum nexthop_types_t type, const union g_addr *addr1,
 104                        const union g_addr *addr2)
 105 {
 106         int ret = 0;
 107
 108         switch (type) {
 109         case NEXTHOP_TYPE_IPV4:
 110         case NEXTHOP_TYPE_IPV4_IFINDEX:
 111                 ret = IPV4_ADDR_CMP(&addr1->ipv4, &addr2->ipv4);
 112                 break;
 113         case NEXTHOP_TYPE_IPV6:
 114         case NEXTHOP_TYPE_IPV6_IFINDEX:
 115                 ret = IPV6_ADDR_CMP(&addr1->ipv6, &addr2->ipv6);
 116                 break;
 117         case NEXTHOP_TYPE_IFINDEX:
 118         case NEXTHOP_TYPE_BLACKHOLE:
 119                 /* No addr here */
 120                 break;
 121         }
 122
 123         return ret;
 124 }
 125
 126 static int _nexthop_gateway_cmp(const struct nexthop *nh1,
 127                                 const struct nexthop *nh2)
 128 {
 129         return nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
 130 }
 131
 132 static int _nexthop_source_cmp(const struct nexthop *nh1,
 133                                const struct nexthop *nh2)
 134 {
 135         return nexthop_g_addr_cmp(nh1->type, &nh1->src, &nh2->src);
 136 }
 137
 138 static int _nexthop_cmp_no_labels(const struct nexthop *next1,
 139                                   const struct nexthop *next2)
 140 {
 141         int ret = 0;
 142
 143         if (next1->vrf_id < next2->vrf_id)
 144                 return -1;
 145
 146         if (next1->vrf_id > next2->vrf_id)
 147                 return 1;
 148
 149         if (next1->type < next2->type)
 150                 return -1;
 151
 152         if (next1->type > next2->type)
 153                 return 1;
 154
 155         if (next1->weight < next2->weight)
 156                 return -1;
 157
 158         if (next1->weight > next2->weight)
 159                 return 1;
 160
 161         switch (next1->type) {
 162         case NEXTHOP_TYPE_IPV4:
 163         case NEXTHOP_TYPE_IPV6:
 164                 ret = _nexthop_gateway_cmp(next1, next2);
 165                 if (ret != 0)
 166                         return ret;
 167                 break;
 168         case NEXTHOP_TYPE_IPV4_IFINDEX:
 169         case NEXTHOP_TYPE_IPV6_IFINDEX:
 170                 ret = _nexthop_gateway_cmp(next1, next2);
 171                 if (ret != 0)
 172                         return ret;
 173                 /* Intentional Fall-Through */
 174         case NEXTHOP_TYPE_IFINDEX:
 175                 if (next1->ifindex < next2->ifindex)
 176                         return -1;
 177
 178                 if (next1->ifindex > next2->ifindex)
 179                         return 1;
 180                 break;
 181         case NEXTHOP_TYPE_BLACKHOLE:
 182                 if (next1->bh_type < next2->bh_type)
 183                         return -1;
 184
 185                 if (next1->bh_type > next2->bh_type)
 186                         return 1;
 187                 break;
 188         }
 189
 190         if (next1->srte_color < next2->srte_color)
 191                 return -1;
 192         if (next1->srte_color > next2->srte_color)
 193                 return 1;
 194
 195         ret = _nexthop_source_cmp(next1, next2);
 196         if (ret != 0)
 197                 goto done;
 198
 199         if (!CHECK_FLAG(next1->flags, NEXTHOP_FLAG_HAS_BACKUP) &&
 200             !CHECK_FLAG(next2->flags, NEXTHOP_FLAG_HAS_BACKUP))
 201                 return 0;
 202
 203         if (!CHECK_FLAG(next1->flags, NEXTHOP_FLAG_HAS_BACKUP) &&
 204             CHECK_FLAG(next2->flags, NEXTHOP_FLAG_HAS_BACKUP))
 205                 return -1;
 206
 207         if (CHECK_FLAG(next1->flags, NEXTHOP_FLAG_HAS_BACKUP) &&
 208             !CHECK_FLAG(next2->flags, NEXTHOP_FLAG_HAS_BACKUP))
 209                 return 1;
 210
 211         if (next1->backup_num == 0 && next2->backup_num == 0)
 212                 goto done;
 213
 214         if (next1->backup_num < next2->backup_num)
 215                 return -1;
 216
 217         if (next1->backup_num > next2->backup_num)
 218                 return 1;
 219
 220         ret = memcmp(next1->backup_idx,
 221                      next2->backup_idx, next1->backup_num);
 222
 223 done:
 224         return ret;
 225 }
 226
 227 int nexthop_cmp(const struct nexthop *next1, const struct nexthop *next2)
 228 {
 229         int ret = 0;
 230
 231         ret = _nexthop_cmp_no_labels(next1, next2);
 232         if (ret != 0)
 233                 return ret;
 234
 235         ret = _nexthop_labels_cmp(next1, next2);
 236         if (ret != 0)
 237                 return ret;
 238
 239         ret = _nexthop_srv6_cmp(next1, next2);
 240
 241         return ret;
 242 }
 243
 244 /*
 245  * More-limited comparison function used to detect duplicate
 246  * nexthops. This is used in places where we don't need the full
 247  * comparison of 'nexthop_cmp()'.
 248  */
 249 int nexthop_cmp_basic(const struct nexthop *nh1,
 250                       const struct nexthop *nh2)
 251 {
 252         int ret = 0;
 253         const struct mpls_label_stack *nhl1 = NULL;
 254         const struct mpls_label_stack *nhl2 = NULL;
 255
 256         if (nh1 == NULL && nh2 == NULL)
 257                 return 0;
 258
 259         if (nh1 && !nh2)
 260                 return 1;
 261
 262         if (!nh1 && nh2)
 263                 return -1;
 264
 265         if (nh1->vrf_id < nh2->vrf_id)
 266                 return -1;
 267
 268         if (nh1->vrf_id > nh2->vrf_id)
 269                 return 1;
 270
 271         if (nh1->type < nh2->type)
 272                 return -1;
 273
 274         if (nh1->type > nh2->type)
 275                 return 1;
 276
 277         if (nh1->weight < nh2->weight)
 278                 return -1;
 279
 280         if (nh1->weight > nh2->weight)
 281                 return 1;
 282
 283         switch (nh1->type) {
 284         case NEXTHOP_TYPE_IPV4:
 285         case NEXTHOP_TYPE_IPV6:
 286                 ret = nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
 287                 if (ret != 0)
 288                         return ret;
 289                 break;
 290         case NEXTHOP_TYPE_IPV4_IFINDEX:
 291         case NEXTHOP_TYPE_IPV6_IFINDEX:
 292                 ret = nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
 293                 if (ret != 0)
 294                         return ret;
 295                 /* Intentional Fall-Through */
 296         case NEXTHOP_TYPE_IFINDEX:
 297                 if (nh1->ifindex < nh2->ifindex)
 298                         return -1;
 299
 300                 if (nh1->ifindex > nh2->ifindex)
 301                         return 1;
 302                 break;
 303         case NEXTHOP_TYPE_BLACKHOLE:
 304                 if (nh1->bh_type < nh2->bh_type)
 305                         return -1;
 306
 307                 if (nh1->bh_type > nh2->bh_type)
 308                         return 1;
 309                 break;
 310         }
 311
 312         /* Compare source addr */
 313         ret = nexthop_g_addr_cmp(nh1->type, &nh1->src, &nh2->src);
 314         if (ret != 0)
 315                 goto done;
 316
 317         nhl1 = nh1->nh_label;
 318         nhl2 = nh2->nh_label;
 319
 320         /* No labels is a match */
 321         if (!nhl1 && !nhl2)
 322                 return 0;
 323
 324         if (nhl1 && !nhl2)
 325                 return 1;
 326
 327         if (nhl2 && !nhl1)
 328                 return -1;
 329
 330         if (nhl1->num_labels > nhl2->num_labels)
 331                 return 1;
 332
 333         if (nhl1->num_labels < nhl2->num_labels)
 334                 return -1;
 335
 336         ret = memcmp(nhl1->label, nhl2->label,
 337                      (nhl1->num_labels * sizeof(mpls_label_t)));
 338
 339 done:
 340         return ret;
 341 }
 342
 343 /*
 344  * nexthop_type_to_str
 345  */
 346 const char *nexthop_type_to_str(enum nexthop_types_t nh_type)
 347 {
 348         static const char *const desc[] = {
 349                 "none",          "Directly connected",
 350                 "IPv4 nexthop",  "IPv4 nexthop with ifindex",
 351                 "IPv6 nexthop",  "IPv6 nexthop with ifindex",
 352                 "Null0 nexthop",
 353         };
 354
 355         return desc[nh_type];
 356 }
 357
 358 /*
 359  * Check if the labels match for the 2 nexthops specified.
 360  */
 361 bool nexthop_labels_match(const struct nexthop *nh1, const struct nexthop *nh2)
 362 {
 363         if (_nexthop_labels_cmp(nh1, nh2) != 0)
 364                 return false;
 365
 366         return true;
 367 }
 368
 369 struct nexthop *nexthop_new(void)
 370 {
 371         struct nexthop *nh;
 372
 373         nh = XCALLOC(MTYPE_NEXTHOP, sizeof(struct nexthop));
 374
 375         /*
 376          * Default the weight to 1 here for all nexthops.
 377          * The linux kernel does some weird stuff with adding +1 to
 378          * all nexthop weights it gets over netlink.
 379          * To handle this, just default everything to 1 right from
 380          * from the beginning so we don't have to special case
 381          * default weights in the linux netlink code.
 382          *
 383          * 1 should be a valid on all platforms anyway.
 384          */
 385         nh->weight = 1;
 386
 387         return nh;
 388 }
 389
 390 /* Free nexthop. */
 391 void nexthop_free(struct nexthop *nexthop)
 392 {
 393         nexthop_del_labels(nexthop);
 394         nexthop_del_srv6_seg6local(nexthop);
 395         nexthop_del_srv6_seg6(nexthop);
 396         if (nexthop->resolved)
 397                 nexthops_free(nexthop->resolved);
 398         XFREE(MTYPE_NEXTHOP, nexthop);
 399 }
 400
 401 /* Frees a list of nexthops */
 402 void nexthops_free(struct nexthop *nexthop)
 403 {
 404         struct nexthop *nh, *next;
 405
 406         for (nh = nexthop; nh; nh = next) {
 407                 next = nh->next;
 408                 nexthop_free(nh);
 409         }
 410 }
 411
 412 bool nexthop_same(const struct nexthop *nh1, const struct nexthop *nh2)
 413 {
 414         if (nh1 && !nh2)
 415                 return false;
 416
 417         if (!nh1 && nh2)
 418                 return false;
 419
 420         if (nh1 == nh2)
 421                 return true;
 422
 423         if (nexthop_cmp(nh1, nh2) != 0)
 424                 return false;
 425
 426         return true;
 427 }
 428
 429 bool nexthop_same_no_labels(const struct nexthop *nh1,
 430                             const struct nexthop *nh2)
 431 {
 432         if (nh1 && !nh2)
 433                 return false;
 434
 435         if (!nh1 && nh2)
 436                 return false;
 437
 438         if (nh1 == nh2)
 439                 return true;
 440
 441         if (_nexthop_cmp_no_labels(nh1, nh2) != 0)
 442                 return false;
 443
 444         return true;
 445 }
 446
 447 /*
 448  * Allocate a new nexthop object and initialize it from various args.
 449  */
 450 struct nexthop *nexthop_from_ifindex(ifindex_t ifindex, vrf_id_t vrf_id)
 451 {
 452         struct nexthop *nexthop;
 453
 454         nexthop = nexthop_new();
 455         nexthop->type = NEXTHOP_TYPE_IFINDEX;
 456         nexthop->ifindex = ifindex;
 457         nexthop->vrf_id = vrf_id;
 458
 459         return nexthop;
 460 }
 461
 462 struct nexthop *nexthop_from_ipv4(const struct in_addr *ipv4,
 463                                   const struct in_addr *src,
 464                                   vrf_id_t vrf_id)
 465 {
 466         struct nexthop *nexthop;
 467
 468         nexthop = nexthop_new();
 469         nexthop->type = NEXTHOP_TYPE_IPV4;
 470         nexthop->vrf_id = vrf_id;
 471         nexthop->gate.ipv4 = *ipv4;
 472         if (src)
 473                 nexthop->src.ipv4 = *src;
 474
 475         return nexthop;
 476 }
 477
 478 struct nexthop *nexthop_from_ipv4_ifindex(const struct in_addr *ipv4,
 479                                           const struct in_addr *src,
 480                                           ifindex_t ifindex, vrf_id_t vrf_id)
 481 {
 482         struct nexthop *nexthop;
 483
 484         nexthop = nexthop_new();
 485         nexthop->type = NEXTHOP_TYPE_IPV4_IFINDEX;
 486         nexthop->vrf_id = vrf_id;
 487         nexthop->gate.ipv4 = *ipv4;
 488         if (src)
 489                 nexthop->src.ipv4 = *src;
 490         nexthop->ifindex = ifindex;
 491
 492         return nexthop;
 493 }
 494
 495 struct nexthop *nexthop_from_ipv6(const struct in6_addr *ipv6,
 496                                   vrf_id_t vrf_id)
 497 {
 498         struct nexthop *nexthop;
 499
 500         nexthop = nexthop_new();
 501         nexthop->vrf_id = vrf_id;
 502         nexthop->type = NEXTHOP_TYPE_IPV6;
 503         nexthop->gate.ipv6 = *ipv6;
 504
 505         return nexthop;
 506 }
 507
 508 struct nexthop *nexthop_from_ipv6_ifindex(const struct in6_addr *ipv6,
 509                                           ifindex_t ifindex, vrf_id_t vrf_id)
 510 {
 511         struct nexthop *nexthop;
 512
 513         nexthop = nexthop_new();
 514         nexthop->vrf_id = vrf_id;
 515         nexthop->type = NEXTHOP_TYPE_IPV6_IFINDEX;
 516         nexthop->gate.ipv6 = *ipv6;
 517         nexthop->ifindex = ifindex;
 518
 519         return nexthop;
 520 }
 521
 522 struct nexthop *nexthop_from_blackhole(enum blackhole_type bh_type,
 523                                        vrf_id_t nh_vrf_id)
 524 {
 525         struct nexthop *nexthop;
 526
 527         nexthop = nexthop_new();
 528         nexthop->vrf_id = nh_vrf_id;
 529         nexthop->type = NEXTHOP_TYPE_BLACKHOLE;
 530         nexthop->bh_type = bh_type;
 531
 532         return nexthop;
 533 }
 534
 535 /* Update nexthop with label information. */
 536 void nexthop_add_labels(struct nexthop *nexthop, enum lsp_types_t ltype,
 537                         uint8_t num_labels, const mpls_label_t *labels)
 538 {
 539         struct mpls_label_stack *nh_label;
 540         int i;
 541
 542         if (num_labels == 0)
 543                 return;
 544
 545         /* Enforce limit on label stack size */
 546         if (num_labels > MPLS_MAX_LABELS)
 547                 num_labels = MPLS_MAX_LABELS;
 548
 549         nexthop->nh_label_type = ltype;
 550
 551         nh_label = XCALLOC(MTYPE_NH_LABEL,
 552                            sizeof(struct mpls_label_stack)
 553                                    + num_labels * sizeof(mpls_label_t));
 554         nh_label->num_labels = num_labels;
 555         for (i = 0; i < num_labels; i++)
 556                 nh_label->label[i] = *(labels + i);
 557         nexthop->nh_label = nh_label;
 558 }
 559
 560 /* Free label information of nexthop, if present. */
 561 void nexthop_del_labels(struct nexthop *nexthop)
 562 {
 563         XFREE(MTYPE_NH_LABEL, nexthop->nh_label);
 564         nexthop->nh_label_type = ZEBRA_LSP_NONE;
 565 }
 566
 567 void nexthop_add_srv6_seg6local(struct nexthop *nexthop, uint32_t action,
 568                                 const struct seg6local_context *ctx)
 569 {
 570         if (action == ZEBRA_SEG6_LOCAL_ACTION_UNSPEC)
 571                 return;
 572
 573         if (!nexthop->nh_srv6)
 574                 nexthop->nh_srv6 = XCALLOC(MTYPE_NH_SRV6,
 575                                            sizeof(struct nexthop_srv6));
 576
 577         nexthop->nh_srv6->seg6local_action = action;
 578         nexthop->nh_srv6->seg6local_ctx = *ctx;
 579 }
 580
 581 void nexthop_del_srv6_seg6local(struct nexthop *nexthop)
 582 {
 583         if (!nexthop->nh_srv6)
 584                 return;
 585
 586         nexthop->nh_srv6->seg6local_action = ZEBRA_SEG6_LOCAL_ACTION_UNSPEC;
 587
 588         if (sid_zero(&nexthop->nh_srv6->seg6_segs))
 589                 XFREE(MTYPE_NH_SRV6, nexthop->nh_srv6);
 590 }
 591
 592 void nexthop_add_srv6_seg6(struct nexthop *nexthop,
 593                            const struct in6_addr *segs)
 594 {
 595         if (!segs)
 596                 return;
 597
 598         if (!nexthop->nh_srv6)
 599                 nexthop->nh_srv6 = XCALLOC(MTYPE_NH_SRV6,
 600                                            sizeof(struct nexthop_srv6));
 601
 602         nexthop->nh_srv6->seg6_segs = *segs;
 603 }
 604
 605 void nexthop_del_srv6_seg6(struct nexthop *nexthop)
 606 {
 607         if (!nexthop->nh_srv6)
 608                 return;
 609
 610         memset(&nexthop->nh_srv6->seg6_segs, 0,
 611                sizeof(nexthop->nh_srv6->seg6_segs));
 612
 613         if (nexthop->nh_srv6->seg6local_action ==
 614             ZEBRA_SEG6_LOCAL_ACTION_UNSPEC)
 615                 XFREE(MTYPE_NH_SRV6, nexthop->nh_srv6);
 616 }
 617
 618 const char *nexthop2str(const struct nexthop *nexthop, char *str, int size)
 619 {
 620         switch (nexthop->type) {
 621         case NEXTHOP_TYPE_IFINDEX:
 622                 snprintf(str, size, "if %u", nexthop->ifindex);
 623                 break;
 624         case NEXTHOP_TYPE_IPV4:
 625         case NEXTHOP_TYPE_IPV4_IFINDEX:
 626                 snprintfrr(str, size, "%pI4 if %u", &nexthop->gate.ipv4,
 627                            nexthop->ifindex);
 628                 break;
 629         case NEXTHOP_TYPE_IPV6:
 630         case NEXTHOP_TYPE_IPV6_IFINDEX:
 631                 snprintfrr(str, size, "%pI6 if %u", &nexthop->gate.ipv6,
 632                            nexthop->ifindex);
 633                 break;
 634         case NEXTHOP_TYPE_BLACKHOLE:
 635                 snprintf(str, size, "blackhole");
 636                 break;
 637         default:
 638                 snprintf(str, size, "unknown");
 639                 break;
 640         }
 641
 642         return str;
 643 }
 644
 645 /*
 646  * Iteration step for ALL_NEXTHOPS macro:
 647  * This is the tricky part. Check if `nexthop' has
 648  * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has
 649  * at least one nexthop attached to `nexthop->resolved', which will be
 650  * the next one.
 651  *
 652  * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
 653  * current chain. In case its current chain end is reached, it will move
 654  * upwards in the recursion levels and progress there. Whenever a step
 655  * forward in a chain is done, recursion will be checked again.
 656  * In a nustshell, it's equivalent to a pre-traversal order assuming that
 657  * left branch is 'resolved' and right branch is 'next':
 658  * https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg
 659  */
 660 struct nexthop *nexthop_next(const struct nexthop *nexthop)
 661 {
 662         if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
 663                 return nexthop->resolved;
 664
 665         if (nexthop->next)
 666                 return nexthop->next;
 667
 668         for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
 669                 if (par->next)
 670                         return par->next;
 671
 672         return NULL;
 673 }
 674
 675 /* Return the next nexthop in the tree that is resolved and active */
 676 struct nexthop *nexthop_next_active_resolved(const struct nexthop *nexthop)
 677 {
 678         struct nexthop *next = nexthop_next(nexthop);
 679
 680         while (next
 681                && (CHECK_FLAG(next->flags, NEXTHOP_FLAG_RECURSIVE)
 682                    || !CHECK_FLAG(next->flags, NEXTHOP_FLAG_ACTIVE)))
 683                 next = nexthop_next(next);
 684
 685         return next;
 686 }
 687
 688 unsigned int nexthop_level(const struct nexthop *nexthop)
 689 {
 690         unsigned int rv = 0;
 691
 692         for (const struct nexthop *par = nexthop->rparent;
 693              par; par = par->rparent)
 694                 rv++;
 695
 696         return rv;
 697 }
 698
 699 /* Only hash word-sized things, let cmp do the rest. */
 700 uint32_t nexthop_hash_quick(const struct nexthop *nexthop)
 701 {
 702         uint32_t key = 0x45afe398;
 703         int i;
 704
 705         key = jhash_3words(nexthop->type, nexthop->vrf_id,
 706                            nexthop->nh_label_type, key);
 707
 708         if (nexthop->nh_label) {
 709                 int labels = nexthop->nh_label->num_labels;
 710
 711                 i = 0;
 712
 713                 while (labels >= 3) {
 714                         key = jhash_3words(nexthop->nh_label->label[i],
 715                                            nexthop->nh_label->label[i + 1],
 716                                            nexthop->nh_label->label[i + 2],
 717                                            key);
 718                         labels -= 3;
 719                         i += 3;
 720                 }
 721
 722                 if (labels >= 2) {
 723                         key = jhash_2words(nexthop->nh_label->label[i],
 724                                            nexthop->nh_label->label[i + 1],
 725                                            key);
 726                         labels -= 2;
 727                         i += 2;
 728                 }
 729
 730                 if (labels >= 1)
 731                         key = jhash_1word(nexthop->nh_label->label[i], key);
 732         }
 733
 734         key = jhash_2words(nexthop->ifindex,
 735                            CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK),
 736                            key);
 737
 738         /* Include backup nexthops, if present */
 739         if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_HAS_BACKUP)) {
 740                 int backups = nexthop->backup_num;
 741
 742                 i = 0;
 743
 744                 while (backups >= 3) {
 745                         key = jhash_3words(nexthop->backup_idx[i],
 746                                            nexthop->backup_idx[i + 1],
 747                                            nexthop->backup_idx[i + 2], key);
 748                         backups -= 3;
 749                         i += 3;
 750                 }
 751
 752                 while (backups >= 2) {
 753                         key = jhash_2words(nexthop->backup_idx[i],
 754                                            nexthop->backup_idx[i + 1], key);
 755                         backups -= 2;
 756                         i += 2;
 757                 }
 758
 759                 if (backups >= 1)
 760                         key = jhash_1word(nexthop->backup_idx[i], key);
 761         }
 762
 763         if (nexthop->nh_srv6) {
 764                 key = jhash_1word(nexthop->nh_srv6->seg6local_action, key);
 765                 key = jhash(&nexthop->nh_srv6->seg6local_ctx,
 766                             sizeof(nexthop->nh_srv6->seg6local_ctx), key);
 767                 key = jhash(&nexthop->nh_srv6->seg6_segs,
 768                             sizeof(nexthop->nh_srv6->seg6_segs), key);
 769         }
 770
 771         return key;
 772 }
 773
 774
 775 #define GATE_SIZE 4 /* Number of uint32_t words in struct g_addr */
 776
 777 /* For a more granular hash */
 778 uint32_t nexthop_hash(const struct nexthop *nexthop)
 779 {
 780         uint32_t gate_src_rmap_raw[GATE_SIZE * 3] = {};
 781         /* Get all the quick stuff */
 782         uint32_t key = nexthop_hash_quick(nexthop);
 783
 784         assert(((sizeof(nexthop->gate) + sizeof(nexthop->src)
 785                  + sizeof(nexthop->rmap_src))
 786                 / 3)
 787                == (GATE_SIZE * sizeof(uint32_t)));
 788
 789         memcpy(gate_src_rmap_raw, &nexthop->gate, GATE_SIZE);
 790         memcpy(gate_src_rmap_raw + GATE_SIZE, &nexthop->src, GATE_SIZE);
 791         memcpy(gate_src_rmap_raw + (2 * GATE_SIZE), &nexthop->rmap_src,
 792                GATE_SIZE);
 793
 794         key = jhash2(gate_src_rmap_raw, (GATE_SIZE * 3), key);
 795
 796         return key;
 797 }
 798
 799 void nexthop_copy_no_recurse(struct nexthop *copy,
 800                              const struct nexthop *nexthop,
 801                              struct nexthop *rparent)
 802 {
 803         copy->vrf_id = nexthop->vrf_id;
 804         copy->ifindex = nexthop->ifindex;
 805         copy->type = nexthop->type;
 806         copy->flags = nexthop->flags;
 807         copy->weight = nexthop->weight;
 808
 809         assert(nexthop->backup_num < NEXTHOP_MAX_BACKUPS);
 810         copy->backup_num = nexthop->backup_num;
 811         if (copy->backup_num > 0)
 812                 memcpy(copy->backup_idx, nexthop->backup_idx, copy->backup_num);
 813
 814         copy->srte_color = nexthop->srte_color;
 815         memcpy(&copy->gate, &nexthop->gate, sizeof(nexthop->gate));
 816         memcpy(&copy->src, &nexthop->src, sizeof(nexthop->src));
 817         memcpy(&copy->rmap_src, &nexthop->rmap_src, sizeof(nexthop->rmap_src));
 818         copy->rparent = rparent;
 819         if (nexthop->nh_label)
 820                 nexthop_add_labels(copy, nexthop->nh_label_type,
 821                                    nexthop->nh_label->num_labels,
 822                                    &nexthop->nh_label->label[0]);
 823
 824         if (nexthop->nh_srv6) {
 825                 if (nexthop->nh_srv6->seg6local_action !=
 826                     ZEBRA_SEG6_LOCAL_ACTION_UNSPEC)
 827                         nexthop_add_srv6_seg6local(copy,
 828                                 nexthop->nh_srv6->seg6local_action,
 829                                 &nexthop->nh_srv6->seg6local_ctx);
 830                 if (!sid_zero(&nexthop->nh_srv6->seg6_segs))
 831                         nexthop_add_srv6_seg6(copy,
 832                                 &nexthop->nh_srv6->seg6_segs);
 833         }
 834 }
 835
 836 void nexthop_copy(struct nexthop *copy, const struct nexthop *nexthop,
 837                   struct nexthop *rparent)
 838 {
 839         nexthop_copy_no_recurse(copy, nexthop, rparent);
 840
 841         /* Bit of a special case here, we need to handle the case
 842          * of a nexthop resolving to a group. Hence, we need to
 843          * use a nexthop_group API.
 844          */
 845         if (CHECK_FLAG(copy->flags, NEXTHOP_FLAG_RECURSIVE))
 846                 copy_nexthops(&copy->resolved, nexthop->resolved, copy);
 847 }
 848
 849 struct nexthop *nexthop_dup_no_recurse(const struct nexthop *nexthop,
 850                                        struct nexthop *rparent)
 851 {
 852         struct nexthop *new = nexthop_new();
 853
 854         nexthop_copy_no_recurse(new, nexthop, rparent);
 855         return new;
 856 }
 857
 858 struct nexthop *nexthop_dup(const struct nexthop *nexthop,
 859                             struct nexthop *rparent)
 860 {
 861         struct nexthop *new = nexthop_new();
 862
 863         nexthop_copy(new, nexthop, rparent);
 864         return new;
 865 }
 866
 867 /*
 868  * Parse one or more backup index values, as comma-separated numbers,
 869  * into caller's array of uint8_ts. The array must be NEXTHOP_MAX_BACKUPS
 870  * in size. Mails back the number of values converted, and returns 0 on
 871  * success, <0 if an error in parsing.
 872  */
 873 int nexthop_str2backups(const char *str, int *num_backups,
 874                         uint8_t *backups)
 875 {
 876         char *ostr;                       /* copy of string (start) */
 877         char *lstr;                       /* working copy of string */
 878         char *nump;                       /* pointer to next segment */
 879         char *endp;                       /* end pointer */
 880         int i, ret;
 881         uint8_t tmp[NEXTHOP_MAX_BACKUPS];
 882         uint32_t lval;
 883
 884         /* Copy incoming string; the parse is destructive */
 885         lstr = ostr = XSTRDUP(MTYPE_TMP, str);
 886         *num_backups = 0;
 887         ret = 0;
 888
 889         for (i = 0; i < NEXTHOP_MAX_BACKUPS && lstr; i++) {
 890                 nump = strsep(&lstr, ",");
 891                 lval = strtoul(nump, &endp, 10);
 892
 893                 /* Format check */
 894                 if (*endp != '\0') {
 895                         ret = -1;
 896                         break;
 897                 }
 898
 899                 /* Empty value */
 900                 if (endp == nump) {
 901                         ret = -1;
 902                         break;
 903                 }
 904
 905                 /* Limit to one octet */
 906                 if (lval > 255) {
 907                         ret = -1;
 908                         break;
 909                 }
 910
 911                 tmp[i] = lval;
 912         }
 913
 914         /* Excess values */
 915         if (ret == 0 && i == NEXTHOP_MAX_BACKUPS && lstr)
 916                 ret = -1;
 917
 918         if (ret == 0) {
 919                 *num_backups = i;
 920                 memcpy(backups, tmp, i);
 921         }
 922
 923         XFREE(MTYPE_TMP, ostr);
 924
 925         return ret;
 926 }
 927
 928 /*
 929  * nexthop printing variants:
 930  *      %pNHvv
 931  *              via 1.2.3.4
 932  *              via 1.2.3.4, eth0
 933  *              is directly connected, eth0
 934  *              unreachable (blackhole)
 935  *      %pNHv
 936  *              1.2.3.4
 937  *              1.2.3.4, via eth0
 938  *              directly connected, eth0
 939  *              unreachable (blackhole)
 940  *      %pNHs
 941  *              nexthop2str()
 942  */
 943 printfrr_ext_autoreg_p("NH", printfrr_nh)
 944 static ssize_t printfrr_nh(struct fbuf *buf, struct printfrr_eargs *ea,
 945                            const void *ptr)
 946 {
 947         const struct nexthop *nexthop = ptr;
 948         bool do_ifi = false;
 949         const char *v_is = "", *v_via = "", *v_viaif = "via ";
 950         ssize_t ret = 0;
 951
 952         switch (*ea->fmt) {
 953         case 'v':
 954                 ea->fmt++;
 955                 if (*ea->fmt == 'v') {
 956                         v_is = "is ";
 957                         v_via = "via ";
 958                         v_viaif = "";
 959                         ea->fmt++;
 960                 }
 961
 962                 if (!nexthop)
 963                         return bputs(buf, "(null)");
 964
 965                 switch (nexthop->type) {
 966                 case NEXTHOP_TYPE_IPV4:
 967                 case NEXTHOP_TYPE_IPV4_IFINDEX:
 968                         ret += bprintfrr(buf, "%s%pI4", v_via,
 969                                          &nexthop->gate.ipv4);
 970                         do_ifi = true;
 971                         break;
 972                 case NEXTHOP_TYPE_IPV6:
 973                 case NEXTHOP_TYPE_IPV6_IFINDEX:
 974                         ret += bprintfrr(buf, "%s%pI6", v_via,
 975                                          &nexthop->gate.ipv6);
 976                         do_ifi = true;
 977                         break;
 978                 case NEXTHOP_TYPE_IFINDEX:
 979                         ret += bprintfrr(buf, "%sdirectly connected, %s", v_is,
 980                                          ifindex2ifname(nexthop->ifindex,
 981                                                         nexthop->vrf_id));
 982                         break;
 983                 case NEXTHOP_TYPE_BLACKHOLE:
 984                         ret += bputs(buf, "unreachable");
 985
 986                         switch (nexthop->bh_type) {
 987                         case BLACKHOLE_REJECT:
 988                                 ret += bputs(buf, " (ICMP unreachable)");
 989                                 break;
 990                         case BLACKHOLE_ADMINPROHIB:
 991                                 ret += bputs(buf, " (ICMP admin-prohibited)");
 992                                 break;
 993                         case BLACKHOLE_NULL:
 994                                 ret += bputs(buf, " (blackhole)");
 995                                 break;
 996                         default:
 997                                 break;
 998                         }
 999                         break;
1000                 default:
1001                         break;
1002                 }
1003                 if (do_ifi && nexthop->ifindex)
1004                         ret += bprintfrr(buf, ", %s%s", v_viaif,
1005                                          ifindex2ifname(nexthop->ifindex,
1006                                                         nexthop->vrf_id));
1007
1008                 return ret;
1009         case 's':
1010                 ea->fmt++;
1011
1012                 if (!nexthop)
1013                         return bputs(buf, "(null)");
1014
1015                 switch (nexthop->type) {
1016                 case NEXTHOP_TYPE_IFINDEX:
1017                         ret += bprintfrr(buf, "if %u", nexthop->ifindex);
1018                         break;
1019                 case NEXTHOP_TYPE_IPV4:
1020                 case NEXTHOP_TYPE_IPV4_IFINDEX:
1021                         ret += bprintfrr(buf, "%pI4 if %u", &nexthop->gate.ipv4,
1022                                          nexthop->ifindex);
1023                         break;
1024                 case NEXTHOP_TYPE_IPV6:
1025                 case NEXTHOP_TYPE_IPV6_IFINDEX:
1026                         ret += bprintfrr(buf, "%pI6 if %u", &nexthop->gate.ipv6,
1027                                          nexthop->ifindex);
1028                         break;
1029                 case NEXTHOP_TYPE_BLACKHOLE:
1030                         ret += bputs(buf, "blackhole");
1031                         break;
1032                 default:
1033                         ret += bputs(buf, "unknown");
1034                         break;
1035                 }
1036                 return ret;
1037         }
1038         return -1;
1039 }