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