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