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