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 {
 524         struct nexthop *nexthop;
 525
 526         nexthop = nexthop_new();
 527         nexthop->vrf_id = VRF_DEFAULT;
 528         nexthop->type = NEXTHOP_TYPE_BLACKHOLE;
 529         nexthop->bh_type = bh_type;
 530
 531         return nexthop;
 532 }
 533
 534 /* Update nexthop with label information. */
 535 void nexthop_add_labels(struct nexthop *nexthop, enum lsp_types_t ltype,
 536                         uint8_t num_labels, const mpls_label_t *labels)
 537 {
 538         struct mpls_label_stack *nh_label;
 539         int i;
 540
 541         if (num_labels == 0)
 542                 return;
 543
 544         /* Enforce limit on label stack size */
 545         if (num_labels > MPLS_MAX_LABELS)
 546                 num_labels = MPLS_MAX_LABELS;
 547
 548         nexthop->nh_label_type = ltype;
 549
 550         nh_label = XCALLOC(MTYPE_NH_LABEL,
 551                            sizeof(struct mpls_label_stack)
 552                                    + num_labels * sizeof(mpls_label_t));
 553         nh_label->num_labels = num_labels;
 554         for (i = 0; i < num_labels; i++)
 555                 nh_label->label[i] = *(labels + i);
 556         nexthop->nh_label = nh_label;
 557 }
 558
 559 /* Free label information of nexthop, if present. */
 560 void nexthop_del_labels(struct nexthop *nexthop)
 561 {
 562         XFREE(MTYPE_NH_LABEL, nexthop->nh_label);
 563         nexthop->nh_label_type = ZEBRA_LSP_NONE;
 564 }
 565
 566 void nexthop_add_srv6_seg6local(struct nexthop *nexthop, uint32_t action,
 567                                 const struct seg6local_context *ctx)
 568 {
 569         if (action == ZEBRA_SEG6_LOCAL_ACTION_UNSPEC)
 570                 return;
 571
 572         if (!nexthop->nh_srv6)
 573                 nexthop->nh_srv6 = XCALLOC(MTYPE_NH_SRV6,
 574                                            sizeof(struct nexthop_srv6));
 575
 576         nexthop->nh_srv6->seg6local_action = action;
 577         nexthop->nh_srv6->seg6local_ctx = *ctx;
 578 }
 579
 580 void nexthop_del_srv6_seg6local(struct nexthop *nexthop)
 581 {
 582         if (!nexthop->nh_srv6)
 583                 return;
 584
 585         nexthop->nh_srv6->seg6local_action = ZEBRA_SEG6_LOCAL_ACTION_UNSPEC;
 586
 587         if (sid_zero(&nexthop->nh_srv6->seg6_segs))
 588                 XFREE(MTYPE_NH_SRV6, nexthop->nh_srv6);
 589 }
 590
 591 void nexthop_add_srv6_seg6(struct nexthop *nexthop,
 592                            const struct in6_addr *segs)
 593 {
 594         if (!segs)
 595                 return;
 596
 597         if (!nexthop->nh_srv6)
 598                 nexthop->nh_srv6 = XCALLOC(MTYPE_NH_SRV6,
 599                                            sizeof(struct nexthop_srv6));
 600
 601         nexthop->nh_srv6->seg6_segs = *segs;
 602 }
 603
 604 void nexthop_del_srv6_seg6(struct nexthop *nexthop)
 605 {
 606         if (!nexthop->nh_srv6)
 607                 return;
 608
 609         memset(&nexthop->nh_srv6->seg6_segs, 0,
 610                sizeof(nexthop->nh_srv6->seg6_segs));
 611
 612         if (nexthop->nh_srv6->seg6local_action ==
 613             ZEBRA_SEG6_LOCAL_ACTION_UNSPEC)
 614                 XFREE(MTYPE_NH_SRV6, nexthop->nh_srv6);
 615 }
 616
 617 const char *nexthop2str(const struct nexthop *nexthop, char *str, int size)
 618 {
 619         switch (nexthop->type) {
 620         case NEXTHOP_TYPE_IFINDEX:
 621                 snprintf(str, size, "if %u", nexthop->ifindex);
 622                 break;
 623         case NEXTHOP_TYPE_IPV4:
 624         case NEXTHOP_TYPE_IPV4_IFINDEX:
 625                 snprintfrr(str, size, "%pI4 if %u", &nexthop->gate.ipv4,
 626                            nexthop->ifindex);
 627                 break;
 628         case NEXTHOP_TYPE_IPV6:
 629         case NEXTHOP_TYPE_IPV6_IFINDEX:
 630                 snprintfrr(str, size, "%pI6 if %u", &nexthop->gate.ipv6,
 631                            nexthop->ifindex);
 632                 break;
 633         case NEXTHOP_TYPE_BLACKHOLE:
 634                 snprintf(str, size, "blackhole");
 635                 break;
 636         default:
 637                 snprintf(str, size, "unknown");
 638                 break;
 639         }
 640
 641         return str;
 642 }
 643
 644 /*
 645  * Iteration step for ALL_NEXTHOPS macro:
 646  * This is the tricky part. Check if `nexthop' has
 647  * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has
 648  * at least one nexthop attached to `nexthop->resolved', which will be
 649  * the next one.
 650  *
 651  * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
 652  * current chain. In case its current chain end is reached, it will move
 653  * upwards in the recursion levels and progress there. Whenever a step
 654  * forward in a chain is done, recursion will be checked again.
 655  * In a nustshell, it's equivalent to a pre-traversal order assuming that
 656  * left branch is 'resolved' and right branch is 'next':
 657  * https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg
 658  */
 659 struct nexthop *nexthop_next(const struct nexthop *nexthop)
 660 {
 661         if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
 662                 return nexthop->resolved;
 663
 664         if (nexthop->next)
 665                 return nexthop->next;
 666
 667         for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
 668                 if (par->next)
 669                         return par->next;
 670
 671         return NULL;
 672 }
 673
 674 /* Return the next nexthop in the tree that is resolved and active */
 675 struct nexthop *nexthop_next_active_resolved(const struct nexthop *nexthop)
 676 {
 677         struct nexthop *next = nexthop_next(nexthop);
 678
 679         while (next
 680                && (CHECK_FLAG(next->flags, NEXTHOP_FLAG_RECURSIVE)
 681                    || !CHECK_FLAG(next->flags, NEXTHOP_FLAG_ACTIVE)))
 682                 next = nexthop_next(next);
 683
 684         return next;
 685 }
 686
 687 unsigned int nexthop_level(const struct nexthop *nexthop)
 688 {
 689         unsigned int rv = 0;
 690
 691         for (const struct nexthop *par = nexthop->rparent;
 692              par; par = par->rparent)
 693                 rv++;
 694
 695         return rv;
 696 }
 697
 698 /* Only hash word-sized things, let cmp do the rest. */
 699 uint32_t nexthop_hash_quick(const struct nexthop *nexthop)
 700 {
 701         uint32_t key = 0x45afe398;
 702         int i;
 703
 704         key = jhash_3words(nexthop->type, nexthop->vrf_id,
 705                            nexthop->nh_label_type, key);
 706
 707         if (nexthop->nh_label) {
 708                 int labels = nexthop->nh_label->num_labels;
 709
 710                 i = 0;
 711
 712                 while (labels >= 3) {
 713                         key = jhash_3words(nexthop->nh_label->label[i],
 714                                            nexthop->nh_label->label[i + 1],
 715                                            nexthop->nh_label->label[i + 2],
 716                                            key);
 717                         labels -= 3;
 718                         i += 3;
 719                 }
 720
 721                 if (labels >= 2) {
 722                         key = jhash_2words(nexthop->nh_label->label[i],
 723                                            nexthop->nh_label->label[i + 1],
 724                                            key);
 725                         labels -= 2;
 726                         i += 2;
 727                 }
 728
 729                 if (labels >= 1)
 730                         key = jhash_1word(nexthop->nh_label->label[i], key);
 731         }
 732
 733         key = jhash_2words(nexthop->ifindex,
 734                            CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK),
 735                            key);
 736
 737         /* Include backup nexthops, if present */
 738         if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_HAS_BACKUP)) {
 739                 int backups = nexthop->backup_num;
 740
 741                 i = 0;
 742
 743                 while (backups >= 3) {
 744                         key = jhash_3words(nexthop->backup_idx[i],
 745                                            nexthop->backup_idx[i + 1],
 746                                            nexthop->backup_idx[i + 2], key);
 747                         backups -= 3;
 748                         i += 3;
 749                 }
 750
 751                 while (backups >= 2) {
 752                         key = jhash_2words(nexthop->backup_idx[i],
 753                                            nexthop->backup_idx[i + 1], key);
 754                         backups -= 2;
 755                         i += 2;
 756                 }
 757
 758                 if (backups >= 1)
 759                         key = jhash_1word(nexthop->backup_idx[i], key);
 760         }
 761
 762         if (nexthop->nh_srv6) {
 763                 key = jhash_1word(nexthop->nh_srv6->seg6local_action, key);
 764                 key = jhash(&nexthop->nh_srv6->seg6local_ctx,
 765                             sizeof(nexthop->nh_srv6->seg6local_ctx), key);
 766                 key = jhash(&nexthop->nh_srv6->seg6_segs,
 767                             sizeof(nexthop->nh_srv6->seg6_segs), key);
 768         }
 769
 770         return key;
 771 }
 772
 773
 774 #define GATE_SIZE 4 /* Number of uint32_t words in struct g_addr */
 775
 776 /* For a more granular hash */
 777 uint32_t nexthop_hash(const struct nexthop *nexthop)
 778 {
 779         uint32_t gate_src_rmap_raw[GATE_SIZE * 3] = {};
 780         /* Get all the quick stuff */
 781         uint32_t key = nexthop_hash_quick(nexthop);
 782
 783         assert(((sizeof(nexthop->gate) + sizeof(nexthop->src)
 784                  + sizeof(nexthop->rmap_src))
 785                 / 3)
 786                == (GATE_SIZE * sizeof(uint32_t)));
 787
 788         memcpy(gate_src_rmap_raw, &nexthop->gate, GATE_SIZE);
 789         memcpy(gate_src_rmap_raw + GATE_SIZE, &nexthop->src, GATE_SIZE);
 790         memcpy(gate_src_rmap_raw + (2 * GATE_SIZE), &nexthop->rmap_src,
 791                GATE_SIZE);
 792
 793         key = jhash2(gate_src_rmap_raw, (GATE_SIZE * 3), key);
 794
 795         return key;
 796 }
 797
 798 void nexthop_copy_no_recurse(struct nexthop *copy,
 799                              const struct nexthop *nexthop,
 800                              struct nexthop *rparent)
 801 {
 802         copy->vrf_id = nexthop->vrf_id;
 803         copy->ifindex = nexthop->ifindex;
 804         copy->type = nexthop->type;
 805         copy->flags = nexthop->flags;
 806         copy->weight = nexthop->weight;
 807
 808         assert(nexthop->backup_num < NEXTHOP_MAX_BACKUPS);
 809         copy->backup_num = nexthop->backup_num;
 810         if (copy->backup_num > 0)
 811                 memcpy(copy->backup_idx, nexthop->backup_idx, copy->backup_num);
 812
 813         copy->srte_color = nexthop->srte_color;
 814         memcpy(&copy->gate, &nexthop->gate, sizeof(nexthop->gate));
 815         memcpy(&copy->src, &nexthop->src, sizeof(nexthop->src));
 816         memcpy(&copy->rmap_src, &nexthop->rmap_src, sizeof(nexthop->rmap_src));
 817         copy->rparent = rparent;
 818         if (nexthop->nh_label)
 819                 nexthop_add_labels(copy, nexthop->nh_label_type,
 820                                    nexthop->nh_label->num_labels,
 821                                    &nexthop->nh_label->label[0]);
 822
 823         if (nexthop->nh_srv6) {
 824                 if (nexthop->nh_srv6->seg6local_action !=
 825                     ZEBRA_SEG6_LOCAL_ACTION_UNSPEC)
 826                         nexthop_add_srv6_seg6local(copy,
 827                                 nexthop->nh_srv6->seg6local_action,
 828                                 &nexthop->nh_srv6->seg6local_ctx);
 829                 if (!sid_zero(&nexthop->nh_srv6->seg6_segs))
 830                         nexthop_add_srv6_seg6(copy,
 831                                 &nexthop->nh_srv6->seg6_segs);
 832         }
 833 }
 834
 835 void nexthop_copy(struct nexthop *copy, const struct nexthop *nexthop,
 836                   struct nexthop *rparent)
 837 {
 838         nexthop_copy_no_recurse(copy, nexthop, rparent);
 839
 840         /* Bit of a special case here, we need to handle the case
 841          * of a nexthop resolving to a group. Hence, we need to
 842          * use a nexthop_group API.
 843          */
 844         if (CHECK_FLAG(copy->flags, NEXTHOP_FLAG_RECURSIVE))
 845                 copy_nexthops(&copy->resolved, nexthop->resolved, copy);
 846 }
 847
 848 struct nexthop *nexthop_dup_no_recurse(const struct nexthop *nexthop,
 849                                        struct nexthop *rparent)
 850 {
 851         struct nexthop *new = nexthop_new();
 852
 853         nexthop_copy_no_recurse(new, nexthop, rparent);
 854         return new;
 855 }
 856
 857 struct nexthop *nexthop_dup(const struct nexthop *nexthop,
 858                             struct nexthop *rparent)
 859 {
 860         struct nexthop *new = nexthop_new();
 861
 862         nexthop_copy(new, nexthop, rparent);
 863         return new;
 864 }
 865
 866 /*
 867  * Parse one or more backup index values, as comma-separated numbers,
 868  * into caller's array of uint8_ts. The array must be NEXTHOP_MAX_BACKUPS
 869  * in size. Mails back the number of values converted, and returns 0 on
 870  * success, <0 if an error in parsing.
 871  */
 872 int nexthop_str2backups(const char *str, int *num_backups,
 873                         uint8_t *backups)
 874 {
 875         char *ostr;                       /* copy of string (start) */
 876         char *lstr;                       /* working copy of string */
 877         char *nump;                       /* pointer to next segment */
 878         char *endp;                       /* end pointer */
 879         int i, ret;
 880         uint8_t tmp[NEXTHOP_MAX_BACKUPS];
 881         uint32_t lval;
 882
 883         /* Copy incoming string; the parse is destructive */
 884         lstr = ostr = XSTRDUP(MTYPE_TMP, str);
 885         *num_backups = 0;
 886         ret = 0;
 887
 888         for (i = 0; i < NEXTHOP_MAX_BACKUPS && lstr; i++) {
 889                 nump = strsep(&lstr, ",");
 890                 lval = strtoul(nump, &endp, 10);
 891
 892                 /* Format check */
 893                 if (*endp != '\0') {
 894                         ret = -1;
 895                         break;
 896                 }
 897
 898                 /* Empty value */
 899                 if (endp == nump) {
 900                         ret = -1;
 901                         break;
 902                 }
 903
 904                 /* Limit to one octet */
 905                 if (lval > 255) {
 906                         ret = -1;
 907                         break;
 908                 }
 909
 910                 tmp[i] = lval;
 911         }
 912
 913         /* Excess values */
 914         if (ret == 0 && i == NEXTHOP_MAX_BACKUPS && lstr)
 915                 ret = -1;
 916
 917         if (ret == 0) {
 918                 *num_backups = i;
 919                 memcpy(backups, tmp, i);
 920         }
 921
 922         XFREE(MTYPE_TMP, ostr);
 923
 924         return ret;
 925 }
 926
 927 /*
 928  * nexthop printing variants:
 929  *      %pNHvv
 930  *              via 1.2.3.4
 931  *              via 1.2.3.4, eth0
 932  *              is directly connected, eth0
 933  *              unreachable (blackhole)
 934  *      %pNHv
 935  *              1.2.3.4
 936  *              1.2.3.4, via eth0
 937  *              directly connected, eth0
 938  *              unreachable (blackhole)
 939  *      %pNHs
 940  *              nexthop2str()
 941  */
 942 printfrr_ext_autoreg_p("NH", printfrr_nh)
 943 static ssize_t printfrr_nh(struct fbuf *buf, struct printfrr_eargs *ea,
 944                            const void *ptr)
 945 {
 946         const struct nexthop *nexthop = ptr;
 947         bool do_ifi = false;
 948         const char *v_is = "", *v_via = "", *v_viaif = "via ";
 949         ssize_t ret = 0;
 950
 951         switch (*ea->fmt) {
 952         case 'v':
 953                 ea->fmt++;
 954                 if (*ea->fmt == 'v') {
 955                         v_is = "is ";
 956                         v_via = "via ";
 957                         v_viaif = "";
 958                         ea->fmt++;
 959                 }
 960
 961                 if (!nexthop)
 962                         return bputs(buf, "(null)");
 963
 964                 switch (nexthop->type) {
 965                 case NEXTHOP_TYPE_IPV4:
 966                 case NEXTHOP_TYPE_IPV4_IFINDEX:
 967                         ret += bprintfrr(buf, "%s%pI4", v_via,
 968                                          &nexthop->gate.ipv4);
 969                         do_ifi = true;
 970                         break;
 971                 case NEXTHOP_TYPE_IPV6:
 972                 case NEXTHOP_TYPE_IPV6_IFINDEX:
 973                         ret += bprintfrr(buf, "%s%pI6", v_via,
 974                                          &nexthop->gate.ipv6);
 975                         do_ifi = true;
 976                         break;
 977                 case NEXTHOP_TYPE_IFINDEX:
 978                         ret += bprintfrr(buf, "%sdirectly connected, %s", v_is,
 979                                          ifindex2ifname(nexthop->ifindex,
 980                                                         nexthop->vrf_id));
 981                         break;
 982                 case NEXTHOP_TYPE_BLACKHOLE:
 983                         ret += bputs(buf, "unreachable");
 984
 985                         switch (nexthop->bh_type) {
 986                         case BLACKHOLE_REJECT:
 987                                 ret += bputs(buf, " (ICMP unreachable)");
 988                                 break;
 989                         case BLACKHOLE_ADMINPROHIB:
 990                                 ret += bputs(buf, " (ICMP admin-prohibited)");
 991                                 break;
 992                         case BLACKHOLE_NULL:
 993                                 ret += bputs(buf, " (blackhole)");
 994                                 break;
 995                         default:
 996                                 break;
 997                         }
 998                         break;
 999                 default:
1000                         break;
1001                 }
1002                 if (do_ifi && nexthop->ifindex)
1003                         ret += bprintfrr(buf, ", %s%s", v_viaif,
1004                                          ifindex2ifname(nexthop->ifindex,
1005                                                         nexthop->vrf_id));
1006
1007                 return ret;
1008         case 's':
1009                 ea->fmt++;
1010
1011                 if (!nexthop)
1012                         return bputs(buf, "(null)");
1013
1014                 switch (nexthop->type) {
1015                 case NEXTHOP_TYPE_IFINDEX:
1016                         ret += bprintfrr(buf, "if %u", nexthop->ifindex);
1017                         break;
1018                 case NEXTHOP_TYPE_IPV4:
1019                 case NEXTHOP_TYPE_IPV4_IFINDEX:
1020                         ret += bprintfrr(buf, "%pI4 if %u", &nexthop->gate.ipv4,
1021                                          nexthop->ifindex);
1022                         break;
1023                 case NEXTHOP_TYPE_IPV6:
1024                 case NEXTHOP_TYPE_IPV6_IFINDEX:
1025                         ret += bprintfrr(buf, "%pI6 if %u", &nexthop->gate.ipv6,
1026                                          nexthop->ifindex);
1027                         break;
1028                 case NEXTHOP_TYPE_BLACKHOLE:
1029                         ret += bputs(buf, "blackhole");
1030                         break;
1031                 default:
1032                         ret += bputs(buf, "unknown");
1033                         break;
1034                 }
1035                 return ret;
1036         }
1037         return -1;
1038 }