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
  25 #include "pim_macro.h"
  26 #include "pimd.h"
  27 #include "pim_str.h"
  28 #include "pim_iface.h"
  29 #include "pim_ifchannel.h"
  30
  31 /*
  32   DownstreamJPState(S,G,I) is the per-interface state machine for
  33   receiving (S,G) Join/Prune messages.
  34
  35   DownstreamJPState(S,G,I) is either Join or Prune-Pending ?
  36 */
  37 static int downstream_jpstate_isjoined(const struct pim_ifchannel *ch)
  38 {
  39   return ch->ifjoin_state != PIM_IFJOIN_NOINFO;
  40 }
  41
  42 /*
  43   The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD
  44   module or other local membership mechanism has determined that local
  45   members on interface I desire to receive traffic sent specifically
  46   by S to G.
  47 */
  48 static int local_receiver_include(const struct pim_ifchannel *ch)
  49 {
  50   /* local_receiver_include(S,G,I) ? */
  51   return ch->local_ifmembership == PIM_IFMEMBERSHIP_INCLUDE;
  52 }
  53
  54 /*
  55   RFC 4601: 4.1.6.  State Summarization Macros
  56
  57    The set "joins(S,G)" is the set of all interfaces on which the
  58    router has received (S,G) Joins:
  59
  60    joins(S,G) =
  61        { all interfaces I such that
  62          DownstreamJPState(S,G,I) is either Join or Prune-Pending }
  63
  64   DownstreamJPState(S,G,I) is either Join or Prune-Pending ?
  65 */
  66 int pim_macro_chisin_joins(const struct pim_ifchannel *ch)
  67 {
  68   return downstream_jpstate_isjoined(ch);
  69 }
  70
  71 /*
  72   RFC 4601: 4.6.5.  Assert State Macros
  73
  74    The set "lost_assert(S,G)" is the set of all interfaces on which the
  75    router has received (S,G) joins but has lost an (S,G) assert.
  76
  77    lost_assert(S,G) =
  78        { all interfaces I such that
  79          lost_assert(S,G,I) == TRUE }
  80
  81      bool lost_assert(S,G,I) {
  82        if ( RPF_interface(S) == I ) {
  83           return FALSE
  84        } else {
  85           return ( AssertWinner(S,G,I) != NULL AND
  86                    AssertWinner(S,G,I) != me  AND
  87                    (AssertWinnerMetric(S,G,I) is better
  88                       than spt_assert_metric(S,I) )
  89        }
  90      }
  91
  92   AssertWinner(S,G,I) is the IP source address of the Assert(S,G)
  93   packet that won an Assert.
  94 */
  95 int pim_macro_ch_lost_assert(const struct pim_ifchannel *ch)
  96 {
  97   struct interface *ifp;
  98   struct pim_interface *pim_ifp;
  99   struct pim_assert_metric spt_assert_metric;
 100
 101   ifp = ch->interface;
 102   if (!ifp) {
 103     char src_str[100];
 104     char grp_str[100];
 105     pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
 106     pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
 107     zlog_warn("%s: (S,G)=(%s,%s): null interface",
 108               __PRETTY_FUNCTION__,
 109               src_str, grp_str);
 110     return 0; /* false */
 111   }
 112
 113   /* RPF_interface(S) == I ? */
 114   if (ch->upstream->rpf.source_nexthop.interface == ifp)
 115     return 0; /* false */
 116
 117   pim_ifp = ifp->info;
 118   if (!pim_ifp) {
 119     char src_str[100];
 120     char grp_str[100];
 121     pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
 122     pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
 123     zlog_warn("%s: (S,G)=(%s,%s): multicast not enabled on interface %s",
 124               __PRETTY_FUNCTION__,
 125               src_str, grp_str, ifp->name);
 126     return 0; /* false */
 127   }
 128
 129   if (PIM_INADDR_IS_ANY(ch->ifassert_winner))
 130     return 0; /* false */
 131
 132   /* AssertWinner(S,G,I) == me ? */
 133   if (ch->ifassert_winner.s_addr == pim_ifp->primary_address.s_addr)
 134     return 0; /* false */
 135
 136   spt_assert_metric = pim_macro_spt_assert_metric(&ch->upstream->rpf,
 137                                                   pim_ifp->primary_address);
 138
 139   return pim_assert_metric_better(&ch->ifassert_winner_metric,
 140                                   &spt_assert_metric);
 141 }
 142
 143 /*
 144   RFC 4601: 4.1.6.  State Summarization Macros
 145
 146    pim_include(S,G) =
 147        { all interfaces I such that:
 148          ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE )
 149            OR AssertWinner(S,G,I) == me )
 150           AND  local_receiver_include(S,G,I) }
 151
 152    AssertWinner(S,G,I) is the IP source address of the Assert(S,G)
 153    packet that won an Assert.
 154 */
 155 int pim_macro_chisin_pim_include(const struct pim_ifchannel *ch)
 156 {
 157   struct pim_interface *pim_ifp = ch->interface->info;
 158
 159   if (!pim_ifp) {
 160     char src_str[100];
 161     char grp_str[100];
 162     pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
 163     pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
 164     zlog_warn("%s: (S,G)=(%s,%s): multicast not enabled on interface %s",
 165               __PRETTY_FUNCTION__,
 166               src_str, grp_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           &&
 182           /* lost_assert(S,G,I) == FALSE ? */
 183           (!pim_macro_ch_lost_assert(ch))
 184           );
 185 }
 186
 187 int pim_macro_chisin_joins_or_include(const struct pim_ifchannel *ch)
 188 {
 189   if (pim_macro_chisin_joins(ch))
 190     return 1; /* true */
 191
 192   return pim_macro_chisin_pim_include(ch);
 193 }
 194
 195 /*
 196   RFC 4601: 4.6.1.  (S,G) Assert Message State Machine
 197
 198   CouldAssert(S,G,I) =
 199   SPTbit(S,G)==TRUE
 200   AND (RPF_interface(S) != I)
 201   AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
 202                  (+) ( pim_include(*,G) (-) pim_exclude(S,G) )
 203                  (-) lost_assert(*,G)
 204                  (+) joins(S,G) (+) pim_include(S,G) ) )
 205
 206   CouldAssert(S,G,I) is true for downstream interfaces that would be in
 207   the inherited_olist(S,G) if (S,G) assert information was not taken
 208   into account.
 209
 210   CouldAssert(S,G,I) may be affected by changes in the following:
 211
 212   pim_ifp->primary_address
 213   pim_ifp->pim_dr_addr
 214   ch->ifassert_winner_metric
 215   ch->ifassert_winner
 216   ch->local_ifmembership
 217   ch->ifjoin_state
 218   ch->upstream->rpf.source_nexthop.mrib_metric_preference
 219   ch->upstream->rpf.source_nexthop.mrib_route_metric
 220   ch->upstream->rpf.source_nexthop.interface
 221 */
 222 int pim_macro_ch_could_assert_eval(const struct pim_ifchannel *ch)
 223 {
 224   struct interface *ifp;
 225
 226   ifp = ch->interface;
 227   if (!ifp) {
 228     char src_str[100];
 229     char grp_str[100];
 230     pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
 231     pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
 232     zlog_warn("%s: (S,G)=(%s,%s): null interface",
 233               __PRETTY_FUNCTION__,
 234               src_str, grp_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_JOINED) {
 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     char src_str[100];
 390     char grp_str[100];
 391     pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
 392     pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
 393     zlog_warn("%s: (S,G)=(%s,%s): null interface",
 394               __PRETTY_FUNCTION__,
 395               src_str, grp_str);
 396     return 0; /* false */
 397   }
 398
 399   pim_ifp = ifp->info;
 400   if (!pim_ifp) {
 401     char src_str[100];
 402     char grp_str[100];
 403     pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
 404     pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
 405     zlog_warn("%s: (S,G)=(%s,%s): multicast not enabled on interface %s",
 406               __PRETTY_FUNCTION__,
 407               src_str, grp_str, ch->interface->name);
 408     return 0; /* false */
 409   }
 410
 411   /* I in joins(S,G) ? */
 412   if (pim_macro_chisin_joins(ch))
 413     return 1; /* true */
 414
 415   /* local_receiver_include(S,G,I) ? */
 416   if (local_receiver_include(ch)) {
 417     /* I_am_DR(I) ? */
 418     if (PIM_I_am_DR(pim_ifp))
 419       return 1; /* true */
 420
 421     /* AssertWinner(S,G,I) == me ? */
 422     if (ch->ifassert_winner.s_addr == pim_ifp->primary_address.s_addr)
 423       return 1; /* true */
 424   }
 425
 426   /* RPF_interface(S) == I ? */
 427   if (ch->upstream->rpf.source_nexthop.interface == ifp) {
 428     /* JoinDesired(S,G) ? */
 429     if (PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(ch->upstream->flags))
 430       return 1; /* true */
 431   }
 432
 433   return 0; /* false */
 434 }
 435