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