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