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