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