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