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