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