pimd/pim_macro.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * PIM for Quagga
   4  * Copyright (C) 2008  Everton da Silva Marques
   5  */
   6
   7 #include <zebra.h>
   8
   9 #include "log.h"
  10 #include "prefix.h"
  11 #include "vty.h"
  12 #include "plist.h"
  13
  14 #include "pimd.h"
  15 #include "pim_instance.h"
  16 #include "pim_macro.h"
  17 #include "pim_iface.h"
  18 #include "pim_ifchannel.h"
  19 #include "pim_rp.h"
  20
  21 /*
  22   DownstreamJPState(S,G,I) is the per-interface state machine for
  23   receiving (S,G) Join/Prune messages.
  24
  25   DownstreamJPState(S,G,I) is either Join or Prune-Pending
  26   DownstreamJPState(*,G,I) is either Join or Prune-Pending
  27 */
  28 static int downstream_jpstate_isjoined(const struct pim_ifchannel *ch)
  29 {
  30         switch (ch->ifjoin_state) {
  31         case PIM_IFJOIN_NOINFO:
  32         case PIM_IFJOIN_PRUNE:
  33         case PIM_IFJOIN_PRUNE_TMP:
  34         case PIM_IFJOIN_PRUNE_PENDING_TMP:
  35                 return 0;
  36         case PIM_IFJOIN_JOIN:
  37         case PIM_IFJOIN_PRUNE_PENDING:
  38                 return 1;
  39         }
  40         return 0;
  41 }
  42
  43 /*
  44   The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD
  45   module or other local membership mechanism has determined that local
  46   members on interface I desire to receive traffic sent specifically
  47   by S to G.
  48 */
  49 static int local_receiver_include(const struct pim_ifchannel *ch)
  50 {
  51         /* local_receiver_include(S,G,I) ? */
  52         return ch->local_ifmembership == PIM_IFMEMBERSHIP_INCLUDE;
  53 }
  54
  55 /*
  56   RFC 4601: 4.1.6.  State Summarization Macros
  57
  58    The set "joins(S,G)" is the set of all interfaces on which the
  59    router has received (S,G) Joins:
  60
  61    joins(S,G) =
  62        { all interfaces I such that
  63          DownstreamJPState(S,G,I) is either Join or Prune-Pending }
  64
  65   DownstreamJPState(S,G,I) is either Join or Prune-Pending ?
  66 */
  67 int pim_macro_chisin_joins(const struct pim_ifchannel *ch)
  68 {
  69         return downstream_jpstate_isjoined(ch);
  70 }
  71
  72 /*
  73   RFC 4601: 4.6.5.  Assert State Macros
  74
  75    The set "lost_assert(S,G)" is the set of all interfaces on which the
  76    router has received (S,G) joins but has lost an (S,G) assert.
  77
  78    lost_assert(S,G) =
  79        { all interfaces I such that
  80          lost_assert(S,G,I) == true }
  81
  82      bool lost_assert(S,G,I) {
  83        if ( RPF_interface(S) == I ) {
  84           return false
  85        } else {
  86           return ( AssertWinner(S,G,I) != NULL AND
  87                    AssertWinner(S,G,I) != me  AND
  88                    (AssertWinnerMetric(S,G,I) is better
  89                       than spt_assert_metric(S,I) )
  90        }
  91      }
  92
  93   AssertWinner(S,G,I) is the IP source address of the Assert(S,G)
  94   packet that won an Assert.
  95 */
  96 int pim_macro_ch_lost_assert(const struct pim_ifchannel *ch)
  97 {
  98         struct interface *ifp;
  99         struct pim_interface *pim_ifp;
 100         struct pim_assert_metric spt_assert_metric;
 101
 102         ifp = ch->interface;
 103         if (!ifp) {
 104                 zlog_warn("%s: (S,G)=%s: null interface", __func__, ch->sg_str);
 105                 return 0; /* false */
 106         }
 107
 108         /* RPF_interface(S) == I ? */
 109         if (ch->upstream->rpf.source_nexthop.interface == ifp)
 110                 return 0; /* false */
 111
 112         pim_ifp = ifp->info;
 113         if (!pim_ifp) {
 114                 zlog_warn("%s: (S,G)=%s: multicast not enabled on interface %s",
 115                           __func__, ch->sg_str, ifp->name);
 116                 return 0; /* false */
 117         }
 118
 119         if (pim_addr_is_any(ch->ifassert_winner))
 120                 return 0; /* false */
 121
 122         /* AssertWinner(S,G,I) == me ? */
 123         if (!pim_addr_cmp(ch->ifassert_winner, pim_ifp->primary_address))
 124                 return 0; /* false */
 125
 126         spt_assert_metric = pim_macro_spt_assert_metric(
 127                 &ch->upstream->rpf, pim_ifp->primary_address);
 128
 129         return pim_assert_metric_better(&ch->ifassert_winner_metric,
 130                                         &spt_assert_metric);
 131 }
 132
 133 /*
 134   RFC 4601: 4.1.6.  State Summarization Macros
 135
 136    pim_include(S,G) =
 137        { all interfaces I such that:
 138          ( (I_am_DR( I ) AND lost_assert(S,G,I) == false )
 139            OR AssertWinner(S,G,I) == me )
 140           AND  local_receiver_include(S,G,I) }
 141
 142    AssertWinner(S,G,I) is the IP source address of the Assert(S,G)
 143    packet that won an Assert.
 144 */
 145 int pim_macro_chisin_pim_include(const struct pim_ifchannel *ch)
 146 {
 147         struct pim_interface *pim_ifp = ch->interface->info;
 148         bool mlag_active = false;
 149
 150         if (!pim_ifp) {
 151                 zlog_warn("%s: (S,G)=%s: multicast not enabled on interface %s",
 152                           __func__, ch->sg_str, ch->interface->name);
 153                 return 0; /* false */
 154         }
 155
 156         /* local_receiver_include(S,G,I) ? */
 157         if (!local_receiver_include(ch))
 158                 return 0; /* false */
 159
 160         /* OR AssertWinner(S,G,I) == me ? */
 161         if (!pim_addr_cmp(ch->ifassert_winner, pim_ifp->primary_address))
 162                 return 1; /* true */
 163
 164         /*
 165          * When we have a activeactive interface we need to signal
 166          * that this interface is interesting to the upstream
 167          * decision to JOIN *if* we are syncing over the interface
 168          */
 169         if (pim_ifp->activeactive) {
 170                 struct pim_upstream *up = ch->upstream;
 171
 172                 if (PIM_UPSTREAM_FLAG_TEST_MLAG_INTERFACE(up->flags))
 173                         mlag_active = true;
 174         }
 175
 176         return (
 177                 /* I_am_DR( I ) ? */
 178                 (PIM_I_am_DR(pim_ifp) || mlag_active) &&
 179                 /* lost_assert(S,G,I) == false ? */
 180                 (!pim_macro_ch_lost_assert(ch)));
 181 }
 182
 183 int pim_macro_chisin_joins_or_include(const struct pim_ifchannel *ch)
 184 {
 185         if (pim_macro_chisin_joins(ch))
 186                 return 1; /* true */
 187
 188         return pim_macro_chisin_pim_include(ch);
 189 }
 190
 191 /*
 192   RFC 4601: 4.6.1.  (S,G) Assert Message State Machine
 193
 194   CouldAssert(S,G,I) =
 195   SPTbit(S,G)==TRUE
 196   AND (RPF_interface(S) != I)
 197   AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
 198                  (+) ( pim_include(*,G) (-) pim_exclude(S,G) )
 199                  (-) lost_assert(*,G)
 200                  (+) joins(S,G) (+) pim_include(S,G) ) )
 201
 202   CouldAssert(S,G,I) is true for downstream interfaces that would be in
 203   the inherited_olist(S,G) if (S,G) assert information was not taken
 204   into account.
 205
 206   CouldAssert(S,G,I) may be affected by changes in the following:
 207
 208   pim_ifp->primary_address
 209   pim_ifp->pim_dr_addr
 210   ch->ifassert_winner_metric
 211   ch->ifassert_winner
 212   ch->local_ifmembership
 213   ch->ifjoin_state
 214   ch->upstream->rpf.source_nexthop.mrib_metric_preference
 215   ch->upstream->rpf.source_nexthop.mrib_route_metric
 216   ch->upstream->rpf.source_nexthop.interface
 217 */
 218 int pim_macro_ch_could_assert_eval(const struct pim_ifchannel *ch)
 219 {
 220         struct interface *ifp;
 221
 222         ifp = ch->interface;
 223         if (!ifp) {
 224                 zlog_warn("%s: (S,G)=%s: null interface", __func__, ch->sg_str);
 225                 return 0; /* false */
 226         }
 227
 228         /* SPTbit(S,G) == true */
 229         if (ch->upstream->sptbit == PIM_UPSTREAM_SPTBIT_FALSE)
 230                 return 0; /* false */
 231
 232         /* RPF_interface(S) != I ? */
 233         if (ch->upstream->rpf.source_nexthop.interface == ifp)
 234                 return 0; /* false */
 235
 236         /* I in joins(S,G) (+) pim_include(S,G) ? */
 237         return pim_macro_chisin_joins_or_include(ch);
 238 }
 239
 240 /*
 241   RFC 4601: 4.6.3.  Assert Metrics
 242
 243    spt_assert_metric(S,I) gives the assert metric we use if we're
 244    sending an assert based on active (S,G) forwarding state:
 245
 246     assert_metric
 247     spt_assert_metric(S,I) {
 248       return {0,MRIB.pref(S),MRIB.metric(S),my_ip_address(I)}
 249     }
 250 */
 251 struct pim_assert_metric pim_macro_spt_assert_metric(const struct pim_rpf *rpf,
 252                                                      pim_addr ifaddr)
 253 {
 254         struct pim_assert_metric metric;
 255
 256         metric.rpt_bit_flag = 0;
 257         metric.metric_preference = rpf->source_nexthop.mrib_metric_preference;
 258         metric.route_metric = rpf->source_nexthop.mrib_route_metric;
 259         metric.ip_address = ifaddr;
 260
 261         return metric;
 262 }
 263
 264 /*
 265   RFC 4601: 4.6.3.  Assert Metrics
 266
 267    An assert metric for (S,G) to include in (or compare against) an
 268    Assert message sent on interface I should be computed using the
 269    following pseudocode:
 270
 271   assert_metric  my_assert_metric(S,G,I) {
 272     if( CouldAssert(S,G,I) == true ) {
 273       return spt_assert_metric(S,I)
 274     } else if( CouldAssert(*,G,I) == true ) {
 275       return rpt_assert_metric(G,I)
 276     } else {
 277       return infinite_assert_metric()
 278     }
 279   }
 280 */
 281 struct pim_assert_metric
 282 pim_macro_ch_my_assert_metric_eval(const struct pim_ifchannel *ch)
 283 {
 284         struct pim_interface *pim_ifp;
 285
 286         pim_ifp = ch->interface->info;
 287
 288         if (pim_ifp) {
 289                 if (PIM_IF_FLAG_TEST_COULD_ASSERT(ch->flags)) {
 290                         return pim_macro_spt_assert_metric(
 291                                 &ch->upstream->rpf, pim_ifp->primary_address);
 292                 }
 293         }
 294
 295         return router->infinite_assert_metric;
 296 }
 297
 298 /*
 299   RFC 4601 4.2.  Data Packet Forwarding Rules
 300
 301   Macro:
 302   inherited_olist(S,G) =
 303     inherited_olist(S,G,rpt) (+)
 304     joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
 305 */
 306 static int pim_macro_chisin_inherited_olist(const struct pim_ifchannel *ch)
 307 {
 308         if (pim_macro_ch_lost_assert(ch))
 309                 return 0; /* false */
 310
 311         return pim_macro_chisin_joins_or_include(ch);
 312 }
 313
 314 /*
 315   RFC 4601 4.2.  Data Packet Forwarding Rules
 316   RFC 4601 4.8.2.  PIM-SSM-Only Routers
 317
 318   Additionally, the Packet forwarding rules of Section 4.2 can be
 319   simplified in a PIM-SSM-only router:
 320
 321   iif is the incoming interface of the packet.
 322   oiflist = NULL
 323   if (iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined) {
 324     oiflist = inherited_olist(S,G)
 325   } else if (iif is in inherited_olist(S,G)) {
 326     send Assert(S,G) on iif
 327   }
 328   oiflist = oiflist (-) iif
 329   forward packet on all interfaces in oiflist
 330
 331   Macro:
 332   inherited_olist(S,G) =
 333     joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
 334
 335   Note:
 336   - The following test is performed as response to WRONGVIF kernel
 337     upcall:
 338     if (iif is in inherited_olist(S,G)) {
 339       send Assert(S,G) on iif
 340     }
 341     See pim_mroute.c mroute_msg().
 342 */
 343 int pim_macro_chisin_oiflist(const struct pim_ifchannel *ch)
 344 {
 345         if (ch->upstream->join_state == PIM_UPSTREAM_NOTJOINED) {
 346                 /* oiflist is NULL */
 347                 return 0; /* false */
 348         }
 349
 350         /* oiflist = oiflist (-) iif */
 351         if (ch->interface == ch->upstream->rpf.source_nexthop.interface)
 352                 return 0; /* false */
 353
 354         return pim_macro_chisin_inherited_olist(ch);
 355 }
 356
 357 /*
 358   RFC 4601: 4.6.1.  (S,G) Assert Message State Machine
 359
 360   AssertTrackingDesired(S,G,I) =
 361   (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
 362         (+) ( pim_include(*,G) (-) pim_exclude(S,G) )
 363         (-) lost_assert(*,G)
 364         (+) joins(S,G) ) )
 365      OR (local_receiver_include(S,G,I) == true
 366          AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me)))
 367      OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == true))
 368      OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == true)
 369          AND (SPTbit(S,G) == false))
 370
 371   AssertTrackingDesired(S,G,I) is true on any interface in which an
 372   (S,G) assert might affect our behavior.
 373 */
 374 int pim_macro_assert_tracking_desired_eval(const struct pim_ifchannel *ch)
 375 {
 376         struct pim_interface *pim_ifp;
 377         struct interface *ifp;
 378
 379         ifp = ch->interface;
 380         if (!ifp) {
 381                 zlog_warn("%s: (S,G)=%s: null interface", __func__, ch->sg_str);
 382                 return 0; /* false */
 383         }
 384
 385         pim_ifp = ifp->info;
 386         if (!pim_ifp) {
 387                 zlog_warn("%s: (S,G)=%s: multicast not enabled on interface %s",
 388                           __func__, ch->sg_str, ch->interface->name);
 389                 return 0; /* false */
 390         }
 391
 392         /* I in joins(S,G) ? */
 393         if (pim_macro_chisin_joins(ch))
 394                 return 1; /* true */
 395
 396         /* local_receiver_include(S,G,I) ? */
 397         if (local_receiver_include(ch)) {
 398                 /* I_am_DR(I) ? */
 399                 if (PIM_I_am_DR(pim_ifp))
 400                         return 1; /* true */
 401
 402                 /* AssertWinner(S,G,I) == me ? */
 403                 if (!pim_addr_cmp(ch->ifassert_winner,
 404                                   pim_ifp->primary_address))
 405                         return 1; /* true */
 406         }
 407
 408         /* RPF_interface(S) == I ? */
 409         if (ch->upstream->rpf.source_nexthop.interface == ifp) {
 410                 /* JoinDesired(S,G) ? */
 411                 if (PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(ch->upstream->flags))
 412                         return 1; /* true */
 413         }
 414
 415         return 0; /* false */
 416 }