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_rpf.h"
  31 #include "pim_pim.h"
  32 #include "pim_str.h"
  33 #include "pim_iface.h"
  34 #include "pim_neighbor.h"
  35 #include "pim_zlookup.h"
  36 #include "pim_ifchannel.h"
  37 #include "pim_time.h"
  38 #include "pim_nht.h"
  39 #include "pim_oil.h"
  40 #include "pim_mlag.h"
  41
  42 static pim_addr pim_rpf_find_rpf_addr(struct pim_upstream *up);
  43
  44 void pim_rpf_set_refresh_time(struct pim_instance *pim)
  45 {
  46         pim->last_route_change_time = pim_time_monotonic_usec();
  47         if (PIM_DEBUG_PIM_TRACE)
  48                 zlog_debug("%s: vrf(%s) New last route change time: %" PRId64,
  49                            __func__, pim->vrf->name,
  50                            pim->last_route_change_time);
  51 }
  52
  53 bool pim_nexthop_lookup(struct pim_instance *pim, struct pim_nexthop *nexthop,
  54                         pim_addr addr, int neighbor_needed)
  55 {
  56         struct pim_zlookup_nexthop nexthop_tab[MULTIPATH_NUM];
  57         struct pim_neighbor *nbr = NULL;
  58         int num_ifindex;
  59         struct interface *ifp = NULL;
  60         ifindex_t first_ifindex = 0;
  61         int found = 0;
  62         int i = 0;
  63
  64 #if PIM_IPV == 4
  65         /*
  66          * We should not attempt to lookup a
  67          * 255.255.255.255 address, since
  68          * it will never work
  69          */
  70         if (pim_addr_is_any(addr))
  71                 return false;
  72 #endif
  73
  74         if (!pim_addr_cmp(nexthop->last_lookup, addr)
  75             && (nexthop->last_lookup_time > pim->last_route_change_time)) {
  76                 if (PIM_DEBUG_PIM_NHT) {
  77                         char nexthop_str[PREFIX_STRLEN];
  78                         pim_addr_dump("<nexthop?>", &nexthop->mrib_nexthop_addr,
  79                                       nexthop_str, sizeof(nexthop_str));
  80                         zlog_debug(
  81                                 "%s: Using last lookup for %pPAs at %lld, %" PRId64" addr %s",
  82                                 __func__, &addr, nexthop->last_lookup_time,
  83                                 pim->last_route_change_time, nexthop_str);
  84                 }
  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) * MULTIPATH_NUM);
  97         num_ifindex = zclient_lookup_nexthop(pim, nexthop_tab, MULTIPATH_NUM,
  98                                              addr, PIM_NEXTHOP_LOOKUP_MAX);
  99         if (num_ifindex < 1) {
 100                 zlog_warn(
 101                         "%s %s: could not find nexthop ifindex for address %pPAs",
 102                         __FILE__, __func__, &addr);
 103                 return false;
 104         }
 105
 106         while (!found && (i < num_ifindex)) {
 107                 first_ifindex = nexthop_tab[i].ifindex;
 108
 109                 ifp = if_lookup_by_index(first_ifindex, pim->vrf->vrf_id);
 110                 if (!ifp) {
 111                         if (PIM_DEBUG_ZEBRA)
 112                                 zlog_debug(
 113                                         "%s %s: could not find interface for ifindex %d (address %pPAs)",
 114                                         __FILE__, __func__, first_ifindex,
 115                                         &addr);
 116                         i++;
 117                         continue;
 118                 }
 119
 120                 if (!ifp->info) {
 121                         if (PIM_DEBUG_ZEBRA)
 122                                 zlog_debug(
 123                                         "%s: multicast not enabled on input interface %s (ifindex=%d, RPF for source %pPAs)",
 124                                         __func__, ifp->name, first_ifindex,
 125                                         &addr);
 126                         i++;
 127                 } else if (neighbor_needed
 128                            && !pim_if_connected_to_source(ifp, addr)) {
 129                         nbr = pim_neighbor_find_prefix(
 130                                 ifp, &nexthop_tab[i].nexthop_addr);
 131                         if (PIM_DEBUG_PIM_TRACE_DETAIL)
 132                                 zlog_debug("ifp name: %s, pim nbr: %p",
 133                                            ifp->name, nbr);
 134                         if (!nbr && !if_is_loopback(ifp))
 135                                 i++;
 136                         else
 137                                 found = 1;
 138                 } else
 139                         found = 1;
 140         }
 141
 142         if (found) {
 143                 if (PIM_DEBUG_ZEBRA) {
 144                         char nexthop_str[PREFIX_STRLEN];
 145                         pim_addr_dump("<nexthop?>",
 146                                       &nexthop_tab[i].nexthop_addr, nexthop_str,
 147                                       sizeof(nexthop_str));
 148                         zlog_debug(
 149                                 "%s %s: found nexthop %s for address %pPAs: interface %s ifindex=%d metric=%d pref=%d",
 150                                 __FILE__, __func__, nexthop_str, &addr,
 151                                 ifp->name, first_ifindex,
 152                                 nexthop_tab[i].route_metric,
 153                                 nexthop_tab[i].protocol_distance);
 154                 }
 155                 /* update nexthop data */
 156                 nexthop->interface = ifp;
 157                 nexthop->mrib_nexthop_addr = nexthop_tab[i].nexthop_addr;
 158                 nexthop->mrib_metric_preference =
 159                         nexthop_tab[i].protocol_distance;
 160                 nexthop->mrib_route_metric = nexthop_tab[i].route_metric;
 161                 nexthop->last_lookup = addr;
 162                 nexthop->last_lookup_time = pim_time_monotonic_usec();
 163                 nexthop->nbr = nbr;
 164                 return true;
 165         } else
 166                 return false;
 167 }
 168
 169 static int nexthop_mismatch(const struct pim_nexthop *nh1,
 170                             const struct pim_nexthop *nh2)
 171 {
 172         pim_addr nh_addr1 = pim_addr_from_prefix(&nh1->mrib_nexthop_addr);
 173         pim_addr nh_addr2 = pim_addr_from_prefix(&nh2->mrib_nexthop_addr);
 174
 175         return (nh1->interface != nh2->interface) ||
 176                (pim_addr_cmp(nh_addr1, nh_addr2)) ||
 177                (nh1->mrib_metric_preference != nh2->mrib_metric_preference) ||
 178                (nh1->mrib_route_metric != nh2->mrib_route_metric);
 179 }
 180
 181 static void pim_rpf_cost_change(struct pim_instance *pim,
 182                 struct pim_upstream *up, uint32_t old_cost)
 183 {
 184         struct pim_rpf *rpf = &up->rpf;
 185         uint32_t new_cost;
 186
 187         new_cost = pim_up_mlag_local_cost(up);
 188         if (PIM_DEBUG_MLAG)
 189                 zlog_debug(
 190                         "%s: Cost_to_rp of upstream-%s changed to:%u, from:%u",
 191                         __func__, up->sg_str, new_cost, old_cost);
 192
 193         if (old_cost == new_cost)
 194                 return;
 195
 196         /* Cost changed, it might Impact MLAG DF election, update */
 197         if (PIM_DEBUG_MLAG)
 198                 zlog_debug(
 199                         "%s: Cost_to_rp of upstream-%s changed to:%u",
 200                         __func__, up->sg_str,
 201                         rpf->source_nexthop.mrib_route_metric);
 202
 203         if (pim_up_mlag_is_local(up))
 204                 pim_mlag_up_local_add(pim, up);
 205 }
 206
 207 enum pim_rpf_result pim_rpf_update(struct pim_instance *pim,
 208                 struct pim_upstream *up, struct pim_rpf *old,
 209                 const char *caller)
 210 {
 211         struct pim_rpf *rpf = &up->rpf;
 212         struct pim_rpf saved;
 213         struct prefix nht_p;
 214         struct prefix src, grp;
 215         bool neigh_needed = true;
 216         uint32_t saved_mrib_route_metric;
 217         pim_addr rpf_addr;
 218         pim_addr saved_rpf_addr;
 219
 220         if (PIM_UPSTREAM_FLAG_TEST_STATIC_IIF(up->flags))
 221                 return PIM_RPF_OK;
 222
 223         if (pim_addr_is_any(up->upstream_addr)) {
 224                 zlog_debug("%s(%s): RP is not configured yet for %s",
 225                         __func__, caller, up->sg_str);
 226                 return PIM_RPF_OK;
 227         }
 228
 229         saved.source_nexthop = rpf->source_nexthop;
 230         saved.rpf_addr = rpf->rpf_addr;
 231         saved_mrib_route_metric = pim_up_mlag_local_cost(up);
 232         if (old) {
 233                 old->source_nexthop = saved.source_nexthop;
 234                 old->rpf_addr = saved.rpf_addr;
 235         }
 236
 237         pim_addr_to_prefix(&nht_p, up->upstream_addr);
 238
 239         pim_addr_to_prefix(&src, up->upstream_addr); // RP or Src address
 240         pim_addr_to_prefix(&grp, up->sg.grp);
 241
 242         if ((pim_addr_is_any(up->sg.src) && I_am_RP(pim, up->sg.grp)) ||
 243             PIM_UPSTREAM_FLAG_TEST_FHR(up->flags))
 244                 neigh_needed = false;
 245         pim_find_or_track_nexthop(pim, &nht_p, up, NULL, NULL);
 246         if (!pim_ecmp_nexthop_lookup(pim, &rpf->source_nexthop, &src, &grp,
 247                                 neigh_needed)) {
 248                 /* Route is Deleted in Zebra, reset the stored NH data */
 249                 pim_upstream_rpf_clear(pim, up);
 250                 pim_rpf_cost_change(pim, up, saved_mrib_route_metric);
 251                 return PIM_RPF_FAILURE;
 252         }
 253
 254         rpf_addr = pim_rpf_find_rpf_addr(up);
 255         pim_addr_to_prefix(&rpf->rpf_addr, rpf_addr);
 256
 257         if (pim_rpf_addr_is_inaddr_any(rpf) && PIM_DEBUG_ZEBRA) {
 258                 /* RPF'(S,G) not found */
 259                 zlog_debug("%s(%s): RPF'%s not found: won't send join upstream",
 260                            __func__, caller, up->sg_str);
 261                 /* warning only */
 262         }
 263
 264         /* detect change in pim_nexthop */
 265         if (nexthop_mismatch(&rpf->source_nexthop, &saved.source_nexthop)) {
 266
 267                 if (PIM_DEBUG_ZEBRA) {
 268                         char nhaddr_str[PREFIX_STRLEN];
 269                         pim_addr_dump("<addr?>",
 270                                       &rpf->source_nexthop.mrib_nexthop_addr,
 271                                       nhaddr_str, sizeof(nhaddr_str));
 272                         zlog_debug("%s(%s): (S,G)=%s source nexthop now is: interface=%s address=%s pref=%d metric=%d",
 273                  __func__, caller,
 274                  up->sg_str,
 275                  rpf->source_nexthop.interface ? rpf->source_nexthop.interface->name : "<ifname?>",
 276                  nhaddr_str,
 277                  rpf->source_nexthop.mrib_metric_preference,
 278                  rpf->source_nexthop.mrib_route_metric);
 279                 }
 280
 281                 pim_upstream_update_join_desired(pim, up);
 282                 pim_upstream_update_could_assert(up);
 283                 pim_upstream_update_my_assert_metric(up);
 284         }
 285
 286         /* detect change in RPF_interface(S) */
 287         if (saved.source_nexthop.interface != rpf->source_nexthop.interface) {
 288
 289                 if (PIM_DEBUG_ZEBRA) {
 290                         zlog_debug("%s(%s): (S,G)=%s RPF_interface(S) changed from %s to %s",
 291                  __func__, caller,
 292                  up->sg_str,
 293                  saved.source_nexthop.interface ? saved.source_nexthop.interface->name : "<oldif?>",
 294                  rpf->source_nexthop.interface ? rpf->source_nexthop.interface->name : "<newif?>");
 295                         /* warning only */
 296                 }
 297
 298                 pim_upstream_rpf_interface_changed(
 299                         up, saved.source_nexthop.interface);
 300         }
 301
 302         /* detect change in RPF'(S,G) */
 303
 304         saved_rpf_addr = pim_addr_from_prefix(&saved.rpf_addr);
 305
 306         if (pim_addr_cmp(saved_rpf_addr, rpf_addr) ||
 307             saved.source_nexthop.interface != rpf->source_nexthop.interface) {
 308                 pim_rpf_cost_change(pim, up, saved_mrib_route_metric);
 309                 return PIM_RPF_CHANGED;
 310         }
 311
 312         if (PIM_DEBUG_MLAG)
 313                 zlog_debug(
 314                         "%s(%s): Cost_to_rp of upstream-%s changed to:%u",
 315                         __func__, caller, up->sg_str,
 316                         rpf->source_nexthop.mrib_route_metric);
 317
 318         pim_rpf_cost_change(pim, up, saved_mrib_route_metric);
 319
 320         return PIM_RPF_OK;
 321 }
 322
 323 /*
 324  * In the case of RP deletion and RP unreachablity,
 325  * uninstall the mroute in the kernel and clear the
 326  * rpf information in the pim upstream and pim channel
 327  * oil data structure.
 328  */
 329 void pim_upstream_rpf_clear(struct pim_instance *pim,
 330                             struct pim_upstream *up)
 331 {
 332         if (up->rpf.source_nexthop.interface) {
 333                 pim_upstream_switch(pim, up, PIM_UPSTREAM_NOTJOINED);
 334                 up->rpf.source_nexthop.interface = NULL;
 335                 pim_addr_to_prefix(&up->rpf.source_nexthop.mrib_nexthop_addr,
 336                                    PIMADDR_ANY);
 337                 up->rpf.source_nexthop.mrib_metric_preference =
 338                         router->infinite_assert_metric.metric_preference;
 339                 up->rpf.source_nexthop.mrib_route_metric =
 340                         router->infinite_assert_metric.route_metric;
 341                 pim_addr_to_prefix(&up->rpf.rpf_addr, PIMADDR_ANY);
 342                 pim_upstream_mroute_iif_update(up->channel_oil, __func__);
 343         }
 344 }
 345
 346 /*
 347   RFC 4601: 4.1.6.  State Summarization Macros
 348
 349      neighbor RPF'(S,G) {
 350          if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) {
 351               return AssertWinner(S, G, RPF_interface(S) )
 352          } else {
 353               return NBR( RPF_interface(S), MRIB.next_hop( S ) )
 354          }
 355      }
 356
 357   RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data
 358   packets should be coming and to which joins should be sent on the RP
 359   tree and SPT, respectively.
 360 */
 361 static pim_addr pim_rpf_find_rpf_addr(struct pim_upstream *up)
 362 {
 363         struct pim_ifchannel *rpf_ch;
 364         struct pim_neighbor *neigh;
 365         pim_addr rpf_addr;
 366
 367         if (!up->rpf.source_nexthop.interface) {
 368                 zlog_warn("%s: missing RPF interface for upstream (S,G)=%s",
 369                           __func__, up->sg_str);
 370
 371                 return PIMADDR_ANY;
 372         }
 373
 374         rpf_ch = pim_ifchannel_find(up->rpf.source_nexthop.interface, &up->sg);
 375         if (rpf_ch) {
 376                 if (rpf_ch->ifassert_state == PIM_IFASSERT_I_AM_LOSER) {
 377                         return rpf_ch->ifassert_winner;
 378                 }
 379         }
 380
 381         /* return NBR( RPF_interface(S), MRIB.next_hop( S ) ) */
 382
 383         pim_addr nhaddr;
 384
 385         nhaddr =
 386                 pim_addr_from_prefix(&up->rpf.source_nexthop.mrib_nexthop_addr);
 387         neigh = pim_if_find_neighbor(up->rpf.source_nexthop.interface, nhaddr);
 388         if (neigh)
 389                 rpf_addr = neigh->source_addr;
 390         else
 391                 rpf_addr = PIMADDR_ANY;
 392
 393         return rpf_addr;
 394 }
 395
 396 int pim_rpf_addr_is_inaddr_any(struct pim_rpf *rpf)
 397 {
 398         pim_addr rpf_addr = pim_addr_from_prefix(&rpf->rpf_addr);
 399
 400         switch (rpf->rpf_addr.family) {
 401         case AF_INET:
 402         case AF_INET6:
 403                 return pim_addr_is_any(rpf_addr);
 404         default:
 405                 return 0;
 406         }
 407 }
 408
 409 int pim_rpf_is_same(struct pim_rpf *rpf1, struct pim_rpf *rpf2)
 410 {
 411         if (rpf1->source_nexthop.interface == rpf2->source_nexthop.interface)
 412                 return 1;
 413
 414         return 0;
 415 }
 416
 417 unsigned int pim_rpf_hash_key(const void *arg)
 418 {
 419         const struct pim_nexthop_cache *r = arg;
 420
 421 #if PIM_IPV == 4 || !defined(PIM_V6_TEMP_BREAK)
 422         return jhash_1word(r->rpf.rpf_addr.u.prefix4.s_addr, 0);
 423 #else
 424         return jhash2(r->rpf.rpf_addr.u.prefix6.s6_addr32,
 425                       array_size(r->rpf.rpf_addr.u.prefix6.s6_addr32), 0);
 426 #endif
 427 }
 428
 429 bool pim_rpf_equal(const void *arg1, const void *arg2)
 430 {
 431         const struct pim_nexthop_cache *r1 =
 432                 (const struct pim_nexthop_cache *)arg1;
 433         const struct pim_nexthop_cache *r2 =
 434                 (const struct pim_nexthop_cache *)arg2;
 435
 436         return prefix_same(&r1->rpf.rpf_addr, &r2->rpf.rpf_addr);
 437 }