pimd/pim_nht.c

   1 /*
   2  * PIM for Quagga
   3  * Copyright (C) 2017 Cumulus Networks, Inc.
   4  * Chirag Shah
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program 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 #include "network.h"
  22 #include "zclient.h"
  23 #include "stream.h"
  24 #include "nexthop.h"
  25 #include "if.h"
  26 #include "hash.h"
  27 #include "jhash.h"
  28
  29 #include "lib/printfrr.h"
  30
  31 #include "pimd.h"
  32 #include "pimd/pim_nht.h"
  33 #include "pim_instance.h"
  34 #include "log.h"
  35 #include "pim_time.h"
  36 #include "pim_oil.h"
  37 #include "pim_ifchannel.h"
  38 #include "pim_mroute.h"
  39 #include "pim_zebra.h"
  40 #include "pim_upstream.h"
  41 #include "pim_join.h"
  42 #include "pim_jp_agg.h"
  43 #include "pim_zebra.h"
  44 #include "pim_zlookup.h"
  45 #include "pim_rp.h"
  46 #include "pim_addr.h"
  47
  48 /**
  49  * pim_sendmsg_zebra_rnh -- Format and send a nexthop register/Unregister
  50  *   command to Zebra.
  51  */
  52 void pim_sendmsg_zebra_rnh(struct pim_instance *pim, struct zclient *zclient,
  53                            struct pim_nexthop_cache *pnc, int command)
  54 {
  55         struct prefix *p;
  56         int ret;
  57
  58         p = &(pnc->rpf.rpf_addr);
  59         ret = zclient_send_rnh(zclient, command, p, SAFI_UNICAST, false, false,
  60                                pim->vrf->vrf_id);
  61         if (ret == ZCLIENT_SEND_FAILURE)
  62                 zlog_warn("sendmsg_nexthop: zclient_send_message() failed");
  63
  64         if (PIM_DEBUG_PIM_NHT)
  65                 zlog_debug(
  66                         "%s: NHT %sregistered addr %pFX(%s) with Zebra ret:%d ",
  67                         __func__,
  68                         (command == ZEBRA_NEXTHOP_REGISTER) ? " " : "de", p,
  69                         pim->vrf->name, ret);
  70
  71         return;
  72 }
  73
  74 struct pim_nexthop_cache *pim_nexthop_cache_find(struct pim_instance *pim,
  75                                                  struct pim_rpf *rpf)
  76 {
  77         struct pim_nexthop_cache *pnc = NULL;
  78         struct pim_nexthop_cache lookup;
  79
  80         lookup.rpf.rpf_addr = rpf->rpf_addr;
  81         pnc = hash_lookup(pim->rpf_hash, &lookup);
  82
  83         return pnc;
  84 }
  85
  86 static struct pim_nexthop_cache *pim_nexthop_cache_add(struct pim_instance *pim,
  87                                                        struct pim_rpf *rpf_addr)
  88 {
  89         struct pim_nexthop_cache *pnc;
  90         char hash_name[64];
  91
  92         pnc = XCALLOC(MTYPE_PIM_NEXTHOP_CACHE,
  93                       sizeof(struct pim_nexthop_cache));
  94         pnc->rpf.rpf_addr = rpf_addr->rpf_addr;
  95
  96         pnc = hash_get(pim->rpf_hash, pnc, hash_alloc_intern);
  97
  98         pnc->rp_list = list_new();
  99         pnc->rp_list->cmp = pim_rp_list_cmp;
 100
 101         snprintfrr(hash_name, sizeof(hash_name), "PNC %pFX(%s) Upstream Hash",
 102                    &pnc->rpf.rpf_addr, pim->vrf->name);
 103         pnc->upstream_hash = hash_create_size(8192, pim_upstream_hash_key,
 104                                               pim_upstream_equal, hash_name);
 105
 106         return pnc;
 107 }
 108
 109 static struct pim_nexthop_cache *pim_nht_get(struct pim_instance *pim,
 110                                              struct prefix *addr)
 111 {
 112         struct pim_nexthop_cache *pnc = NULL;
 113         struct pim_rpf rpf;
 114         struct zclient *zclient = NULL;
 115
 116         zclient = pim_zebra_zclient_get();
 117         memset(&rpf, 0, sizeof(rpf));
 118         rpf.rpf_addr = *addr;
 119
 120         pnc = pim_nexthop_cache_find(pim, &rpf);
 121         if (!pnc) {
 122                 pnc = pim_nexthop_cache_add(pim, &rpf);
 123                 pim_sendmsg_zebra_rnh(pim, zclient, pnc,
 124                                       ZEBRA_NEXTHOP_REGISTER);
 125                 if (PIM_DEBUG_PIM_NHT_DETAIL)
 126                         zlog_debug(
 127                                 "%s: NHT cache and zebra notification added for %pFX(%s)",
 128                                 __func__, addr, pim->vrf->name);
 129         }
 130
 131         return pnc;
 132 }
 133
 134 /* TBD: this does several distinct things and should probably be split up.
 135  * (checking state vs. returning pnc vs. adding upstream vs. adding rp)
 136  */
 137 int pim_find_or_track_nexthop(struct pim_instance *pim, struct prefix *addr,
 138                               struct pim_upstream *up, struct rp_info *rp,
 139                               struct pim_nexthop_cache *out_pnc)
 140 {
 141         struct pim_nexthop_cache *pnc;
 142         struct listnode *ch_node = NULL;
 143
 144         pnc = pim_nht_get(pim, addr);
 145
 146         assertf(up || rp, "addr=%pFX", addr);
 147
 148         if (rp != NULL) {
 149                 ch_node = listnode_lookup(pnc->rp_list, rp);
 150                 if (ch_node == NULL)
 151                         listnode_add_sort(pnc->rp_list, rp);
 152         }
 153
 154         if (up != NULL)
 155                 (void)hash_get(pnc->upstream_hash, up, hash_alloc_intern);
 156
 157         if (CHECK_FLAG(pnc->flags, PIM_NEXTHOP_VALID)) {
 158                 if (out_pnc)
 159                         memcpy(out_pnc, pnc, sizeof(struct pim_nexthop_cache));
 160                 return 1;
 161         }
 162
 163         return 0;
 164 }
 165
 166 #if PIM_IPV == 4
 167 void pim_nht_bsr_add(struct pim_instance *pim, struct in_addr addr)
 168 {
 169         struct pim_nexthop_cache *pnc;
 170         struct prefix pfx;
 171
 172         pfx.family = AF_INET;
 173         pfx.prefixlen = IPV4_MAX_BITLEN;
 174         pfx.u.prefix4 = addr;
 175
 176         pnc = pim_nht_get(pim, &pfx);
 177
 178         pnc->bsr_count++;
 179 }
 180 #endif /* PIM_IPV == 4 */
 181
 182 static void pim_nht_drop_maybe(struct pim_instance *pim,
 183                                struct pim_nexthop_cache *pnc)
 184 {
 185         if (PIM_DEBUG_PIM_NHT)
 186                 zlog_debug(
 187                         "%s: NHT %pFX(%s) rp_list count:%d upstream count:%ld BSR count:%u",
 188                         __func__, &pnc->rpf.rpf_addr, pim->vrf->name,
 189                         pnc->rp_list->count, pnc->upstream_hash->count,
 190                         pnc->bsr_count);
 191
 192         if (pnc->rp_list->count == 0 && pnc->upstream_hash->count == 0
 193             && pnc->bsr_count == 0) {
 194                 struct zclient *zclient = pim_zebra_zclient_get();
 195
 196                 pim_sendmsg_zebra_rnh(pim, zclient, pnc,
 197                                       ZEBRA_NEXTHOP_UNREGISTER);
 198
 199                 list_delete(&pnc->rp_list);
 200                 hash_free(pnc->upstream_hash);
 201
 202                 hash_release(pim->rpf_hash, pnc);
 203                 if (pnc->nexthop)
 204                         nexthops_free(pnc->nexthop);
 205                 XFREE(MTYPE_PIM_NEXTHOP_CACHE, pnc);
 206         }
 207 }
 208
 209 void pim_delete_tracked_nexthop(struct pim_instance *pim, struct prefix *addr,
 210                                 struct pim_upstream *up, struct rp_info *rp)
 211 {
 212         struct pim_nexthop_cache *pnc = NULL;
 213         struct pim_nexthop_cache lookup;
 214         struct pim_upstream *upstream = NULL;
 215
 216         /* Remove from RPF hash if it is the last entry */
 217         lookup.rpf.rpf_addr = *addr;
 218         pnc = hash_lookup(pim->rpf_hash, &lookup);
 219         if (!pnc) {
 220                 zlog_warn("attempting to delete nonexistent NHT entry %pFX",
 221                           addr);
 222                 return;
 223         }
 224
 225         if (rp) {
 226                 /* Release the (*, G)upstream from pnc->upstream_hash,
 227                  * whose Group belongs to the RP getting deleted
 228                  */
 229                 frr_each (rb_pim_upstream, &pim->upstream_head, upstream) {
 230                         struct prefix grp;
 231                         struct rp_info *trp_info;
 232
 233                         if (!pim_addr_is_any(upstream->sg.src))
 234                                 continue;
 235
 236                         pim_addr_to_prefix(&grp, upstream->sg.grp);
 237                         trp_info = pim_rp_find_match_group(pim, &grp);
 238                         if (trp_info == rp)
 239                                 hash_release(pnc->upstream_hash, upstream);
 240                 }
 241                 listnode_delete(pnc->rp_list, rp);
 242         }
 243
 244         if (up)
 245                 hash_release(pnc->upstream_hash, up);
 246
 247         pim_nht_drop_maybe(pim, pnc);
 248 }
 249
 250 #if PIM_IPV == 4
 251 void pim_nht_bsr_del(struct pim_instance *pim, struct in_addr addr)
 252 {
 253         struct pim_nexthop_cache *pnc = NULL;
 254         struct pim_nexthop_cache lookup;
 255
 256         /*
 257          * Nothing to do here if the address to unregister
 258          * is 0.0.0.0 as that the BSR has not been registered
 259          * for tracking yet.
 260          */
 261         if (addr.s_addr == INADDR_ANY)
 262                 return;
 263
 264         lookup.rpf.rpf_addr.family = AF_INET;
 265         lookup.rpf.rpf_addr.prefixlen = IPV4_MAX_BITLEN;
 266         lookup.rpf.rpf_addr.u.prefix4 = addr;
 267
 268         pnc = hash_lookup(pim->rpf_hash, &lookup);
 269
 270         if (!pnc) {
 271                 zlog_warn("attempting to delete nonexistent NHT BSR entry %pI4",
 272                           &addr);
 273                 return;
 274         }
 275
 276         assertf(pnc->bsr_count > 0, "addr=%pI4", &addr);
 277         pnc->bsr_count--;
 278
 279         pim_nht_drop_maybe(pim, pnc);
 280 }
 281
 282 bool pim_nht_bsr_rpf_check(struct pim_instance *pim, struct in_addr bsr_addr,
 283                            struct interface *src_ifp, pim_addr src_ip)
 284 {
 285         struct pim_nexthop_cache *pnc = NULL;
 286         struct pim_nexthop_cache lookup;
 287         struct pim_neighbor *nbr = NULL;
 288         struct nexthop *nh;
 289         struct interface *ifp;
 290
 291         lookup.rpf.rpf_addr.family = AF_INET;
 292         lookup.rpf.rpf_addr.prefixlen = IPV4_MAX_BITLEN;
 293         lookup.rpf.rpf_addr.u.prefix4 = bsr_addr;
 294
 295         pnc = hash_lookup(pim->rpf_hash, &lookup);
 296         if (!pnc || !CHECK_FLAG(pnc->flags, PIM_NEXTHOP_ANSWER_RECEIVED)) {
 297                 /* BSM from a new freshly registered BSR - do a synchronous
 298                  * zebra query since otherwise we'd drop the first packet,
 299                  * leading to additional delay in picking up BSM data
 300                  */
 301
 302                 /* FIXME: this should really be moved into a generic NHT
 303                  * function that does "add and get immediate result" or maybe
 304                  * "check cache or get immediate result." But until that can
 305                  * be worked in, here's a copy of the code below :(
 306                  */
 307                 struct pim_zlookup_nexthop nexthop_tab[MULTIPATH_NUM];
 308                 ifindex_t i;
 309                 struct interface *ifp = NULL;
 310                 int num_ifindex;
 311
 312                 memset(nexthop_tab, 0, sizeof(nexthop_tab));
 313                 num_ifindex = zclient_lookup_nexthop(pim, nexthop_tab,
 314                                                      MULTIPATH_NUM, bsr_addr,
 315                                                      PIM_NEXTHOP_LOOKUP_MAX);
 316
 317                 if (num_ifindex <= 0)
 318                         return false;
 319
 320                 for (i = 0; i < num_ifindex; i++) {
 321                         struct pim_zlookup_nexthop *znh = &nexthop_tab[i];
 322
 323                         /* pim_zlookup_nexthop has no ->type */
 324
 325                         /* 1:1 match code below with znh instead of nh */
 326                         ifp = if_lookup_by_index(znh->ifindex,
 327                                                  pim->vrf->vrf_id);
 328
 329                         if (!ifp || !ifp->info)
 330                                 continue;
 331
 332                         if (if_is_loopback(ifp) && if_is_loopback(src_ifp))
 333                                 return true;
 334
 335                         nbr = pim_neighbor_find(ifp, znh->nexthop_addr);
 336                         if (!nbr)
 337                                 continue;
 338
 339                         return znh->ifindex == src_ifp->ifindex &&
 340                                (!pim_addr_cmp(znh->nexthop_addr, src_ip));
 341                 }
 342                 return false;
 343         }
 344
 345         if (!CHECK_FLAG(pnc->flags, PIM_NEXTHOP_VALID))
 346                 return false;
 347
 348         /* if we accept BSMs from more than one ECMP nexthop, this will cause
 349          * BSM message "multiplication" for each ECMP hop.  i.e. if you have
 350          * 4-way ECMP and 4 hops you end up with 256 copies of each BSM
 351          * message.
 352          *
 353          * so...  only accept the first (IPv4) valid nexthop as source.
 354          */
 355
 356         for (nh = pnc->nexthop; nh; nh = nh->next) {
 357                 pim_addr nhaddr;
 358
 359                 switch (nh->type) {
 360 #if PIM_IPV == 4
 361                 case NEXTHOP_TYPE_IPV4:
 362                         if (nh->ifindex == IFINDEX_INTERNAL)
 363                                 continue;
 364
 365                         /* fallthru */
 366                 case NEXTHOP_TYPE_IPV4_IFINDEX:
 367                         nhaddr = nh->gate.ipv4;
 368                         break;
 369 #else
 370                 case NEXTHOP_TYPE_IPV6:
 371                         if (nh->ifindex == IFINDEX_INTERNAL)
 372                                 continue;
 373
 374                         /* fallthru */
 375                 case NEXTHOP_TYPE_IPV6_IFINDEX:
 376                         nhaddr = nh->gate.ipv6;
 377                         break;
 378 #endif
 379                 case NEXTHOP_TYPE_IFINDEX:
 380                         nhaddr = bsr_addr;
 381                         break;
 382
 383                 default:
 384                         continue;
 385                 }
 386
 387                 ifp = if_lookup_by_index(nh->ifindex, pim->vrf->vrf_id);
 388                 if (!ifp || !ifp->info)
 389                         continue;
 390
 391                 if (if_is_loopback(ifp) && if_is_loopback(src_ifp))
 392                         return true;
 393
 394                 /* MRIB (IGP) may be pointing at a router where PIM is down */
 395                 nbr = pim_neighbor_find(ifp, nhaddr);
 396                 if (!nbr)
 397                         continue;
 398
 399                 return nh->ifindex == src_ifp->ifindex
 400                        && nhaddr.s_addr == src_ip.s_addr;
 401         }
 402         return false;
 403 }
 404 #endif /* PIM_IPV == 4 */
 405
 406 void pim_rp_nexthop_del(struct rp_info *rp_info)
 407 {
 408         rp_info->rp.source_nexthop.interface = NULL;
 409         rp_info->rp.source_nexthop.mrib_nexthop_addr = PIMADDR_ANY;
 410         rp_info->rp.source_nexthop.mrib_metric_preference =
 411                 router->infinite_assert_metric.metric_preference;
 412         rp_info->rp.source_nexthop.mrib_route_metric =
 413                 router->infinite_assert_metric.route_metric;
 414 }
 415
 416 /* Update RP nexthop info based on Nexthop update received from Zebra.*/
 417 static void pim_update_rp_nh(struct pim_instance *pim,
 418                              struct pim_nexthop_cache *pnc)
 419 {
 420         struct listnode *node = NULL;
 421         struct rp_info *rp_info = NULL;
 422
 423         /*Traverse RP list and update each RP Nexthop info */
 424         for (ALL_LIST_ELEMENTS_RO(pnc->rp_list, node, rp_info)) {
 425                 if (pim_rpf_addr_is_inaddr_any(&rp_info->rp))
 426                         continue;
 427
 428                 // Compute PIM RPF using cached nexthop
 429                 if (!pim_ecmp_nexthop_lookup(pim, &rp_info->rp.source_nexthop,
 430                                              &rp_info->rp.rpf_addr,
 431                                              &rp_info->group, 1))
 432                         pim_rp_nexthop_del(rp_info);
 433         }
 434 }
 435
 436 /* Update Upstream nexthop info based on Nexthop update received from Zebra.*/
 437 static int pim_update_upstream_nh_helper(struct hash_bucket *bucket, void *arg)
 438 {
 439         struct pim_instance *pim = (struct pim_instance *)arg;
 440         struct pim_upstream *up = (struct pim_upstream *)bucket->data;
 441
 442         enum pim_rpf_result rpf_result;
 443         struct pim_rpf old;
 444
 445         old.source_nexthop.interface = up->rpf.source_nexthop.interface;
 446         rpf_result = pim_rpf_update(pim, up, &old, __func__);
 447
 448         /* update kernel multicast forwarding cache (MFC); if the
 449          * RPF nbr is now unreachable the MFC has already been updated
 450          * by pim_rpf_clear
 451          */
 452         if (rpf_result != PIM_RPF_FAILURE)
 453                 pim_upstream_mroute_iif_update(up->channel_oil, __func__);
 454
 455         if (rpf_result == PIM_RPF_CHANGED ||
 456                 (rpf_result == PIM_RPF_FAILURE && old.source_nexthop.interface))
 457                 pim_zebra_upstream_rpf_changed(pim, up, &old);
 458
 459
 460         if (PIM_DEBUG_PIM_NHT) {
 461                 zlog_debug(
 462                         "%s: NHT upstream %s(%s) old ifp %s new ifp %s",
 463                         __func__, up->sg_str, pim->vrf->name,
 464                         old.source_nexthop.interface ? old.source_nexthop
 465                                                                .interface->name
 466                                                      : "Unknown",
 467                         up->rpf.source_nexthop.interface ? up->rpf.source_nexthop
 468                                                                    .interface->name
 469                                                          : "Unknown");
 470         }
 471
 472         return HASHWALK_CONTINUE;
 473 }
 474
 475 static int pim_update_upstream_nh(struct pim_instance *pim,
 476                                   struct pim_nexthop_cache *pnc)
 477 {
 478         hash_walk(pnc->upstream_hash, pim_update_upstream_nh_helper, pim);
 479
 480         pim_zebra_update_all_interfaces(pim);
 481
 482         return 0;
 483 }
 484
 485 uint32_t pim_compute_ecmp_hash(struct prefix *src, struct prefix *grp)
 486 {
 487         uint32_t hash_val;
 488
 489         if (!src)
 490                 return 0;
 491
 492         hash_val = prefix_hash_key(src);
 493         if (grp)
 494                 hash_val ^= prefix_hash_key(grp);
 495         return hash_val;
 496 }
 497
 498 static int pim_ecmp_nexthop_search(struct pim_instance *pim,
 499                                    struct pim_nexthop_cache *pnc,
 500                                    struct pim_nexthop *nexthop,
 501                                    struct prefix *src, struct prefix *grp,
 502                                    int neighbor_needed)
 503 {
 504         struct pim_neighbor *nbrs[MULTIPATH_NUM], *nbr = NULL;
 505         struct interface *ifps[MULTIPATH_NUM];
 506         struct nexthop *nh_node = NULL;
 507         ifindex_t first_ifindex;
 508         struct interface *ifp = NULL;
 509         uint32_t hash_val = 0, mod_val = 0;
 510         uint8_t nh_iter = 0, found = 0;
 511         uint32_t i, num_nbrs = 0;
 512         pim_addr nh_addr = nexthop->mrib_nexthop_addr;
 513         pim_addr src_addr = pim_addr_from_prefix(src);
 514         pim_addr grp_addr = pim_addr_from_prefix(grp);
 515
 516         if (!pnc || !pnc->nexthop_num || !nexthop)
 517                 return 0;
 518
 519         memset(&nbrs, 0, sizeof(nbrs));
 520         memset(&ifps, 0, sizeof(ifps));
 521
 522
 523         // Current Nexthop is VALID, check to stay on the current path.
 524         if (nexthop->interface && nexthop->interface->info &&
 525             (!pim_addr_is_any(nh_addr))) {
 526                 /* User configured knob to explicitly switch
 527                    to new path is disabled or current path
 528                    metric is less than nexthop update.
 529                  */
 530
 531                 if (pim->ecmp_rebalance_enable == 0) {
 532                         uint8_t curr_route_valid = 0;
 533                         // Check if current nexthop is present in new updated
 534                         // Nexthop list.
 535                         // If the current nexthop is not valid, candidate to
 536                         // choose new Nexthop.
 537                         for (nh_node = pnc->nexthop; nh_node;
 538                              nh_node = nh_node->next) {
 539                                 curr_route_valid = (nexthop->interface->ifindex
 540                                                     == nh_node->ifindex);
 541                                 if (curr_route_valid)
 542                                         break;
 543                         }
 544
 545                         if (curr_route_valid &&
 546                             !pim_if_connected_to_source(nexthop->interface,
 547                                                         src_addr)) {
 548                                 nbr = pim_neighbor_find(
 549                                         nexthop->interface,
 550                                         nexthop->mrib_nexthop_addr);
 551                                 if (!nbr
 552                                     && !if_is_loopback(nexthop->interface)) {
 553                                         if (PIM_DEBUG_PIM_NHT)
 554                                                 zlog_debug(
 555                                                         "%s: current nexthop does not have nbr ",
 556                                                         __func__);
 557                                 } else {
 558                                         /* update metric even if the upstream
 559                                          * neighbor stays unchanged
 560                                          */
 561                                         nexthop->mrib_metric_preference =
 562                                                 pnc->distance;
 563                                         nexthop->mrib_route_metric =
 564                                                 pnc->metric;
 565                                         if (PIM_DEBUG_PIM_NHT)
 566                                                 zlog_debug(
 567                                                         "%s: (%pPA,%pPA)(%s) current nexthop %s is valid, skipping new path selection",
 568                                                         __func__, &src_addr,
 569                                                         &grp_addr,
 570                                                         pim->vrf->name,
 571                                                         nexthop->interface->name);
 572                                         return 1;
 573                                 }
 574                         }
 575                 }
 576         }
 577
 578         /*
 579          * Look up all interfaces and neighbors,
 580          * store for later usage
 581          */
 582         for (nh_node = pnc->nexthop, i = 0; nh_node;
 583              nh_node = nh_node->next, i++) {
 584                 ifps[i] =
 585                         if_lookup_by_index(nh_node->ifindex, pim->vrf->vrf_id);
 586                 if (ifps[i]) {
 587 #if PIM_IPV == 4
 588                         pim_addr nhaddr = nh_node->gate.ipv4;
 589 #else
 590                         pim_addr nhaddr = nh_node->gate.ipv6;
 591 #endif
 592                         nbrs[i] = pim_neighbor_find(ifps[i], nhaddr);
 593                         if (nbrs[i] ||
 594                             pim_if_connected_to_source(ifps[i], src_addr))
 595                                 num_nbrs++;
 596                 }
 597         }
 598         if (pim->ecmp_enable) {
 599                 uint32_t consider = pnc->nexthop_num;
 600
 601                 if (neighbor_needed && num_nbrs < consider)
 602                         consider = num_nbrs;
 603
 604                 if (consider == 0)
 605                         return 0;
 606
 607                 // PIM ECMP flag is enable then choose ECMP path.
 608                 hash_val = pim_compute_ecmp_hash(src, grp);
 609                 mod_val = hash_val % consider;
 610         }
 611
 612         for (nh_node = pnc->nexthop; nh_node && (found == 0);
 613              nh_node = nh_node->next) {
 614                 first_ifindex = nh_node->ifindex;
 615                 ifp = ifps[nh_iter];
 616                 if (!ifp) {
 617                         if (PIM_DEBUG_PIM_NHT)
 618                                 zlog_debug(
 619                                         "%s %s: could not find interface for ifindex %d (address %pPA(%s))",
 620                                         __FILE__, __func__, first_ifindex,
 621                                         &src_addr, pim->vrf->name);
 622                         if (nh_iter == mod_val)
 623                                 mod_val++; // Select nexthpath
 624                         nh_iter++;
 625                         continue;
 626                 }
 627                 if (!ifp->info) {
 628                         if (PIM_DEBUG_PIM_NHT)
 629                                 zlog_debug(
 630                                         "%s: multicast not enabled on input interface %s(%s) (ifindex=%d, RPF for source %pPA)",
 631                                         __func__, ifp->name, pim->vrf->name,
 632                                         first_ifindex, &src_addr);
 633                         if (nh_iter == mod_val)
 634                                 mod_val++; // Select nexthpath
 635                         nh_iter++;
 636                         continue;
 637                 }
 638
 639                 if (neighbor_needed &&
 640                     !pim_if_connected_to_source(ifp, src_addr)) {
 641                         nbr = nbrs[nh_iter];
 642                         if (!nbr && !if_is_loopback(ifp)) {
 643                                 if (PIM_DEBUG_PIM_NHT)
 644                                         zlog_debug(
 645                                                 "%s: pim nbr not found on input interface %s(%s)",
 646                                                 __func__, ifp->name,
 647                                                 pim->vrf->name);
 648                                 if (nh_iter == mod_val)
 649                                         mod_val++; // Select nexthpath
 650                                 nh_iter++;
 651                                 continue;
 652                         }
 653                 }
 654
 655                 if (nh_iter == mod_val) {
 656                         nexthop->interface = ifp;
 657 #if PIM_IPV == 4
 658                         nexthop->mrib_nexthop_addr = nh_node->gate.ipv4;
 659 #else
 660                         nexthop->mrib_nexthop_addr = nh_node->gate.ipv6;
 661 #endif
 662                         nexthop->mrib_metric_preference = pnc->distance;
 663                         nexthop->mrib_route_metric = pnc->metric;
 664                         nexthop->last_lookup = src_addr;
 665                         nexthop->last_lookup_time = pim_time_monotonic_usec();
 666                         nexthop->nbr = nbr;
 667                         found = 1;
 668                         if (PIM_DEBUG_PIM_NHT)
 669                                 zlog_debug(
 670                                         "%s: (%pPA,%pPA)(%s) selected nhop interface %s addr %pPAs mod_val %u iter %d ecmp %d",
 671                                         __func__, &src_addr, &grp_addr,
 672                                         pim->vrf->name, ifp->name, &nh_addr,
 673                                         mod_val, nh_iter, pim->ecmp_enable);
 674                 }
 675                 nh_iter++;
 676         }
 677
 678         if (found)
 679                 return 1;
 680         else
 681                 return 0;
 682 }
 683
 684 /* This API is used to parse Registered address nexthop update coming from Zebra
 685  */
 686 int pim_parse_nexthop_update(ZAPI_CALLBACK_ARGS)
 687 {
 688         struct nexthop *nexthop;
 689         struct nexthop *nhlist_head = NULL;
 690         struct nexthop *nhlist_tail = NULL;
 691         int i;
 692         struct pim_rpf rpf;
 693         struct pim_nexthop_cache *pnc = NULL;
 694         struct interface *ifp = NULL;
 695         struct vrf *vrf = vrf_lookup_by_id(vrf_id);
 696         struct pim_instance *pim;
 697         struct zapi_route nhr;
 698         struct prefix match;
 699
 700         if (!vrf)
 701                 return 0;
 702         pim = vrf->info;
 703
 704         if (!zapi_nexthop_update_decode(zclient->ibuf, &match, &nhr)) {
 705                 zlog_err("%s: Decode of nexthop update from zebra failed",
 706                          __func__);
 707                 return 0;
 708         }
 709
 710         if (cmd == ZEBRA_NEXTHOP_UPDATE) {
 711                 prefix_copy(&rpf.rpf_addr, &match);
 712                 pnc = pim_nexthop_cache_find(pim, &rpf);
 713                 if (!pnc) {
 714                         if (PIM_DEBUG_PIM_NHT)
 715                                 zlog_debug(
 716                                         "%s: Skipping NHT update, addr %pFX is not in local cached DB.",
 717                                         __func__, &rpf.rpf_addr);
 718                         return 0;
 719                 }
 720         } else {
 721                 /*
 722                  * We do not currently handle ZEBRA_IMPORT_CHECK_UPDATE
 723                  */
 724                 return 0;
 725         }
 726
 727         pnc->last_update = pim_time_monotonic_usec();
 728
 729         if (nhr.nexthop_num) {
 730                 pnc->nexthop_num = 0; // Only increment for pim enabled rpf.
 731
 732                 for (i = 0; i < nhr.nexthop_num; i++) {
 733                         nexthop = nexthop_from_zapi_nexthop(&nhr.nexthops[i]);
 734                         switch (nexthop->type) {
 735                         case NEXTHOP_TYPE_IFINDEX:
 736                                 /*
 737                                  * Connected route (i.e. no nexthop), use
 738                                  * RPF address from nexthop cache (i.e.
 739                                  * destination) as PIM nexthop.
 740                                  */
 741 #if PIM_IPV == 4
 742                                 nexthop->type = NEXTHOP_TYPE_IPV4_IFINDEX;
 743                                 nexthop->gate.ipv4 =
 744                                         pnc->rpf.rpf_addr.u.prefix4;
 745 #else
 746                                 nexthop->type = NEXTHOP_TYPE_IPV6_IFINDEX;
 747                                 nexthop->gate.ipv6 =
 748                                         pnc->rpf.rpf_addr.u.prefix6;
 749 #endif
 750                                 break;
 751 #if PIM_IPV == 4
 752                         /* RFC5549 IPv4-over-IPv6 nexthop handling:
 753                          * if we get an IPv6 nexthop in IPv4 PIM, hunt down a
 754                          * PIM neighbor and use that instead.
 755                          */
 756                         case NEXTHOP_TYPE_IPV6_IFINDEX: {
 757                                 struct interface *ifp1 = NULL;
 758                                 struct pim_neighbor *nbr = NULL;
 759
 760                                 ifp1 = if_lookup_by_index(nexthop->ifindex,
 761                                                           pim->vrf->vrf_id);
 762
 763                                 if (!ifp1)
 764                                         nbr = NULL;
 765                                 else
 766                                         /* FIXME: should really use nbr's
 767                                          * secondary address list here
 768                                          */
 769                                         nbr = pim_neighbor_find_if(ifp1);
 770
 771                                 /* Overwrite with Nbr address as NH addr */
 772                                 if (nbr)
 773                                         nexthop->gate.ipv4 = nbr->source_addr;
 774                                 else
 775                                         // Mark nexthop address to 0 until PIM
 776                                         // Nbr is resolved.
 777                                         nexthop->gate.ipv4 = PIMADDR_ANY;
 778
 779                                 break;
 780                         }
 781 #else
 782                         case NEXTHOP_TYPE_IPV6_IFINDEX:
 783 #endif
 784                         case NEXTHOP_TYPE_IPV6:
 785                         case NEXTHOP_TYPE_IPV4:
 786                         case NEXTHOP_TYPE_IPV4_IFINDEX:
 787                         case NEXTHOP_TYPE_BLACKHOLE:
 788                                 /* nothing to do for the other nexthop types */
 789                                 break;
 790                         }
 791
 792                         ifp = if_lookup_by_index(nexthop->ifindex,
 793                                                  pim->vrf->vrf_id);
 794                         if (!ifp) {
 795                                 if (PIM_DEBUG_PIM_NHT) {
 796                                         char buf[NEXTHOP_STRLEN];
 797                                         zlog_debug(
 798                                                 "%s: could not find interface for ifindex %d(%s) (addr %s)",
 799                                                 __func__, nexthop->ifindex,
 800                                                 pim->vrf->name,
 801                                                 nexthop2str(nexthop, buf,
 802                                                             sizeof(buf)));
 803                                 }
 804                                 nexthop_free(nexthop);
 805                                 continue;
 806                         }
 807
 808                         if (PIM_DEBUG_PIM_NHT) {
 809 #if PIM_IPV == 4
 810                                 pim_addr nhaddr = nexthop->gate.ipv4;
 811 #else
 812                                 pim_addr nhaddr = nexthop->gate.ipv6;
 813 #endif
 814                                 zlog_debug(
 815                                         "%s: NHT addr %pFX(%s) %d-nhop via %pPA(%s) type %d distance:%u metric:%u ",
 816                                         __func__, &match, pim->vrf->name, i + 1,
 817                                         &nhaddr, ifp->name, nexthop->type,
 818                                         nhr.distance, nhr.metric);
 819                         }
 820
 821                         if (!ifp->info) {
 822                                 /*
 823                                  * Though Multicast is not enabled on this
 824                                  * Interface store it in database otheriwse we
 825                                  * may miss this update and this will not cause
 826                                  * any issue, because while choosing the path we
 827                                  * are ommitting the Interfaces which are not
 828                                  * multicast enabled
 829                                  */
 830                                 if (PIM_DEBUG_PIM_NHT) {
 831                                         char buf[NEXTHOP_STRLEN];
 832
 833                                         zlog_debug(
 834                                                 "%s: multicast not enabled on input interface %s(%s) (ifindex=%d, addr %s)",
 835                                                 __func__, ifp->name,
 836                                                 pim->vrf->name,
 837                                                 nexthop->ifindex,
 838                                                 nexthop2str(nexthop, buf,
 839                                                             sizeof(buf)));
 840                                 }
 841                         }
 842
 843                         if (nhlist_tail) {
 844                                 nhlist_tail->next = nexthop;
 845                                 nhlist_tail = nexthop;
 846                         } else {
 847                                 nhlist_tail = nexthop;
 848                                 nhlist_head = nexthop;
 849                         }
 850                         // Only keep track of nexthops which are PIM enabled.
 851                         pnc->nexthop_num++;
 852                 }
 853                 /* Reset existing pnc->nexthop before assigning new list */
 854                 nexthops_free(pnc->nexthop);
 855                 pnc->nexthop = nhlist_head;
 856                 if (pnc->nexthop_num) {
 857                         pnc->flags |= PIM_NEXTHOP_VALID;
 858                         pnc->distance = nhr.distance;
 859                         pnc->metric = nhr.metric;
 860                 }
 861         } else {
 862                 pnc->flags &= ~PIM_NEXTHOP_VALID;
 863                 pnc->nexthop_num = nhr.nexthop_num;
 864                 nexthops_free(pnc->nexthop);
 865                 pnc->nexthop = NULL;
 866         }
 867         SET_FLAG(pnc->flags, PIM_NEXTHOP_ANSWER_RECEIVED);
 868
 869         if (PIM_DEBUG_PIM_NHT)
 870                 zlog_debug(
 871                         "%s: NHT Update for %pFX(%s) num_nh %d num_pim_nh %d vrf:%u up %ld rp %d",
 872                         __func__, &match, pim->vrf->name, nhr.nexthop_num,
 873                         pnc->nexthop_num, vrf_id, pnc->upstream_hash->count,
 874                         listcount(pnc->rp_list));
 875
 876         pim_rpf_set_refresh_time(pim);
 877
 878         if (listcount(pnc->rp_list))
 879                 pim_update_rp_nh(pim, pnc);
 880         if (pnc->upstream_hash->count)
 881                 pim_update_upstream_nh(pim, pnc);
 882
 883         return 0;
 884 }
 885
 886 int pim_ecmp_nexthop_lookup(struct pim_instance *pim,
 887                             struct pim_nexthop *nexthop, struct prefix *src,
 888                             struct prefix *grp, int neighbor_needed)
 889 {
 890         struct pim_nexthop_cache *pnc;
 891         struct pim_zlookup_nexthop nexthop_tab[MULTIPATH_NUM];
 892         struct pim_neighbor *nbrs[MULTIPATH_NUM], *nbr = NULL;
 893         struct pim_rpf rpf;
 894         int num_ifindex;
 895         struct interface *ifps[MULTIPATH_NUM], *ifp;
 896         int first_ifindex;
 897         int found = 0;
 898         uint8_t i = 0;
 899         uint32_t hash_val = 0, mod_val = 0;
 900         uint32_t num_nbrs = 0;
 901         pim_addr src_addr = pim_addr_from_prefix(src);
 902
 903         if (PIM_DEBUG_PIM_NHT_DETAIL)
 904                 zlog_debug("%s: Looking up: %pPA(%s), last lookup time: %lld",
 905                            __func__, &src_addr, pim->vrf->name,
 906                            nexthop->last_lookup_time);
 907
 908         rpf.rpf_addr = *src;
 909
 910         pnc = pim_nexthop_cache_find(pim, &rpf);
 911         if (pnc) {
 912                 if (CHECK_FLAG(pnc->flags, PIM_NEXTHOP_ANSWER_RECEIVED))
 913                     return pim_ecmp_nexthop_search(pim, pnc, nexthop, src, grp,
 914                                                    neighbor_needed);
 915         }
 916
 917         memset(nexthop_tab, 0,
 918                sizeof(struct pim_zlookup_nexthop) * MULTIPATH_NUM);
 919         num_ifindex = zclient_lookup_nexthop(pim, nexthop_tab, MULTIPATH_NUM,
 920                                              src_addr, PIM_NEXTHOP_LOOKUP_MAX);
 921         if (num_ifindex < 1) {
 922                 if (PIM_DEBUG_PIM_NHT)
 923                         zlog_warn(
 924                                 "%s: could not find nexthop ifindex for address %pPA(%s)",
 925                                 __func__, &src_addr, pim->vrf->name);
 926                 return 0;
 927         }
 928
 929         memset(&nbrs, 0, sizeof(nbrs));
 930         memset(&ifps, 0, sizeof(ifps));
 931
 932         /*
 933          * Look up all interfaces and neighbors,
 934          * store for later usage
 935          */
 936         for (i = 0; i < num_ifindex; i++) {
 937                 ifps[i] = if_lookup_by_index(nexthop_tab[i].ifindex,
 938                                              pim->vrf->vrf_id);
 939                 if (ifps[i]) {
 940                         nbrs[i] = pim_neighbor_find(
 941                                 ifps[i], nexthop_tab[i].nexthop_addr);
 942                         if (nbrs[i] ||
 943                             pim_if_connected_to_source(ifps[i], src_addr))
 944                                 num_nbrs++;
 945                 }
 946         }
 947
 948         // If PIM ECMP enable then choose ECMP path.
 949         if (pim->ecmp_enable) {
 950                 uint32_t consider = num_ifindex;
 951
 952                 if (neighbor_needed && num_nbrs < consider)
 953                         consider = num_nbrs;
 954
 955                 if (consider == 0)
 956                         return 0;
 957
 958                 hash_val = pim_compute_ecmp_hash(src, grp);
 959                 mod_val = hash_val % consider;
 960                 if (PIM_DEBUG_PIM_NHT_DETAIL)
 961                         zlog_debug("%s: hash_val %u mod_val %u", __func__,
 962                                    hash_val, mod_val);
 963         }
 964
 965         i = 0;
 966         while (!found && (i < num_ifindex)) {
 967                 first_ifindex = nexthop_tab[i].ifindex;
 968
 969                 ifp = ifps[i];
 970                 if (!ifp) {
 971                         if (PIM_DEBUG_PIM_NHT)
 972                                 zlog_debug(
 973                                         "%s %s: could not find interface for ifindex %d (address %pPA(%s))",
 974                                         __FILE__, __func__, first_ifindex,
 975                                         &src_addr, pim->vrf->name);
 976                         if (i == mod_val)
 977                                 mod_val++;
 978                         i++;
 979                         continue;
 980                 }
 981
 982                 if (!ifp->info) {
 983                         if (PIM_DEBUG_PIM_NHT)
 984                                 zlog_debug(
 985                                         "%s: multicast not enabled on input interface %s(%s) (ifindex=%d, RPF for source %pPA)",
 986                                         __func__, ifp->name, pim->vrf->name,
 987                                         first_ifindex, &src_addr);
 988                         if (i == mod_val)
 989                                 mod_val++;
 990                         i++;
 991                         continue;
 992                 }
 993                 if (neighbor_needed &&
 994                     !pim_if_connected_to_source(ifp, src_addr)) {
 995                         nbr = nbrs[i];
 996                         if (PIM_DEBUG_PIM_NHT_DETAIL)
 997                                 zlog_debug("ifp name: %s(%s), pim nbr: %p",
 998                                            ifp->name, pim->vrf->name, nbr);
 999                         if (!nbr && !if_is_loopback(ifp)) {
1000                                 if (i == mod_val)
1001                                         mod_val++;
1002                                 if (PIM_DEBUG_PIM_NHT)
1003                                         zlog_debug(
1004                                                 "%s: NBR (%pPA) not found on input interface %s(%s) (RPF for source %pPA)",
1005                                                 __func__,
1006                                                 &nexthop_tab[i].nexthop_addr,
1007                                                 ifp->name, pim->vrf->name,
1008                                                 &src_addr);
1009                                 i++;
1010                                 continue;
1011                         }
1012                 }
1013
1014                 if (i == mod_val) {
1015                         if (PIM_DEBUG_PIM_NHT)
1016                                 zlog_debug(
1017                                         "%s: found nhop %pPA for addr %pPA interface %s(%s) metric %d dist %d",
1018                                         __func__, &nexthop_tab[i].nexthop_addr,
1019                                         &src_addr, ifp->name, pim->vrf->name,
1020                                         nexthop_tab[i].route_metric,
1021                                         nexthop_tab[i].protocol_distance);
1022                         /* update nexthop data */
1023                         nexthop->interface = ifp;
1024                         nexthop->mrib_nexthop_addr =
1025                                 nexthop_tab[i].nexthop_addr;
1026                         nexthop->mrib_metric_preference =
1027                                 nexthop_tab[i].protocol_distance;
1028                         nexthop->mrib_route_metric =
1029                                 nexthop_tab[i].route_metric;
1030                         nexthop->last_lookup = src_addr;
1031                         nexthop->last_lookup_time = pim_time_monotonic_usec();
1032                         nexthop->nbr = nbr;
1033                         found = 1;
1034                 }
1035                 i++;
1036         }
1037
1038         if (found)
1039                 return 1;
1040         else
1041                 return 0;
1042 }
1043
1044 int pim_ecmp_fib_lookup_if_vif_index(struct pim_instance *pim,
1045                                      struct prefix *src, struct prefix *grp)
1046 {
1047         struct pim_nexthop nhop;
1048         int vif_index;
1049         ifindex_t ifindex;
1050         pim_addr src_addr;
1051
1052         if (PIM_DEBUG_PIM_NHT_DETAIL) {
1053                 src_addr = pim_addr_from_prefix(src);
1054         }
1055
1056         memset(&nhop, 0, sizeof(nhop));
1057         if (!pim_ecmp_nexthop_lookup(pim, &nhop, src, grp, 1)) {
1058                 if (PIM_DEBUG_PIM_NHT)
1059                         zlog_debug(
1060                                 "%s: could not find nexthop ifindex for address %pPA(%s)",
1061                                 __func__, &src_addr, pim->vrf->name);
1062                 return -1;
1063         }
1064
1065         ifindex = nhop.interface->ifindex;
1066         if (PIM_DEBUG_PIM_NHT)
1067                 zlog_debug(
1068                         "%s: found nexthop ifindex=%d (interface %s(%s)) for address %pPA",
1069                         __func__, ifindex,
1070                         ifindex2ifname(ifindex, pim->vrf->vrf_id),
1071                         pim->vrf->name, &src_addr);
1072
1073         vif_index = pim_if_find_vifindex_by_ifindex(pim, ifindex);
1074
1075         if (vif_index < 0) {
1076                 if (PIM_DEBUG_PIM_NHT) {
1077                         zlog_debug(
1078                                 "%s: low vif_index=%d(%s) < 1 nexthop for address %pPA",
1079                                 __func__, vif_index, pim->vrf->name, &src_addr);
1080                 }
1081                 return -2;
1082         }
1083
1084         return vif_index;
1085 }