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         }
 638
 639         return str;
 640 }
 641
 642 /*
 643  * Iteration step for ALL_NEXTHOPS macro:
 644  * This is the tricky part. Check if `nexthop' has
 645  * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has
 646  * at least one nexthop attached to `nexthop->resolved', which will be
 647  * the next one.
 648  *
 649  * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
 650  * current chain. In case its current chain end is reached, it will move
 651  * upwards in the recursion levels and progress there. Whenever a step
 652  * forward in a chain is done, recursion will be checked again.
 653  * In a nustshell, it's equivalent to a pre-traversal order assuming that
 654  * left branch is 'resolved' and right branch is 'next':
 655  * https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg
 656  */
 657 struct nexthop *nexthop_next(const struct nexthop *nexthop)
 658 {
 659         if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
 660                 return nexthop->resolved;
 661
 662         if (nexthop->next)
 663                 return nexthop->next;
 664
 665         for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
 666                 if (par->next)
 667                         return par->next;
 668
 669         return NULL;
 670 }
 671
 672 /* Return the next nexthop in the tree that is resolved and active */
 673 struct nexthop *nexthop_next_active_resolved(const struct nexthop *nexthop)
 674 {
 675         struct nexthop *next = nexthop_next(nexthop);
 676
 677         while (next
 678                && (CHECK_FLAG(next->flags, NEXTHOP_FLAG_RECURSIVE)
 679                    || !CHECK_FLAG(next->flags, NEXTHOP_FLAG_ACTIVE)))
 680                 next = nexthop_next(next);
 681
 682         return next;
 683 }
 684
 685 unsigned int nexthop_level(const struct nexthop *nexthop)
 686 {
 687         unsigned int rv = 0;
 688
 689         for (const struct nexthop *par = nexthop->rparent;
 690              par; par = par->rparent)
 691                 rv++;
 692
 693         return rv;
 694 }
 695
 696 /* Only hash word-sized things, let cmp do the rest. */
 697 uint32_t nexthop_hash_quick(const struct nexthop *nexthop)
 698 {
 699         uint32_t key = 0x45afe398;
 700         int i;
 701
 702         key = jhash_3words(nexthop->type, nexthop->vrf_id,
 703                            nexthop->nh_label_type, key);
 704
 705         if (nexthop->nh_label) {
 706                 int labels = nexthop->nh_label->num_labels;
 707
 708                 i = 0;
 709
 710                 while (labels >= 3) {
 711                         key = jhash_3words(nexthop->nh_label->label[i],
 712                                            nexthop->nh_label->label[i + 1],
 713                                            nexthop->nh_label->label[i + 2],
 714                                            key);
 715                         labels -= 3;
 716                         i += 3;
 717                 }
 718
 719                 if (labels >= 2) {
 720                         key = jhash_2words(nexthop->nh_label->label[i],
 721                                            nexthop->nh_label->label[i + 1],
 722                                            key);
 723                         labels -= 2;
 724                         i += 2;
 725                 }
 726
 727                 if (labels >= 1)
 728                         key = jhash_1word(nexthop->nh_label->label[i], key);
 729         }
 730
 731         key = jhash_2words(nexthop->ifindex,
 732                            CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK),
 733                            key);
 734
 735         /* Include backup nexthops, if present */
 736         if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_HAS_BACKUP)) {
 737                 int backups = nexthop->backup_num;
 738
 739                 i = 0;
 740
 741                 while (backups >= 3) {
 742                         key = jhash_3words(nexthop->backup_idx[i],
 743                                            nexthop->backup_idx[i + 1],
 744                                            nexthop->backup_idx[i + 2], key);
 745                         backups -= 3;
 746                         i += 3;
 747                 }
 748
 749                 while (backups >= 2) {
 750                         key = jhash_2words(nexthop->backup_idx[i],
 751                                            nexthop->backup_idx[i + 1], key);
 752                         backups -= 2;
 753                         i += 2;
 754                 }
 755
 756                 if (backups >= 1)
 757                         key = jhash_1word(nexthop->backup_idx[i], key);
 758         }
 759
 760         if (nexthop->nh_srv6) {
 761                 key = jhash_1word(nexthop->nh_srv6->seg6local_action, key);
 762                 key = jhash(&nexthop->nh_srv6->seg6local_ctx,
 763                             sizeof(nexthop->nh_srv6->seg6local_ctx), key);
 764                 key = jhash(&nexthop->nh_srv6->seg6_segs,
 765                             sizeof(nexthop->nh_srv6->seg6_segs), key);
 766         }
 767
 768         return key;
 769 }
 770
 771
 772 #define GATE_SIZE 4 /* Number of uint32_t words in struct g_addr */
 773
 774 /* For a more granular hash */
 775 uint32_t nexthop_hash(const struct nexthop *nexthop)
 776 {
 777         uint32_t gate_src_rmap_raw[GATE_SIZE * 3] = {};
 778         /* Get all the quick stuff */
 779         uint32_t key = nexthop_hash_quick(nexthop);
 780
 781         assert(((sizeof(nexthop->gate) + sizeof(nexthop->src)
 782                  + sizeof(nexthop->rmap_src))
 783                 / 3)
 784                == (GATE_SIZE * sizeof(uint32_t)));
 785
 786         memcpy(gate_src_rmap_raw, &nexthop->gate, GATE_SIZE);
 787         memcpy(gate_src_rmap_raw + GATE_SIZE, &nexthop->src, GATE_SIZE);
 788         memcpy(gate_src_rmap_raw + (2 * GATE_SIZE), &nexthop->rmap_src,
 789                GATE_SIZE);
 790
 791         key = jhash2(gate_src_rmap_raw, (GATE_SIZE * 3), key);
 792
 793         return key;
 794 }
 795
 796 void nexthop_copy_no_recurse(struct nexthop *copy,
 797                              const struct nexthop *nexthop,
 798                              struct nexthop *rparent)
 799 {
 800         copy->vrf_id = nexthop->vrf_id;
 801         copy->ifindex = nexthop->ifindex;
 802         copy->type = nexthop->type;
 803         copy->flags = nexthop->flags;
 804         copy->weight = nexthop->weight;
 805
 806         assert(nexthop->backup_num < NEXTHOP_MAX_BACKUPS);
 807         copy->backup_num = nexthop->backup_num;
 808         if (copy->backup_num > 0)
 809                 memcpy(copy->backup_idx, nexthop->backup_idx, copy->backup_num);
 810
 811         copy->srte_color = nexthop->srte_color;
 812         memcpy(&copy->gate, &nexthop->gate, sizeof(nexthop->gate));
 813         memcpy(&copy->src, &nexthop->src, sizeof(nexthop->src));
 814         memcpy(&copy->rmap_src, &nexthop->rmap_src, sizeof(nexthop->rmap_src));
 815         copy->rparent = rparent;
 816         if (nexthop->nh_label)
 817                 nexthop_add_labels(copy, nexthop->nh_label_type,
 818                                    nexthop->nh_label->num_labels,
 819                                    &nexthop->nh_label->label[0]);
 820
 821         if (nexthop->nh_srv6) {
 822                 if (nexthop->nh_srv6->seg6local_action !=
 823                     ZEBRA_SEG6_LOCAL_ACTION_UNSPEC)
 824                         nexthop_add_srv6_seg6local(copy,
 825                                 nexthop->nh_srv6->seg6local_action,
 826                                 &nexthop->nh_srv6->seg6local_ctx);
 827                 if (!sid_zero(&nexthop->nh_srv6->seg6_segs))
 828                         nexthop_add_srv6_seg6(copy,
 829                                 &nexthop->nh_srv6->seg6_segs);
 830         }
 831 }
 832
 833 void nexthop_copy(struct nexthop *copy, const struct nexthop *nexthop,
 834                   struct nexthop *rparent)
 835 {
 836         nexthop_copy_no_recurse(copy, nexthop, rparent);
 837
 838         /* Bit of a special case here, we need to handle the case
 839          * of a nexthop resolving to a group. Hence, we need to
 840          * use a nexthop_group API.
 841          */
 842         if (CHECK_FLAG(copy->flags, NEXTHOP_FLAG_RECURSIVE))
 843                 copy_nexthops(&copy->resolved, nexthop->resolved, copy);
 844 }
 845
 846 struct nexthop *nexthop_dup_no_recurse(const struct nexthop *nexthop,
 847                                        struct nexthop *rparent)
 848 {
 849         struct nexthop *new = nexthop_new();
 850
 851         nexthop_copy_no_recurse(new, nexthop, rparent);
 852         return new;
 853 }
 854
 855 struct nexthop *nexthop_dup(const struct nexthop *nexthop,
 856                             struct nexthop *rparent)
 857 {
 858         struct nexthop *new = nexthop_new();
 859
 860         nexthop_copy(new, nexthop, rparent);
 861         return new;
 862 }
 863
 864 /*
 865  * Parse one or more backup index values, as comma-separated numbers,
 866  * into caller's array of uint8_ts. The array must be NEXTHOP_MAX_BACKUPS
 867  * in size. Mails back the number of values converted, and returns 0 on
 868  * success, <0 if an error in parsing.
 869  */
 870 int nexthop_str2backups(const char *str, int *num_backups,
 871                         uint8_t *backups)
 872 {
 873         char *ostr;                       /* copy of string (start) */
 874         char *lstr;                       /* working copy of string */
 875         char *nump;                       /* pointer to next segment */
 876         char *endp;                       /* end pointer */
 877         int i, ret;
 878         uint8_t tmp[NEXTHOP_MAX_BACKUPS];
 879         uint32_t lval;
 880
 881         /* Copy incoming string; the parse is destructive */
 882         lstr = ostr = XSTRDUP(MTYPE_TMP, str);
 883         *num_backups = 0;
 884         ret = 0;
 885
 886         for (i = 0; i < NEXTHOP_MAX_BACKUPS && lstr; i++) {
 887                 nump = strsep(&lstr, ",");
 888                 lval = strtoul(nump, &endp, 10);
 889
 890                 /* Format check */
 891                 if (*endp != '\0') {
 892                         ret = -1;
 893                         break;
 894                 }
 895
 896                 /* Empty value */
 897                 if (endp == nump) {
 898                         ret = -1;
 899                         break;
 900                 }
 901
 902                 /* Limit to one octet */
 903                 if (lval > 255) {
 904                         ret = -1;
 905                         break;
 906                 }
 907
 908                 tmp[i] = lval;
 909         }
 910
 911         /* Excess values */
 912         if (ret == 0 && i == NEXTHOP_MAX_BACKUPS && lstr)
 913                 ret = -1;
 914
 915         if (ret == 0) {
 916                 *num_backups = i;
 917                 memcpy(backups, tmp, i);
 918         }
 919
 920         XFREE(MTYPE_TMP, ostr);
 921
 922         return ret;
 923 }
 924
 925 ssize_t printfrr_nhs(struct fbuf *buf, const struct nexthop *nexthop)
 926 {
 927         ssize_t ret = 0;
 928
 929         if (!nexthop)
 930                 return bputs(buf, "(null)");
 931
 932         switch (nexthop->type) {
 933         case NEXTHOP_TYPE_IFINDEX:
 934                 ret += bprintfrr(buf, "if %u", nexthop->ifindex);
 935                 break;
 936         case NEXTHOP_TYPE_IPV4:
 937         case NEXTHOP_TYPE_IPV4_IFINDEX:
 938                 ret += bprintfrr(buf, "%pI4 if %u", &nexthop->gate.ipv4,
 939                                  nexthop->ifindex);
 940                 break;
 941         case NEXTHOP_TYPE_IPV6:
 942         case NEXTHOP_TYPE_IPV6_IFINDEX:
 943                 ret += bprintfrr(buf, "%pI6 if %u", &nexthop->gate.ipv6,
 944                                  nexthop->ifindex);
 945                 break;
 946         case NEXTHOP_TYPE_BLACKHOLE:
 947                 ret += bputs(buf, "blackhole");
 948                 break;
 949         }
 950         return ret;
 951 }
 952
 953 /*
 954  * nexthop printing variants:
 955  *      %pNHvv
 956  *              via 1.2.3.4
 957  *              via 1.2.3.4, eth0
 958  *              is directly connected, eth0
 959  *              unreachable (blackhole)
 960  *      %pNHv
 961  *              1.2.3.4
 962  *              1.2.3.4, via eth0
 963  *              directly connected, eth0
 964  *              unreachable (blackhole)
 965  *      %pNHs
 966  *              nexthop2str()
 967  *      %pNHcg
 968  *              1.2.3.4
 969  *              (0-length if no IP address present)
 970  *      %pNHci
 971  *              eth0
 972  *              (0-length if no interface present)
 973  */
 974 printfrr_ext_autoreg_p("NH", printfrr_nh);
 975 static ssize_t printfrr_nh(struct fbuf *buf, struct printfrr_eargs *ea,
 976                            const void *ptr)
 977 {
 978         const struct nexthop *nexthop = ptr;
 979         bool do_ifi = false;
 980         const char *v_is = "", *v_via = "", *v_viaif = "via ";
 981         ssize_t ret = 0;
 982
 983         switch (*ea->fmt) {
 984         case 'v':
 985                 ea->fmt++;
 986                 if (*ea->fmt == 'v') {
 987                         v_is = "is ";
 988                         v_via = "via ";
 989                         v_viaif = "";
 990                         ea->fmt++;
 991                 }
 992
 993                 if (!nexthop)
 994                         return bputs(buf, "(null)");
 995
 996                 switch (nexthop->type) {
 997                 case NEXTHOP_TYPE_IPV4:
 998                 case NEXTHOP_TYPE_IPV4_IFINDEX:
 999                         ret += bprintfrr(buf, "%s%pI4", v_via,
1000                                          &nexthop->gate.ipv4);
1001                         do_ifi = true;
1002                         break;
1003                 case NEXTHOP_TYPE_IPV6:
1004                 case NEXTHOP_TYPE_IPV6_IFINDEX:
1005                         ret += bprintfrr(buf, "%s%pI6", v_via,
1006                                          &nexthop->gate.ipv6);
1007                         do_ifi = true;
1008                         break;
1009                 case NEXTHOP_TYPE_IFINDEX:
1010                         ret += bprintfrr(buf, "%sdirectly connected, %s", v_is,
1011                                          ifindex2ifname(nexthop->ifindex,
1012                                                         nexthop->vrf_id));
1013                         break;
1014                 case NEXTHOP_TYPE_BLACKHOLE:
1015                         ret += bputs(buf, "unreachable");
1016
1017                         switch (nexthop->bh_type) {
1018                         case BLACKHOLE_REJECT:
1019                                 ret += bputs(buf, " (ICMP unreachable)");
1020                                 break;
1021                         case BLACKHOLE_ADMINPROHIB:
1022                                 ret += bputs(buf, " (ICMP admin-prohibited)");
1023                                 break;
1024                         case BLACKHOLE_NULL:
1025                                 ret += bputs(buf, " (blackhole)");
1026                                 break;
1027                         case BLACKHOLE_UNSPEC:
1028                                 break;
1029                         }
1030                         break;
1031                 }
1032                 if (do_ifi && nexthop->ifindex)
1033                         ret += bprintfrr(buf, ", %s%s", v_viaif,
1034                                          ifindex2ifname(nexthop->ifindex,
1035                                                         nexthop->vrf_id));
1036
1037                 return ret;
1038         case 's':
1039                 ea->fmt++;
1040
1041                 ret += printfrr_nhs(buf, nexthop);
1042                 return ret;
1043         case 'c':
1044                 ea->fmt++;
1045                 if (*ea->fmt == 'g') {
1046                         ea->fmt++;
1047                         if (!nexthop)
1048                                 return bputs(buf, "(null)");
1049                         switch (nexthop->type) {
1050                         case NEXTHOP_TYPE_IPV4:
1051                         case NEXTHOP_TYPE_IPV4_IFINDEX:
1052                                 ret += bprintfrr(buf, "%pI4",
1053                                                  &nexthop->gate.ipv4);
1054                                 break;
1055                         case NEXTHOP_TYPE_IPV6:
1056                         case NEXTHOP_TYPE_IPV6_IFINDEX:
1057                                 ret += bprintfrr(buf, "%pI6",
1058                                                  &nexthop->gate.ipv6);
1059                                 break;
1060                         case NEXTHOP_TYPE_IFINDEX:
1061                         case NEXTHOP_TYPE_BLACKHOLE:
1062                                 break;
1063                         }
1064                 } else if (*ea->fmt == 'i') {
1065                         ea->fmt++;
1066                         if (!nexthop)
1067                                 return bputs(buf, "(null)");
1068                         switch (nexthop->type) {
1069                         case NEXTHOP_TYPE_IFINDEX:
1070                                 ret += bprintfrr(
1071                                         buf, "%s",
1072                                         ifindex2ifname(nexthop->ifindex,
1073                                                        nexthop->vrf_id));
1074                                 break;
1075                         case NEXTHOP_TYPE_IPV4:
1076                         case NEXTHOP_TYPE_IPV4_IFINDEX:
1077                         case NEXTHOP_TYPE_IPV6:
1078                         case NEXTHOP_TYPE_IPV6_IFINDEX:
1079                                 if (nexthop->ifindex)
1080                                         ret += bprintfrr(
1081                                                 buf, "%s",
1082                                                 ifindex2ifname(
1083                                                         nexthop->ifindex,
1084                                                         nexthop->vrf_id));
1085                                 break;
1086                         case NEXTHOP_TYPE_BLACKHOLE:
1087                                 break;
1088                         }
1089                 }
1090                 return ret;
1091         }
1092         return -1;
1093 }