pimd/pim_rpf.c

   1 /*
   2  * PIM for Quagga
   3  * Copyright (C) 2008  Everton da Silva Marques
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; see the file COPYING; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  18  */
  19
  20 #include <zebra.h>
  21
  22 #include "if.h"
  23
  24 #include "log.h"
  25 #include "prefix.h"
  26 #include "memory.h"
  27 #include "jhash.h"
  28
  29 #include "pimd.h"
  30 #include "pim_instance.h"
  31 #include "pim_rpf.h"
  32 #include "pim_pim.h"
  33 #include "pim_str.h"
  34 #include "pim_iface.h"
  35 #include "pim_neighbor.h"
  36 #include "pim_zlookup.h"
  37 #include "pim_ifchannel.h"
  38 #include "pim_time.h"
  39 #include "pim_nht.h"
  40 #include "pim_oil.h"
  41 #include "pim_mlag.h"
  42
  43 static pim_addr pim_rpf_find_rpf_addr(struct pim_upstream *up);
  44
  45 void pim_rpf_set_refresh_time(struct pim_instance *pim)
  46 {
  47         pim->last_route_change_time = pim_time_monotonic_usec();
  48         if (PIM_DEBUG_PIM_TRACE)
  49                 zlog_debug("%s: vrf(%s) New last route change time: %" PRId64,
  50                            __func__, pim->vrf->name,
  51                            pim->last_route_change_time);
  52 }
  53
  54 bool pim_nexthop_lookup(struct pim_instance *pim, struct pim_nexthop *nexthop,
  55                         pim_addr addr, int neighbor_needed)
  56 {
  57         struct pim_zlookup_nexthop nexthop_tab[router->multipath];
  58         struct pim_neighbor *nbr = NULL;
  59         int num_ifindex;
  60         struct interface *ifp = NULL;
  61         ifindex_t first_ifindex = 0;
  62         int found = 0;
  63         int i = 0;
  64         struct pim_interface *pim_ifp;
  65
  66 #if PIM_IPV == 4
  67         /*
  68          * We should not attempt to lookup a
  69          * 255.255.255.255 address, since
  70          * it will never work
  71          */
  72         if (pim_addr_is_any(addr))
  73                 return false;
  74 #endif
  75
  76         if ((!pim_addr_cmp(nexthop->last_lookup, addr)) &&
  77             (nexthop->last_lookup_time > pim->last_route_change_time)) {
  78                 if (PIM_DEBUG_PIM_NHT)
  79                         zlog_debug(
  80                                 "%s: Using last lookup for %pPAs at %lld, %" PRId64
  81                                 " addr %pPAs",
  82                                 __func__, &addr, nexthop->last_lookup_time,
  83                                 pim->last_route_change_time,
  84                                 &nexthop->mrib_nexthop_addr);
  85                 pim->nexthop_lookups_avoided++;
  86                 return true;
  87         } else {
  88                 if (PIM_DEBUG_PIM_NHT)
  89                         zlog_debug(
  90                                 "%s: Looking up: %pPAs, last lookup time: %lld, %" PRId64,
  91                                 __func__, &addr, nexthop->last_lookup_time,
  92                                 pim->last_route_change_time);
  93         }
  94
  95         memset(nexthop_tab, 0,
  96                sizeof(struct pim_zlookup_nexthop) * router->multipath);
  97         num_ifindex =
  98                 zclient_lookup_nexthop(pim, nexthop_tab, router->multipath,
  99                                        addr, PIM_NEXTHOP_LOOKUP_MAX);
 100         if (num_ifindex < 1) {
 101                 if (PIM_DEBUG_PIM_NHT)
 102                         zlog_debug(
 103                                 "%s %s: could not find nexthop ifindex for address %pPAs",
 104                                 __FILE__, __func__, &addr);
 105                 return false;
 106         }
 107
 108         while (!found && (i < num_ifindex)) {
 109                 first_ifindex = nexthop_tab[i].ifindex;
 110
 111                 ifp = if_lookup_by_index(first_ifindex, pim->vrf->vrf_id);
 112                 if (!ifp) {
 113                         if (PIM_DEBUG_ZEBRA)
 114                                 zlog_debug(
 115                                         "%s %s: could not find interface for ifindex %d (address %pPAs)",
 116                                         __FILE__, __func__, first_ifindex,
 117                                         &addr);
 118                         i++;
 119                         continue;
 120                 }
 121
 122                 pim_ifp = ifp->info;
 123                 if (!pim_ifp || !pim_ifp->pim_enable) {
 124                         if (PIM_DEBUG_ZEBRA)
 125                                 zlog_debug(
 126                                         "%s: pim not enabled on input interface %s (ifindex=%d, RPF for source %pPAs)",
 127                                         __func__, ifp->name, first_ifindex,
 128                                         &addr);
 129                         i++;
 130                 } else if (neighbor_needed &&
 131                            !pim_if_connected_to_source(ifp, addr)) {
 132                         nbr = pim_neighbor_find(ifp,
 133                                                 nexthop_tab[i].nexthop_addr);
 134                         if (PIM_DEBUG_PIM_TRACE_DETAIL)
 135                                 zlog_debug("ifp name: %s, pim nbr: %p",
 136                                            ifp->name, nbr);
 137                         if (!nbr && !if_is_loopback(ifp))
 138                                 i++;
 139                         else
 140                                 found = 1;
 141                 } else
 142                         found = 1;
 143         }
 144
 145         if (found) {
 146                 if (PIM_DEBUG_ZEBRA)
 147                         zlog_debug(
 148                                 "%s %s: found nexthop %pPAs for address %pPAs: interface %s ifindex=%d metric=%d pref=%d",
 149                                 __FILE__, __func__,
 150                                 &nexthop_tab[i].nexthop_addr, &addr, ifp->name,
 151                                 first_ifindex, nexthop_tab[i].route_metric,
 152                                 nexthop_tab[i].protocol_distance);
 153
 154                 /* update nexthop data */
 155                 nexthop->interface = ifp;
 156                 nexthop->mrib_nexthop_addr = nexthop_tab[i].nexthop_addr;
 157                 nexthop->mrib_metric_preference =
 158                         nexthop_tab[i].protocol_distance;
 159                 nexthop->mrib_route_metric = nexthop_tab[i].route_metric;
 160                 nexthop->last_lookup = addr;
 161                 nexthop->last_lookup_time = pim_time_monotonic_usec();
 162                 nexthop->nbr = nbr;
 163                 return true;
 164         } else
 165                 return false;
 166 }
 167
 168 static int nexthop_mismatch(const struct pim_nexthop *nh1,
 169                             const struct pim_nexthop *nh2)
 170 {
 171         return (nh1->interface != nh2->interface) ||
 172                (pim_addr_cmp(nh1->mrib_nexthop_addr, nh2->mrib_nexthop_addr)) ||
 173                (nh1->mrib_metric_preference != nh2->mrib_metric_preference) ||
 174                (nh1->mrib_route_metric != nh2->mrib_route_metric);
 175 }
 176
 177 static void pim_rpf_cost_change(struct pim_instance *pim,
 178                 struct pim_upstream *up, uint32_t old_cost)
 179 {
 180         struct pim_rpf *rpf = &up->rpf;
 181         uint32_t new_cost;
 182
 183         new_cost = pim_up_mlag_local_cost(up);
 184         if (PIM_DEBUG_MLAG)
 185                 zlog_debug(
 186                         "%s: Cost_to_rp of upstream-%s changed to:%u, from:%u",
 187                         __func__, up->sg_str, new_cost, old_cost);
 188
 189         if (old_cost == new_cost)
 190                 return;
 191
 192         /* Cost changed, it might Impact MLAG DF election, update */
 193         if (PIM_DEBUG_MLAG)
 194                 zlog_debug(
 195                         "%s: Cost_to_rp of upstream-%s changed to:%u",
 196                         __func__, up->sg_str,
 197                         rpf->source_nexthop.mrib_route_metric);
 198
 199         if (pim_up_mlag_is_local(up))
 200                 pim_mlag_up_local_add(pim, up);
 201 }
 202
 203 enum pim_rpf_result pim_rpf_update(struct pim_instance *pim,
 204                 struct pim_upstream *up, struct pim_rpf *old,
 205                 const char *caller)
 206 {
 207         struct pim_rpf *rpf = &up->rpf;
 208         struct pim_rpf saved;
 209         pim_addr src;
 210         struct prefix grp;
 211         bool neigh_needed = true;
 212         uint32_t saved_mrib_route_metric;
 213
 214         if (PIM_UPSTREAM_FLAG_TEST_STATIC_IIF(up->flags))
 215                 return PIM_RPF_OK;
 216
 217         if (pim_addr_is_any(up->upstream_addr)) {
 218                 zlog_debug("%s(%s): RP is not configured yet for %s",
 219                         __func__, caller, up->sg_str);
 220                 return PIM_RPF_OK;
 221         }
 222
 223         saved.source_nexthop = rpf->source_nexthop;
 224         saved.rpf_addr = rpf->rpf_addr;
 225         saved_mrib_route_metric = pim_up_mlag_local_cost(up);
 226         if (old) {
 227                 old->source_nexthop = saved.source_nexthop;
 228                 old->rpf_addr = saved.rpf_addr;
 229         }
 230
 231         src = up->upstream_addr; // RP or Src address
 232         pim_addr_to_prefix(&grp, up->sg.grp);
 233
 234         if ((pim_addr_is_any(up->sg.src) && I_am_RP(pim, up->sg.grp)) ||
 235             PIM_UPSTREAM_FLAG_TEST_FHR(up->flags))
 236                 neigh_needed = false;
 237         pim_find_or_track_nexthop(pim, up->upstream_addr, up, NULL, NULL);
 238         if (!pim_ecmp_nexthop_lookup(pim, &rpf->source_nexthop, src, &grp,
 239                                      neigh_needed)) {
 240                 /* Route is Deleted in Zebra, reset the stored NH data */
 241                 pim_upstream_rpf_clear(pim, up);
 242                 pim_rpf_cost_change(pim, up, saved_mrib_route_metric);
 243                 return PIM_RPF_FAILURE;
 244         }
 245
 246         rpf->rpf_addr = pim_rpf_find_rpf_addr(up);
 247
 248         if (pim_rpf_addr_is_inaddr_any(rpf) && PIM_DEBUG_ZEBRA) {
 249                 /* RPF'(S,G) not found */
 250                 zlog_debug("%s(%s): RPF'%s not found: won't send join upstream",
 251                            __func__, caller, up->sg_str);
 252                 /* warning only */
 253         }
 254
 255         /* detect change in pim_nexthop */
 256         if (nexthop_mismatch(&rpf->source_nexthop, &saved.source_nexthop)) {
 257
 258                 if (PIM_DEBUG_ZEBRA)
 259                         zlog_debug("%s(%s): (S,G)=%s source nexthop now is: interface=%s address=%pPAs pref=%d metric=%d",
 260                  __func__, caller,
 261                  up->sg_str,
 262                  rpf->source_nexthop.interface ? rpf->source_nexthop.interface->name : "<ifname?>",
 263                  &rpf->source_nexthop.mrib_nexthop_addr,
 264                  rpf->source_nexthop.mrib_metric_preference,
 265                  rpf->source_nexthop.mrib_route_metric);
 266
 267                 pim_upstream_update_join_desired(pim, up);
 268                 pim_upstream_update_could_assert(up);
 269                 pim_upstream_update_my_assert_metric(up);
 270         }
 271
 272         /* detect change in RPF_interface(S) */
 273         if (saved.source_nexthop.interface != rpf->source_nexthop.interface) {
 274
 275                 if (PIM_DEBUG_ZEBRA) {
 276                         zlog_debug("%s(%s): (S,G)=%s RPF_interface(S) changed from %s to %s",
 277                  __func__, caller,
 278                  up->sg_str,
 279                  saved.source_nexthop.interface ? saved.source_nexthop.interface->name : "<oldif?>",
 280                  rpf->source_nexthop.interface ? rpf->source_nexthop.interface->name : "<newif?>");
 281                         /* warning only */
 282                 }
 283
 284                 pim_upstream_rpf_interface_changed(
 285                         up, saved.source_nexthop.interface);
 286         }
 287
 288         /* detect change in RPF'(S,G) */
 289         if (pim_addr_cmp(saved.rpf_addr, rpf->rpf_addr) ||
 290             saved.source_nexthop.interface != rpf->source_nexthop.interface) {
 291                 pim_rpf_cost_change(pim, up, saved_mrib_route_metric);
 292                 return PIM_RPF_CHANGED;
 293         }
 294
 295         if (PIM_DEBUG_MLAG)
 296                 zlog_debug(
 297                         "%s(%s): Cost_to_rp of upstream-%s changed to:%u",
 298                         __func__, caller, up->sg_str,
 299                         rpf->source_nexthop.mrib_route_metric);
 300
 301         pim_rpf_cost_change(pim, up, saved_mrib_route_metric);
 302
 303         return PIM_RPF_OK;
 304 }
 305
 306 /*
 307  * In the case of RP deletion and RP unreachablity,
 308  * uninstall the mroute in the kernel and clear the
 309  * rpf information in the pim upstream and pim channel
 310  * oil data structure.
 311  */
 312 void pim_upstream_rpf_clear(struct pim_instance *pim,
 313                             struct pim_upstream *up)
 314 {
 315         if (up->rpf.source_nexthop.interface) {
 316                 pim_upstream_switch(pim, up, PIM_UPSTREAM_NOTJOINED);
 317                 up->rpf.source_nexthop.interface = NULL;
 318                 up->rpf.source_nexthop.mrib_nexthop_addr = PIMADDR_ANY;
 319                 up->rpf.source_nexthop.mrib_metric_preference =
 320                         router->infinite_assert_metric.metric_preference;
 321                 up->rpf.source_nexthop.mrib_route_metric =
 322                         router->infinite_assert_metric.route_metric;
 323                 up->rpf.rpf_addr = PIMADDR_ANY;
 324                 pim_upstream_mroute_iif_update(up->channel_oil, __func__);
 325         }
 326 }
 327
 328 /*
 329   RFC 4601: 4.1.6.  State Summarization Macros
 330
 331      neighbor RPF'(S,G) {
 332          if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) {
 333               return AssertWinner(S, G, RPF_interface(S) )
 334          } else {
 335               return NBR( RPF_interface(S), MRIB.next_hop( S ) )
 336          }
 337      }
 338
 339   RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data
 340   packets should be coming and to which joins should be sent on the RP
 341   tree and SPT, respectively.
 342 */
 343 static pim_addr pim_rpf_find_rpf_addr(struct pim_upstream *up)
 344 {
 345         struct pim_ifchannel *rpf_ch;
 346         struct pim_neighbor *neigh;
 347         pim_addr rpf_addr;
 348
 349         if (!up->rpf.source_nexthop.interface) {
 350                 zlog_warn("%s: missing RPF interface for upstream (S,G)=%s",
 351                           __func__, up->sg_str);
 352
 353                 return PIMADDR_ANY;
 354         }
 355
 356         rpf_ch = pim_ifchannel_find(up->rpf.source_nexthop.interface, &up->sg);
 357         if (rpf_ch) {
 358                 if (rpf_ch->ifassert_state == PIM_IFASSERT_I_AM_LOSER) {
 359                         return rpf_ch->ifassert_winner;
 360                 }
 361         }
 362
 363         /* return NBR( RPF_interface(S), MRIB.next_hop( S ) ) */
 364
 365         neigh = pim_if_find_neighbor(up->rpf.source_nexthop.interface,
 366                                      up->rpf.source_nexthop.mrib_nexthop_addr);
 367         if (neigh)
 368                 rpf_addr = neigh->source_addr;
 369         else
 370                 rpf_addr = PIMADDR_ANY;
 371
 372         return rpf_addr;
 373 }
 374
 375 int pim_rpf_addr_is_inaddr_any(struct pim_rpf *rpf)
 376 {
 377         return pim_addr_is_any(rpf->rpf_addr);
 378 }
 379
 380 int pim_rpf_is_same(struct pim_rpf *rpf1, struct pim_rpf *rpf2)
 381 {
 382         if (rpf1->source_nexthop.interface == rpf2->source_nexthop.interface)
 383                 return 1;
 384
 385         return 0;
 386 }
 387
 388 unsigned int pim_rpf_hash_key(const void *arg)
 389 {
 390         const struct pim_nexthop_cache *r = arg;
 391
 392 #if PIM_IPV == 4
 393         return jhash_1word(r->rpf.rpf_addr.s_addr, 0);
 394 #else
 395         return jhash2(r->rpf.rpf_addr.s6_addr32,
 396                       array_size(r->rpf.rpf_addr.s6_addr32), 0);
 397 #endif
 398 }
 399
 400 bool pim_rpf_equal(const void *arg1, const void *arg2)
 401 {
 402         const struct pim_nexthop_cache *r1 =
 403                 (const struct pim_nexthop_cache *)arg1;
 404         const struct pim_nexthop_cache *r2 =
 405                 (const struct pim_nexthop_cache *)arg2;
 406
 407         return (!pim_addr_cmp(r1->rpf.rpf_addr, r2->rpf.rpf_addr));
 408 }