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
  16   along with this program; see the file COPYING; if not, write to the
  17   Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
  18   MA 02110-1301 USA
  19 */
  20
  21 #include <zebra.h>
  22
  23 #include "if.h"
  24
  25 #include "log.h"
  26 #include "prefix.h"
  27 #include "memory.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_zlookup.h"
  35 #include "pim_ifchannel.h"
  36 #include "pim_time.h"
  37 #include "pim_nht.h"
  38
  39 static long long last_route_change_time = -1;
  40 long long nexthop_lookups_avoided = 0;
  41
  42 static struct in_addr pim_rpf_find_rpf_addr (struct pim_upstream *up);
  43
  44 void
  45 pim_rpf_set_refresh_time (void)
  46 {
  47   last_route_change_time = pim_time_monotonic_usec();
  48   if (PIM_DEBUG_TRACE)
  49     zlog_debug ("%s: New last route change time: %lld",
  50                 __PRETTY_FUNCTION__, last_route_change_time);
  51 }
  52
  53 int pim_nexthop_lookup(struct pim_nexthop *nexthop, struct in_addr addr, int neighbor_needed)
  54 {
  55   struct pim_zlookup_nexthop nexthop_tab[MULTIPATH_NUM];
  56   struct pim_neighbor *nbr = NULL;
  57   int num_ifindex;
  58   struct interface *ifp = NULL;
  59   ifindex_t first_ifindex = 0;
  60   int found = 0;
  61   int i = 0;
  62
  63   if ((nexthop->last_lookup.s_addr == addr.s_addr) &&
  64       (nexthop->last_lookup_time > last_route_change_time))
  65     {
  66       if (PIM_DEBUG_TRACE)
  67         {
  68           char addr_str[INET_ADDRSTRLEN];
  69           pim_inet4_dump("<addr?>", addr, addr_str, sizeof(addr_str));
  70           char nexthop_str[PREFIX_STRLEN];
  71           pim_addr_dump("<nexthop?>", &nexthop->mrib_nexthop_addr,
  72                             nexthop_str, sizeof(nexthop_str));
  73           zlog_debug ("%s: Using last lookup for %s at %lld, %lld addr%s",
  74                       __PRETTY_FUNCTION__,
  75                       addr_str,
  76                       nexthop->last_lookup_time,
  77                       last_route_change_time, nexthop_str);
  78         }
  79       nexthop_lookups_avoided++;
  80       return 0;
  81     }
  82   else
  83     {
  84       if (PIM_DEBUG_TRACE)
  85         {
  86           char addr_str[INET_ADDRSTRLEN];
  87           pim_inet4_dump("<addr?>", addr, addr_str, sizeof(addr_str));
  88           zlog_debug ("%s: Looking up: %s, last lookup time: %lld, %lld",
  89                       __PRETTY_FUNCTION__,
  90                       addr_str,
  91                       nexthop->last_lookup_time,
  92                       last_route_change_time);
  93         }
  94     }
  95
  96   memset (nexthop_tab, 0, sizeof (struct pim_zlookup_nexthop) * MULTIPATH_NUM);
  97   num_ifindex = zclient_lookup_nexthop(nexthop_tab,
  98                                        MULTIPATH_NUM,
  99                                        addr, PIM_NEXTHOP_LOOKUP_MAX);
 100   if (num_ifindex < 1) {
 101     char addr_str[INET_ADDRSTRLEN];
 102     pim_inet4_dump("<addr?>", addr, addr_str, sizeof(addr_str));
 103     zlog_warn("%s %s: could not find nexthop ifindex for address %s",
 104               __FILE__, __PRETTY_FUNCTION__,
 105               addr_str);
 106     return -1;
 107   }
 108
 109   while (!found && (i < num_ifindex))
 110     {
 111       first_ifindex = nexthop_tab[i].ifindex;
 112
 113       ifp = if_lookup_by_index(first_ifindex, VRF_DEFAULT);
 114       if (!ifp)
 115         {
 116           if (PIM_DEBUG_ZEBRA)
 117             {
 118               char addr_str[INET_ADDRSTRLEN];
 119               pim_inet4_dump("<addr?>", addr, addr_str, sizeof(addr_str));
 120               zlog_debug("%s %s: could not find interface for ifindex %d (address %s)",
 121                          __FILE__, __PRETTY_FUNCTION__,
 122                          first_ifindex, addr_str);
 123             }
 124           i++;
 125           continue;
 126         }
 127
 128       if (!ifp->info)
 129         {
 130           if (PIM_DEBUG_ZEBRA)
 131             {
 132               char addr_str[INET_ADDRSTRLEN];
 133               pim_inet4_dump("<addr?>", addr, addr_str, sizeof(addr_str));
 134               zlog_debug("%s: multicast not enabled on input interface %s (ifindex=%d, RPF for source %s)",
 135                          __PRETTY_FUNCTION__,
 136                          ifp->name, first_ifindex, addr_str);
 137             }
 138           i++;
 139         }
 140       else if (neighbor_needed && !pim_if_connected_to_source (ifp, addr))
 141         {
 142           nbr = pim_neighbor_find (ifp, nexthop_tab[i].nexthop_addr.u.prefix4);
 143           if (PIM_DEBUG_PIM_TRACE_DETAIL)
 144             zlog_debug ("ifp name: %s, pim nbr: %p", ifp->name, nbr);
 145           if (!nbr && !if_is_loopback (ifp))
 146             i++;
 147           else
 148             found = 1;
 149         }
 150       else
 151         found = 1;
 152     }
 153
 154   if (found)
 155     {
 156       if (PIM_DEBUG_ZEBRA) {
 157         char nexthop_str[PREFIX_STRLEN];
 158         char addr_str[INET_ADDRSTRLEN];
 159         pim_addr_dump("<nexthop?>", &nexthop_tab[i].nexthop_addr, nexthop_str, sizeof(nexthop_str));
 160         pim_inet4_dump("<addr?>", addr, addr_str, sizeof(addr_str));
 161         zlog_debug("%s %s: found nexthop %s for address %s: interface %s ifindex=%d metric=%d pref=%d",
 162                    __FILE__, __PRETTY_FUNCTION__,
 163                    nexthop_str, addr_str,
 164                    ifp->name, first_ifindex,
 165                    nexthop_tab[i].route_metric,
 166                    nexthop_tab[i].protocol_distance);
 167       }
 168       /* update nextop data */
 169       nexthop->interface                = ifp;
 170       nexthop->mrib_nexthop_addr        = nexthop_tab[i].nexthop_addr;
 171       nexthop->mrib_metric_preference   = nexthop_tab[i].protocol_distance;
 172       nexthop->mrib_route_metric        = nexthop_tab[i].route_metric;
 173       nexthop->last_lookup              = addr;
 174       nexthop->last_lookup_time         = pim_time_monotonic_usec();
 175       nexthop->nbr                      = nbr;
 176       return 0;
 177     }
 178   else
 179     return -1;
 180 }
 181
 182 static int nexthop_mismatch(const struct pim_nexthop *nh1,
 183                             const struct pim_nexthop *nh2)
 184 {
 185   return (nh1->interface != nh2->interface)                          ||
 186     (nh1->mrib_nexthop_addr.u.prefix4.s_addr != nh2->mrib_nexthop_addr.u.prefix4.s_addr) ||
 187     (nh1->mrib_metric_preference != nh2->mrib_metric_preference)     ||
 188     (nh1->mrib_route_metric != nh2->mrib_route_metric);
 189 }
 190
 191 enum pim_rpf_result pim_rpf_update(struct pim_upstream *up, struct pim_rpf *old, uint8_t is_new)
 192 {
 193   struct pim_rpf     *rpf = &up->rpf;
 194   struct pim_rpf     saved;
 195   struct prefix     nht_p;
 196   struct pim_nexthop_cache pnc;
 197   int ret = 0;
 198   struct prefix src, grp;
 199
 200   saved.source_nexthop = rpf->source_nexthop;
 201   saved.rpf_addr = rpf->rpf_addr;
 202
 203   if (is_new && PIM_DEBUG_ZEBRA)
 204     {
 205       char source_str[INET_ADDRSTRLEN];
 206       pim_inet4_dump ("<source?>", up->upstream_addr, source_str,
 207                       sizeof (source_str));
 208       zlog_debug ("%s: NHT Register upstream %s addr %s with Zebra.",
 209                   __PRETTY_FUNCTION__, up->sg_str, source_str);
 210     }
 211   /* Register addr with Zebra NHT */
 212   nht_p.family = AF_INET;
 213   nht_p.prefixlen = IPV4_MAX_BITLEN;
 214   nht_p.u.prefix4.s_addr = up->upstream_addr.s_addr;
 215
 216   src.family = AF_INET;
 217   src.prefixlen = IPV4_MAX_BITLEN;
 218   src.u.prefix4 = up->upstream_addr;    //RP or Src address
 219   grp.family = AF_INET;
 220   grp.prefixlen = IPV4_MAX_BITLEN;
 221   grp.u.prefix4 = up->sg.grp;
 222   memset (&pnc, 0, sizeof (struct pim_nexthop_cache));
 223   if ((ret = pim_find_or_track_nexthop (&nht_p, up, NULL, &pnc)) == 1)
 224     {
 225       if (pnc.nexthop_num)
 226         {
 227           //Compute PIM RPF using Cached nexthop
 228           pim_ecmp_nexthop_search (&pnc, &up->rpf.source_nexthop,
 229                                    &src, &grp,
 230                                    !PIM_UPSTREAM_FLAG_TEST_FHR (up->flags) &&
 231                                    !PIM_UPSTREAM_FLAG_TEST_SRC_IGMP (up->
 232                                                                      flags));
 233         }
 234     }
 235   else
 236     {
 237       if (pim_ecmp_nexthop_lookup (&rpf->source_nexthop,
 238                                    up->upstream_addr, &src, &grp,
 239                                    !PIM_UPSTREAM_FLAG_TEST_FHR (up->flags) &&
 240                                    !PIM_UPSTREAM_FLAG_TEST_SRC_IGMP (up->
 241                                                                      flags)))
 242         {
 243           return PIM_RPF_FAILURE;
 244         }
 245    }
 246
 247   rpf->rpf_addr.family = AF_INET;
 248   rpf->rpf_addr.u.prefix4 = pim_rpf_find_rpf_addr(up);
 249   if (pim_rpf_addr_is_inaddr_any(rpf) && PIM_DEBUG_ZEBRA) {
 250     /* RPF'(S,G) not found */
 251     zlog_debug("%s %s: RPF'%s not found: won't send join upstream",
 252                __FILE__, __PRETTY_FUNCTION__,
 253                up->sg_str);
 254     /* warning only */
 255   }
 256
 257   /* detect change in pim_nexthop */
 258   if (nexthop_mismatch(&rpf->source_nexthop, &saved.source_nexthop)) {
 259
 260     if (PIM_DEBUG_ZEBRA) {
 261       char nhaddr_str[PREFIX_STRLEN];
 262       pim_addr_dump("<addr?>", &rpf->source_nexthop.mrib_nexthop_addr, nhaddr_str, sizeof(nhaddr_str));
 263       zlog_debug("%s %s: (S,G)=%s source nexthop now is: interface=%s address=%s pref=%d metric=%d",
 264                  __FILE__, __PRETTY_FUNCTION__,
 265                  up->sg_str,
 266                  rpf->source_nexthop.interface ? rpf->source_nexthop.interface->name : "<ifname?>",
 267                  nhaddr_str,
 268                  rpf->source_nexthop.mrib_metric_preference,
 269                  rpf->source_nexthop.mrib_route_metric);
 270     }
 271
 272     pim_upstream_update_join_desired(up);
 273     pim_upstream_update_could_assert(up);
 274     pim_upstream_update_my_assert_metric(up);
 275   }
 276
 277   /* detect change in RPF_interface(S) */
 278   if (saved.source_nexthop.interface != rpf->source_nexthop.interface) {
 279
 280     if (PIM_DEBUG_ZEBRA) {
 281       zlog_debug("%s %s: (S,G)=%s RPF_interface(S) changed from %s to %s",
 282                  __FILE__, __PRETTY_FUNCTION__,
 283                  up->sg_str,
 284                  saved.source_nexthop.interface ? saved.source_nexthop.interface->name : "<oldif?>",
 285                  rpf->source_nexthop.interface ? rpf->source_nexthop.interface->name : "<newif?>");
 286       /* warning only */
 287     }
 288
 289     pim_upstream_rpf_interface_changed(up, saved.source_nexthop.interface);
 290   }
 291
 292   /* detect change in RPF'(S,G) */
 293   if (saved.rpf_addr.u.prefix4.s_addr != rpf->rpf_addr.u.prefix4.s_addr ||
 294       saved.source_nexthop.interface != rpf->source_nexthop.interface)
 295     {
 296
 297     /* return old rpf to caller ? */
 298     if (old)
 299       {
 300         old->source_nexthop = saved.source_nexthop;
 301         old->rpf_addr = saved.rpf_addr;
 302       }
 303     return PIM_RPF_CHANGED;
 304   }
 305
 306   return PIM_RPF_OK;
 307 }
 308
 309 /*
 310   RFC 4601: 4.1.6.  State Summarization Macros
 311
 312      neighbor RPF'(S,G) {
 313          if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) {
 314               return AssertWinner(S, G, RPF_interface(S) )
 315          } else {
 316               return NBR( RPF_interface(S), MRIB.next_hop( S ) )
 317          }
 318      }
 319
 320   RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data
 321   packets should be coming and to which joins should be sent on the RP
 322   tree and SPT, respectively.
 323 */
 324 static struct in_addr pim_rpf_find_rpf_addr(struct pim_upstream *up)
 325 {
 326   struct pim_ifchannel *rpf_ch;
 327   struct pim_neighbor *neigh;
 328   struct in_addr rpf_addr;
 329
 330   if (!up->rpf.source_nexthop.interface) {
 331     zlog_warn("%s: missing RPF interface for upstream (S,G)=%s",
 332               __PRETTY_FUNCTION__,
 333               up->sg_str);
 334
 335     rpf_addr.s_addr = PIM_NET_INADDR_ANY;
 336     return rpf_addr;
 337   }
 338
 339   rpf_ch = pim_ifchannel_find(up->rpf.source_nexthop.interface,
 340                               &up->sg);
 341   if (rpf_ch) {
 342     if (rpf_ch->ifassert_state == PIM_IFASSERT_I_AM_LOSER) {
 343       return rpf_ch->ifassert_winner;
 344     }
 345   }
 346
 347   /* return NBR( RPF_interface(S), MRIB.next_hop( S ) ) */
 348
 349   neigh = pim_if_find_neighbor(up->rpf.source_nexthop.interface,
 350                                up->rpf.source_nexthop.mrib_nexthop_addr.u.prefix4);
 351   if (neigh)
 352     rpf_addr = neigh->source_addr;
 353   else
 354     rpf_addr.s_addr = PIM_NET_INADDR_ANY;
 355
 356   return rpf_addr;
 357 }
 358
 359 int
 360 pim_rpf_addr_is_inaddr_none (struct pim_rpf *rpf)
 361 {
 362   switch (rpf->rpf_addr.family)
 363     {
 364     case AF_INET:
 365       return rpf->rpf_addr.u.prefix4.s_addr == INADDR_NONE;
 366       break;
 367     case AF_INET6:
 368       zlog_warn ("%s: v6 Unimplmeneted", __PRETTY_FUNCTION__);
 369       return 1;
 370       break;
 371     default:
 372       return 0;
 373       break;
 374     }
 375
 376   return 0;
 377 }
 378
 379 int
 380 pim_rpf_addr_is_inaddr_any (struct pim_rpf *rpf)
 381 {
 382   switch (rpf->rpf_addr.family)
 383     {
 384     case AF_INET:
 385       return rpf->rpf_addr.u.prefix4.s_addr == INADDR_ANY;
 386       break;
 387     case AF_INET6:
 388       zlog_warn ("%s: v6 Unimplmented", __PRETTY_FUNCTION__);
 389       return 1;
 390       break;
 391     default:
 392       return 0;
 393       break;
 394     }
 395
 396   return 0;
 397 }
 398
 399 int
 400 pim_rpf_is_same (struct pim_rpf *rpf1, struct pim_rpf *rpf2)
 401 {
 402   if (rpf1->source_nexthop.interface == rpf2->source_nexthop.interface)
 403     return 1;
 404
 405   return 0;
 406 }