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         memset(&nbrs, 0, sizeof(nbrs));
 434         memset(&ifps, 0, sizeof(ifps));
 435
 436         // Current Nexthop is VALID, check to stay on the current path.
 437         if (nexthop->interface && nexthop->interface->info
 438             && nexthop->mrib_nexthop_addr.u.prefix4.s_addr
 439                        != PIM_NET_INADDR_ANY) {
 440                 /* User configured knob to explicitly switch
 441                    to new path is disabled or current path
 442                    metric is less than nexthop update.
 443                  */
 444
 445                 if (pim->ecmp_rebalance_enable == 0) {
 446                         uint8_t curr_route_valid = 0;
 447                         // Check if current nexthop is present in new updated
 448                         // Nexthop list.
 449                         // If the current nexthop is not valid, candidate to
 450                         // choose new Nexthop.
 451                         for (nh_node = pnc->nexthop; nh_node;
 452                              nh_node = nh_node->next) {
 453                                 curr_route_valid = (nexthop->interface->ifindex
 454                                                     == nh_node->ifindex);
 455                                 if (curr_route_valid)
 456                                         break;
 457                         }
 458
 459                         if (curr_route_valid
 460                             && !pim_if_connected_to_source(nexthop->interface,
 461                                                            src->u.prefix4)) {
 462                                 nbr = pim_neighbor_find(
 463                                         nexthop->interface,
 464                                         nexthop->mrib_nexthop_addr.u.prefix4);
 465                                 if (!nbr
 466                                     && !if_is_loopback(nexthop->interface)) {
 467                                         if (PIM_DEBUG_PIM_NHT)
 468                                                 zlog_debug(
 469                                                         "%s: current nexthop does not have nbr ",
 470                                                         __PRETTY_FUNCTION__);
 471                                 } else {
 472                                         if (PIM_DEBUG_PIM_NHT) {
 473                                                 char src_str[INET_ADDRSTRLEN];
 474                                                 pim_inet4_dump("<addr?>",
 475                                                                src->u.prefix4,
 476                                                                src_str,
 477                                                                sizeof(src_str));
 478                                                 char grp_str[INET_ADDRSTRLEN];
 479                                                 pim_inet4_dump("<addr?>",
 480                                                                grp->u.prefix4,
 481                                                                grp_str,
 482                                                                sizeof(grp_str));
 483                                                 zlog_debug(
 484                                                         "%s: (%s,%s)(%s) current nexthop %s is valid, skipping new path selection",
 485                                                         __PRETTY_FUNCTION__,
 486                                                         src_str, grp_str,
 487                                                         pim->vrf->name,
 488                                                         nexthop->interface->name);
 489                                         }
 490                                         return 1;
 491                                 }
 492                         }
 493                 }
 494         }
 495
 496         /*
 497          * Look up all interfaces and neighbors,
 498          * store for later usage
 499          */
 500         for (nh_node = pnc->nexthop, i = 0; nh_node;
 501              nh_node = nh_node->next, i++) {
 502                 ifps[i] = if_lookup_by_index(nh_node->ifindex, pim->vrf_id);
 503                 if (ifps[i]) {
 504                         nbrs[i] = pim_neighbor_find(ifps[i],
 505                                                     nh_node->gate.ipv4);
 506                         if (nbrs[i] || pim_if_connected_to_source(ifps[i],
 507
 508                                                                   src->u.prefix4))
 509                                 num_nbrs++;
 510                 }
 511         }
 512         if (pim->ecmp_enable) {
 513                 uint32_t consider = pnc->nexthop_num;
 514
 515                 if (neighbor_needed && num_nbrs < consider)
 516                         consider = num_nbrs;
 517
 518                 if (consider == 0)
 519                         return 0;
 520
 521                 // PIM ECMP flag is enable then choose ECMP path.
 522                 hash_val = pim_compute_ecmp_hash(src, grp);
 523                 mod_val = hash_val % consider;
 524         }
 525
 526         for (nh_node = pnc->nexthop; nh_node && (found == 0);
 527              nh_node = nh_node->next) {
 528                 first_ifindex = nh_node->ifindex;
 529                 ifp = ifps[nh_iter];
 530                 if (!ifp) {
 531                         if (PIM_DEBUG_PIM_NHT) {
 532                                 char addr_str[INET_ADDRSTRLEN];
 533                                 pim_inet4_dump("<addr?>", src->u.prefix4,
 534                                                addr_str, sizeof(addr_str));
 535                                 zlog_debug(
 536                                         "%s %s: could not find interface for ifindex %d (address %s(%s))",
 537                                         __FILE__, __PRETTY_FUNCTION__,
 538                                         first_ifindex, addr_str,
 539                                         pim->vrf->name);
 540                         }
 541                         if (nh_iter == mod_val)
 542                                 mod_val++; // Select nexthpath
 543                         nh_iter++;
 544                         continue;
 545                 }
 546                 if (!ifp->info) {
 547                         if (PIM_DEBUG_PIM_NHT) {
 548                                 char addr_str[INET_ADDRSTRLEN];
 549                                 pim_inet4_dump("<addr?>", src->u.prefix4,
 550                                                addr_str, sizeof(addr_str));
 551                                 zlog_debug(
 552                                         "%s: multicast not enabled on input interface %s(%s) (ifindex=%d, RPF for source %s)",
 553                                         __PRETTY_FUNCTION__, ifp->name,
 554                                         pim->vrf->name, first_ifindex,
 555                                         addr_str);
 556                         }
 557                         if (nh_iter == mod_val)
 558                                 mod_val++; // Select nexthpath
 559                         nh_iter++;
 560                         continue;
 561                 }
 562
 563                 if (neighbor_needed
 564                     && !pim_if_connected_to_source(ifp, src->u.prefix4)) {
 565                         nbr = nbrs[nh_iter];
 566                         if (!nbr && !if_is_loopback(ifp)) {
 567                                 if (PIM_DEBUG_PIM_NHT)
 568                                         zlog_debug(
 569                                                 "%s: pim nbr not found on input interface %s(%s)",
 570                                                 __PRETTY_FUNCTION__, ifp->name,
 571                                                 pim->vrf->name);
 572                                 if (nh_iter == mod_val)
 573                                         mod_val++; // Select nexthpath
 574                                 nh_iter++;
 575                                 continue;
 576                         }
 577                 }
 578
 579                 if (nh_iter == mod_val) {
 580                         nexthop->interface = ifp;
 581                         nexthop->mrib_nexthop_addr.family = AF_INET;
 582                         nexthop->mrib_nexthop_addr.prefixlen = IPV4_MAX_BITLEN;
 583                         nexthop->mrib_nexthop_addr.u.prefix4 =
 584                                 nh_node->gate.ipv4;
 585                         nexthop->mrib_metric_preference = pnc->distance;
 586                         nexthop->mrib_route_metric = pnc->metric;
 587                         nexthop->last_lookup = src->u.prefix4;
 588                         nexthop->last_lookup_time = pim_time_monotonic_usec();
 589                         nexthop->nbr = nbr;
 590                         found = 1;
 591                         if (PIM_DEBUG_PIM_NHT) {
 592                                 char buf[INET_ADDRSTRLEN];
 593                                 char buf2[INET_ADDRSTRLEN];
 594                                 char buf3[INET_ADDRSTRLEN];
 595                                 pim_inet4_dump("<src?>", src->u.prefix4, buf2,
 596                                                sizeof(buf2));
 597                                 pim_inet4_dump("<grp?>", grp->u.prefix4, buf3,
 598                                                sizeof(buf3));
 599                                 pim_inet4_dump(
 600                                         "<rpf?>",
 601                                         nexthop->mrib_nexthop_addr.u.prefix4,
 602                                         buf, sizeof(buf));
 603                                 zlog_debug(
 604                                         "%s: (%s,%s)(%s) selected nhop interface %s addr %s mod_val %u iter %d ecmp %d",
 605                                         __PRETTY_FUNCTION__, buf2, buf3,
 606                                         pim->vrf->name, ifp->name, buf, mod_val,
 607                                         nh_iter, pim->ecmp_enable);
 608                         }
 609                 }
 610                 nh_iter++;
 611         }
 612
 613         if (found)
 614                 return 1;
 615         else
 616                 return 0;
 617 }
 618
 619 /* This API is used to parse Registered address nexthop update coming from Zebra
 620  */
 621 int pim_parse_nexthop_update(int command, struct zclient *zclient,
 622                              zebra_size_t length, vrf_id_t vrf_id)
 623 {
 624         struct nexthop *nexthop;
 625         struct nexthop *nhlist_head = NULL;
 626         struct nexthop *nhlist_tail = NULL;
 627         int i;
 628         struct pim_rpf rpf;
 629         struct pim_nexthop_cache *pnc = NULL;
 630         struct pim_neighbor *nbr = NULL;
 631         struct interface *ifp = NULL;
 632         struct interface *ifp1 = NULL;
 633         struct vrf *vrf = vrf_lookup_by_id(vrf_id);
 634         struct pim_instance *pim;
 635         struct zapi_route nhr;
 636
 637         if (!vrf)
 638                 return 0;
 639         pim = vrf->info;
 640
 641         if (!zapi_nexthop_update_decode(zclient->ibuf, &nhr)) {
 642                 if (PIM_DEBUG_PIM_NHT)
 643                         zlog_debug(
 644                                 "%s: Decode of nexthop update from zebra failed",
 645                                 __PRETTY_FUNCTION__);
 646                 return 0;
 647         }
 648
 649         if (command == ZEBRA_NEXTHOP_UPDATE) {
 650                 prefix_copy(&rpf.rpf_addr, &nhr.prefix);
 651                 pnc = pim_nexthop_cache_find(pim, &rpf);
 652                 if (!pnc) {
 653                         if (PIM_DEBUG_PIM_NHT) {
 654                                 char buf[PREFIX2STR_BUFFER];
 655                                 prefix2str(&rpf.rpf_addr, buf, sizeof(buf));
 656                                 zlog_debug(
 657                                         "%s: Skipping NHT update, addr %s is not in local cached DB.",
 658                                         __PRETTY_FUNCTION__, buf);
 659                         }
 660                         return 0;
 661                 }
 662         } else {
 663                 /*
 664                  * We do not currently handle ZEBRA_IMPORT_CHECK_UPDATE
 665                  */
 666                 return 0;
 667         }
 668
 669         pnc->last_update = pim_time_monotonic_usec();
 670
 671         if (nhr.nexthop_num) {
 672                 pnc->nexthop_num = 0; // Only increment for pim enabled rpf.
 673
 674                 for (i = 0; i < nhr.nexthop_num; i++) {
 675                         nexthop = nexthop_from_zapi_nexthop(&nhr.nexthops[i]);
 676                         switch (nexthop->type) {
 677                         case NEXTHOP_TYPE_IPV4:
 678                         case NEXTHOP_TYPE_IPV4_IFINDEX:
 679                         case NEXTHOP_TYPE_IPV6:
 680                         case NEXTHOP_TYPE_BLACKHOLE:
 681                                 break;
 682                         case NEXTHOP_TYPE_IFINDEX:
 683                                 /*
 684                                  * Connected route (i.e. no nexthop), use
 685                                  * RPF address from nexthop cache (i.e.
 686                                  * destination) as PIM nexthop.
 687                                  */
 688                                 nexthop->type = NEXTHOP_TYPE_IPV4_IFINDEX;
 689                                 nexthop->gate.ipv4 =
 690                                         pnc->rpf.rpf_addr.u.prefix4;
 691                                 break;
 692                         case NEXTHOP_TYPE_IPV6_IFINDEX:
 693                                 ifp1 = if_lookup_by_index(nexthop->ifindex,
 694                                                           pim->vrf_id);
 695                                 nbr = pim_neighbor_find_if(ifp1);
 696                                 /* Overwrite with Nbr address as NH addr */
 697                                 if (nbr)
 698                                         nexthop->gate.ipv4 = nbr->source_addr;
 699                                 else {
 700                                         // Mark nexthop address to 0 until PIM
 701                                         // Nbr is resolved.
 702                                         nexthop->gate.ipv4.s_addr =
 703                                                 PIM_NET_INADDR_ANY;
 704                                 }
 705
 706                                 break;
 707                         }
 708
 709                         ifp = if_lookup_by_index(nexthop->ifindex, pim->vrf_id);
 710                         if (!ifp) {
 711                                 if (PIM_DEBUG_PIM_NHT) {
 712                                         char buf[NEXTHOP_STRLEN];
 713                                         zlog_debug(
 714                                                 "%s: could not find interface for ifindex %d(%s) (addr %s)",
 715                                                 __PRETTY_FUNCTION__,
 716                                                 nexthop->ifindex,
 717                                                 pim->vrf->name,
 718                                                 nexthop2str(nexthop, buf,
 719                                                             sizeof(buf)));
 720                                 }
 721                                 nexthop_free(nexthop);
 722                                 continue;
 723                         }
 724
 725                         if (PIM_DEBUG_PIM_NHT) {
 726                                 char p_str[PREFIX2STR_BUFFER];
 727
 728                                 prefix2str(&nhr.prefix, p_str, sizeof(p_str));
 729                                 zlog_debug(
 730                                         "%s: NHT addr %s(%s) %d-nhop via %s(%s) type %d distance:%u metric:%u ",
 731                                         __PRETTY_FUNCTION__, p_str,
 732                                         pim->vrf->name, i + 1,
 733                                         inet_ntoa(nexthop->gate.ipv4),
 734                                         ifp->name, nexthop->type, nhr.distance,
 735                                         nhr.metric);
 736                         }
 737
 738                         if (!ifp->info) {
 739                                 if (PIM_DEBUG_PIM_NHT) {
 740                                         char buf[NEXTHOP_STRLEN];
 741
 742                                         zlog_debug(
 743                                                 "%s: multicast not enabled on input interface %s(%s) (ifindex=%d, addr %s)",
 744                                                 __PRETTY_FUNCTION__, ifp->name,
 745                                                 pim->vrf->name,
 746                                                 nexthop->ifindex,
 747                                                 nexthop2str(nexthop, buf,
 748                                                             sizeof(buf)));
 749                                 }
 750                                 nexthop_free(nexthop);
 751                                 continue;
 752                         }
 753
 754                         if (nhlist_tail) {
 755                                 nhlist_tail->next = nexthop;
 756                                 nhlist_tail = nexthop;
 757                         } else {
 758                                 nhlist_tail = nexthop;
 759                                 nhlist_head = nexthop;
 760                         }
 761                         // Only keep track of nexthops which are PIM enabled.
 762                         pnc->nexthop_num++;
 763                 }
 764                 /* Reset existing pnc->nexthop before assigning new list */
 765                 nexthops_free(pnc->nexthop);
 766                 pnc->nexthop = nhlist_head;
 767                 if (pnc->nexthop_num) {
 768                         pnc->flags |= PIM_NEXTHOP_VALID;
 769                         pnc->distance = nhr.distance;
 770                         pnc->metric = nhr.metric;
 771                 }
 772         } else {
 773                 pnc->flags &= ~PIM_NEXTHOP_VALID;
 774                 pnc->nexthop_num = nhr.nexthop_num;
 775                 nexthops_free(pnc->nexthop);
 776                 pnc->nexthop = NULL;
 777         }
 778
 779         if (PIM_DEBUG_PIM_NHT) {
 780                 char buf[PREFIX2STR_BUFFER];
 781                 prefix2str(&nhr.prefix, buf, sizeof(buf));
 782                 zlog_debug(
 783                         "%s: NHT Update for %s(%s) num_nh %d num_pim_nh %d vrf:%u up %ld rp %d",
 784                         __PRETTY_FUNCTION__, buf, pim->vrf->name,
 785                         nhr.nexthop_num, pnc->nexthop_num, vrf_id,
 786                         pnc->upstream_hash->count, listcount(pnc->rp_list));
 787         }
 788
 789         pim_rpf_set_refresh_time(pim);
 790
 791         if (listcount(pnc->rp_list))
 792                 pim_update_rp_nh(pim, pnc);
 793         if (pnc->upstream_hash->count)
 794                 pim_update_upstream_nh(pim, pnc);
 795
 796         return 0;
 797 }
 798
 799 int pim_ecmp_nexthop_lookup(struct pim_instance *pim,
 800                             struct pim_nexthop *nexthop, struct prefix *src,
 801                             struct prefix *grp, int neighbor_needed)
 802 {
 803         struct pim_zlookup_nexthop nexthop_tab[MULTIPATH_NUM];
 804         struct pim_neighbor *nbrs[MULTIPATH_NUM], *nbr = NULL;
 805         int num_ifindex;
 806         struct interface *ifps[MULTIPATH_NUM], *ifp;
 807         int first_ifindex;
 808         int found = 0;
 809         uint8_t i = 0;
 810         uint32_t hash_val = 0, mod_val = 0;
 811         uint32_t num_nbrs = 0;
 812         char addr_str[PREFIX_STRLEN];
 813
 814         if (PIM_DEBUG_PIM_NHT) {
 815                 pim_inet4_dump("<addr?>", src->u.prefix4, addr_str,
 816                                sizeof(addr_str));
 817                 zlog_debug("%s: Looking up: %s(%s), last lookup time: %lld",
 818                            __PRETTY_FUNCTION__, addr_str, pim->vrf->name,
 819                            nexthop->last_lookup_time);
 820         }
 821
 822         memset(nexthop_tab, 0,
 823                sizeof(struct pim_zlookup_nexthop) * MULTIPATH_NUM);
 824         num_ifindex =
 825                 zclient_lookup_nexthop(pim, nexthop_tab, MULTIPATH_NUM,
 826                                        src->u.prefix4, PIM_NEXTHOP_LOOKUP_MAX);
 827         if (num_ifindex < 1) {
 828                 if (PIM_DEBUG_PIM_NHT)
 829                         zlog_warn(
 830                                 "%s: could not find nexthop ifindex for address %s(%s)",
 831                                 __PRETTY_FUNCTION__, addr_str, pim->vrf->name);
 832                 return 0;
 833         }
 834
 835         memset(&nbrs, 0, sizeof(nbrs));
 836         memset(&ifps, 0, sizeof(ifps));
 837
 838         /*
 839          * Look up all interfaces and neighbors,
 840          * store for later usage
 841          */
 842         for (i = 0; i < num_ifindex; i++) {
 843                 ifps[i] = if_lookup_by_index(nexthop_tab[i].ifindex,
 844                                              pim->vrf_id);
 845                 if (ifps[i]) {
 846                         nbrs[i] = pim_neighbor_find(
 847                                 ifps[i], nexthop_tab[i].nexthop_addr.u.prefix4);
 848                         if (nbrs[i]
 849                             || pim_if_connected_to_source(ifps[i],
 850                                                           src->u.prefix4))
 851                                 num_nbrs++;
 852                 }
 853         }
 854
 855         // If PIM ECMP enable then choose ECMP path.
 856         if (pim->ecmp_enable) {
 857                 uint32_t consider = num_ifindex;
 858
 859                 if (neighbor_needed && num_nbrs < consider)
 860                         consider = num_nbrs;
 861
 862                 if (consider == 0)
 863                         return 0;
 864
 865                 hash_val = pim_compute_ecmp_hash(src, grp);
 866                 mod_val = hash_val % consider;
 867                 if (PIM_DEBUG_PIM_NHT_DETAIL)
 868                         zlog_debug("%s: hash_val %u mod_val %u",
 869                                    __PRETTY_FUNCTION__, hash_val, mod_val);
 870         }
 871
 872         i = 0;
 873         while (!found && (i < num_ifindex)) {
 874                 first_ifindex = nexthop_tab[i].ifindex;
 875
 876                 ifp = ifps[i];
 877                 if (!ifp) {
 878                         if (PIM_DEBUG_PIM_NHT)
 879                                 zlog_debug(
 880                                         "%s %s: could not find interface for ifindex %d (address %s(%s))",
 881                                         __FILE__, __PRETTY_FUNCTION__,
 882                                         first_ifindex, addr_str,
 883                                         pim->vrf->name);
 884                         if (i == mod_val)
 885                                 mod_val++;
 886                         i++;
 887                         continue;
 888                 }
 889
 890                 if (!ifp->info) {
 891                         if (PIM_DEBUG_PIM_NHT)
 892                                 zlog_debug(
 893                                         "%s: multicast not enabled on input interface %s(%s) (ifindex=%d, RPF for source %s)",
 894                                         __PRETTY_FUNCTION__, ifp->name,
 895                                         pim->vrf->name, first_ifindex,
 896                                         addr_str);
 897                         if (i == mod_val)
 898                                 mod_val++;
 899                         i++;
 900                         continue;
 901                 }
 902                 if (neighbor_needed
 903                     && !pim_if_connected_to_source(ifp, src->u.prefix4)) {
 904                         nbr = nbrs[i];
 905                         if (PIM_DEBUG_PIM_NHT_DETAIL)
 906                                 zlog_debug("ifp name: %s(%s), pim nbr: %p",
 907                                            ifp->name, pim->vrf->name, nbr);
 908                         if (!nbr && !if_is_loopback(ifp)) {
 909                                 if (i == mod_val)
 910                                         mod_val++;
 911                                 i++;
 912                                 if (PIM_DEBUG_PIM_NHT)
 913                                         zlog_debug(
 914                                                 "%s: NBR not found on input interface %s(%s) (RPF for source %s)",
 915                                                 __PRETTY_FUNCTION__, ifp->name,
 916                                                 pim->vrf->name, addr_str);
 917                                 continue;
 918                         }
 919                 }
 920
 921                 if (i == mod_val) {
 922                         if (PIM_DEBUG_PIM_NHT) {
 923                                 char nexthop_str[PREFIX_STRLEN];
 924
 925                                 pim_addr_dump("<nexthop?>",
 926                                               &nexthop_tab[i].nexthop_addr,
 927                                               nexthop_str, sizeof(nexthop_str));
 928                                 zlog_debug(
 929                                         "%s: found nhop %s for addr %s interface %s(%s) metric %d dist %d",
 930                                         __PRETTY_FUNCTION__, nexthop_str,
 931                                         addr_str, ifp->name, pim->vrf->name,
 932                                         nexthop_tab[i].route_metric,
 933                                         nexthop_tab[i].protocol_distance);
 934                         }
 935                         /* update nexthop data */
 936                         nexthop->interface = ifp;
 937                         nexthop->mrib_nexthop_addr =
 938                                 nexthop_tab[i].nexthop_addr;
 939                         nexthop->mrib_metric_preference =
 940                                 nexthop_tab[i].protocol_distance;
 941                         nexthop->mrib_route_metric =
 942                                 nexthop_tab[i].route_metric;
 943                         nexthop->last_lookup = src->u.prefix4;
 944                         nexthop->last_lookup_time = pim_time_monotonic_usec();
 945                         nexthop->nbr = nbr;
 946                         found = 1;
 947                 }
 948                 i++;
 949         }
 950
 951         if (found)
 952                 return 1;
 953         else
 954                 return 0;
 955 }
 956
 957 int pim_ecmp_fib_lookup_if_vif_index(struct pim_instance *pim,
 958                                      struct prefix *src, struct prefix *grp)
 959 {
 960         struct pim_nexthop nhop;
 961         int vif_index;
 962         ifindex_t ifindex;
 963         char addr_str[PREFIX_STRLEN];
 964
 965         if (PIM_DEBUG_PIM_NHT)
 966                 pim_inet4_dump("<addr?>", src->u.prefix4, addr_str,
 967                                sizeof(addr_str));
 968         if (!pim_ecmp_nexthop_lookup(pim, &nhop, src, grp, 0)) {
 969                 if (PIM_DEBUG_PIM_NHT)
 970                         zlog_debug(
 971                                 "%s: could not find nexthop ifindex for address %s(%s)",
 972                                 __PRETTY_FUNCTION__, addr_str, pim->vrf->name);
 973                 return -1;
 974         }
 975
 976         ifindex = nhop.interface->ifindex;
 977         if (PIM_DEBUG_PIM_NHT)
 978                 zlog_debug(
 979                         "%s: found nexthop ifindex=%d (interface %s(%s)) for address %s",
 980                         __PRETTY_FUNCTION__, ifindex,
 981                         ifindex2ifname(ifindex, pim->vrf_id),
 982                         pim->vrf->name, addr_str);
 983
 984         vif_index = pim_if_find_vifindex_by_ifindex(pim, ifindex);
 985
 986         if (vif_index < 0) {
 987                 if (PIM_DEBUG_PIM_NHT) {
 988                         zlog_debug(
 989                                 "%s: low vif_index=%d(%s) < 1 nexthop for address %s",
 990                                 __PRETTY_FUNCTION__, vif_index, pim->vrf->name,
 991                                 addr_str);
 992                 }
 993                 return -2;
 994         }
 995
 996         return vif_index;
 997 }