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