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