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