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   $QuaggaId: $Format:%an, %ai, %h$ $
  21 */
  22
  23 #include <zebra.h>
  24
  25 #include "log.h"
  26
  27 #include "pim_macro.h"
  28 #include "pimd.h"
  29 #include "pim_str.h"
  30 #include "pim_iface.h"
  31 #include "pim_ifchannel.h"
  32
  33 #define PIM_IFP_I_am_DR(pim_ifp) ((pim_ifp)->pim_dr_addr.s_addr == (pim_ifp)->primary_address.s_addr)
  34
  35 /*
  36   DownstreamJPState(S,G,I) is the per-interface state machine for
  37   receiving (S,G) Join/Prune messages.
  38
  39   DownstreamJPState(S,G,I) is either Join or Prune-Pending ?
  40 */
  41 static int downstream_jpstate_isjoined(const struct pim_ifchannel *ch)
  42 {
  43   return ch->ifjoin_state != PIM_IFJOIN_NOINFO;
  44 }
  45
  46 /*
  47   The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD
  48   module or other local membership mechanism has determined that local
  49   members on interface I desire to receive traffic sent specifically
  50   by S to G.
  51 */
  52 static int local_receiver_include(const struct pim_ifchannel *ch)
  53 {
  54   /* local_receiver_include(S,G,I) ? */
  55   return ch->local_ifmembership == PIM_IFMEMBERSHIP_INCLUDE;
  56 }
  57
  58 /*
  59   RFC 4601: 4.1.6.  State Summarization Macros
  60
  61    The set "joins(S,G)" is the set of all interfaces on which the
  62    router has received (S,G) Joins:
  63
  64    joins(S,G) =
  65        { all interfaces I such that
  66          DownstreamJPState(S,G,I) is either Join or Prune-Pending }
  67
  68   DownstreamJPState(S,G,I) is either Join or Prune-Pending ?
  69 */
  70 int pim_macro_chisin_joins(const struct pim_ifchannel *ch)
  71 {
  72   return downstream_jpstate_isjoined(ch);
  73 }
  74
  75 /*
  76   RFC 4601: 4.6.5.  Assert State Macros
  77
  78    The set "lost_assert(S,G)" is the set of all interfaces on which the
  79    router has received (S,G) joins but has lost an (S,G) assert.
  80
  81    lost_assert(S,G) =
  82        { all interfaces I such that
  83          lost_assert(S,G,I) == TRUE }
  84
  85      bool lost_assert(S,G,I) {
  86        if ( RPF_interface(S) == I ) {
  87           return FALSE
  88        } else {
  89           return ( AssertWinner(S,G,I) != NULL AND
  90                    AssertWinner(S,G,I) != me  AND
  91                    (AssertWinnerMetric(S,G,I) is better
  92                       than spt_assert_metric(S,I) )
  93        }
  94      }
  95
  96   AssertWinner(S,G,I) is the IP source address of the Assert(S,G)
  97   packet that won an Assert.
  98 */
  99 int pim_macro_ch_lost_assert(const struct pim_ifchannel *ch)
 100 {
 101   struct interface *ifp;
 102   struct pim_interface *pim_ifp;
 103   struct pim_assert_metric spt_assert_metric;
 104
 105   ifp = ch->interface;
 106   if (!ifp) {
 107     char src_str[100];
 108     char grp_str[100];
 109     pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
 110     pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
 111     zlog_warn("%s: (S,G)=(%s,%s): null interface",
 112               __PRETTY_FUNCTION__,
 113               src_str, grp_str);
 114     return 0; /* false */
 115   }
 116
 117   /* RPF_interface(S) == I ? */
 118   if (ch->upstream->rpf.source_nexthop.interface == ifp)
 119     return 0; /* false */
 120
 121   pim_ifp = ifp->info;
 122   if (!pim_ifp) {
 123     char src_str[100];
 124     char grp_str[100];
 125     pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
 126     pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
 127     zlog_warn("%s: (S,G)=(%s,%s): multicast not enabled on interface %s",
 128               __PRETTY_FUNCTION__,
 129               src_str, grp_str, ifp->name);
 130     return 0; /* false */
 131   }
 132
 133   if (PIM_INADDR_IS_ANY(ch->ifassert_winner))
 134     return 0; /* false */
 135
 136   /* AssertWinner(S,G,I) == me ? */
 137   if (ch->ifassert_winner.s_addr == pim_ifp->primary_address.s_addr)
 138     return 0; /* false */
 139
 140   spt_assert_metric = pim_macro_spt_assert_metric(&ch->upstream->rpf,
 141                                                   pim_ifp->primary_address);
 142
 143   return pim_assert_metric_better(&ch->ifassert_winner_metric,
 144                                   &spt_assert_metric);
 145 }
 146
 147 /*
 148   RFC 4601: 4.1.6.  State Summarization Macros
 149
 150    pim_include(S,G) =
 151        { all interfaces I such that:
 152          ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE )
 153            OR AssertWinner(S,G,I) == me )
 154           AND  local_receiver_include(S,G,I) }
 155
 156    AssertWinner(S,G,I) is the IP source address of the Assert(S,G)
 157    packet that won an Assert.
 158 */
 159 int pim_macro_chisin_pim_include(const struct pim_ifchannel *ch)
 160 {
 161   struct pim_interface *pim_ifp = ch->interface->info;
 162
 163   if (!pim_ifp) {
 164     char src_str[100];
 165     char grp_str[100];
 166     pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
 167     pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
 168     zlog_warn("%s: (S,G)=(%s,%s): multicast not enabled on interface %s",
 169               __PRETTY_FUNCTION__,
 170               src_str, grp_str, ch->interface->name);
 171     return 0; /* false */
 172   }
 173
 174   /* local_receiver_include(S,G,I) ? */
 175   if (!local_receiver_include(ch))
 176     return 0; /* false */
 177
 178   /* OR AssertWinner(S,G,I) == me ? */
 179   if (ch->ifassert_winner.s_addr == pim_ifp->primary_address.s_addr)
 180     return 1; /* true */
 181
 182   return (
 183           /* I_am_DR( I ) ? */
 184           PIM_IFP_I_am_DR(pim_ifp)
 185           &&
 186           /* lost_assert(S,G,I) == FALSE ? */
 187           (!pim_macro_ch_lost_assert(ch))
 188           );
 189 }
 190
 191 int pim_macro_chisin_joins_or_include(const struct pim_ifchannel *ch)
 192 {
 193   if (pim_macro_chisin_joins(ch))
 194     return 1; /* true */
 195
 196   return pim_macro_chisin_pim_include(ch);
 197 }
 198
 199 /*
 200   RFC 4601: 4.6.1.  (S,G) Assert Message State Machine
 201
 202   CouldAssert(S,G,I) =
 203   SPTbit(S,G)==TRUE
 204   AND (RPF_interface(S) != I)
 205   AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
 206                  (+) ( pim_include(*,G) (-) pim_exclude(S,G) )
 207                  (-) lost_assert(*,G)
 208                  (+) joins(S,G) (+) pim_include(S,G) ) )
 209
 210   CouldAssert(S,G,I) is true for downstream interfaces that would be in
 211   the inherited_olist(S,G) if (S,G) assert information was not taken
 212   into account.
 213
 214   CouldAssert(S,G,I) may be affected by changes in the following:
 215
 216   pim_ifp->primary_address
 217   pim_ifp->pim_dr_addr
 218   ch->ifassert_winner_metric
 219   ch->ifassert_winner
 220   ch->local_ifmembership
 221   ch->ifjoin_state
 222   ch->upstream->rpf.source_nexthop.mrib_metric_preference
 223   ch->upstream->rpf.source_nexthop.mrib_route_metric
 224   ch->upstream->rpf.source_nexthop.interface
 225 */
 226 int pim_macro_ch_could_assert_eval(const struct pim_ifchannel *ch)
 227 {
 228   struct interface *ifp;
 229
 230   /* SPTbit(S,G) is always true for PIM-SSM-Only Routers */
 231
 232   ifp = ch->interface;
 233   if (!ifp) {
 234     char src_str[100];
 235     char grp_str[100];
 236     pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
 237     pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
 238     zlog_warn("%s: (S,G)=(%s,%s): null interface",
 239               __PRETTY_FUNCTION__,
 240               src_str, grp_str);
 241     return 0; /* false */
 242   }
 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                                                      struct in_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 pim_macro_ch_my_assert_metric_eval(const struct pim_ifchannel *ch)
 294 {
 295   struct pim_interface *pim_ifp;
 296
 297   pim_ifp = ch->interface->info;
 298
 299   if (pim_ifp) {
 300     if (PIM_IF_FLAG_TEST_COULD_ASSERT(ch->flags)) {
 301       return pim_macro_spt_assert_metric(&ch->upstream->rpf, pim_ifp->primary_address);
 302     }
 303   }
 304
 305   return qpim_infinite_assert_metric;
 306 }
 307
 308 /*
 309   RFC 4601 4.2.  Data Packet Forwarding Rules
 310   RFC 4601 4.8.2.  PIM-SSM-Only Routers
 311
 312   Macro:
 313   inherited_olist(S,G) =
 314     joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
 315 */
 316 static int pim_macro_chisin_inherited_olist(const struct pim_ifchannel *ch)
 317 {
 318   if (pim_macro_ch_lost_assert(ch))
 319     return 0; /* false */
 320
 321   return pim_macro_chisin_joins_or_include(ch);
 322 }
 323
 324 /*
 325   RFC 4601 4.2.  Data Packet Forwarding Rules
 326   RFC 4601 4.8.2.  PIM-SSM-Only Routers
 327
 328   Additionally, the Packet forwarding rules of Section 4.2 can be
 329   simplified in a PIM-SSM-only router:
 330
 331   iif is the incoming interface of the packet.
 332   oiflist = NULL
 333   if (iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined) {
 334     oiflist = inherited_olist(S,G)
 335   } else if (iif is in inherited_olist(S,G)) {
 336     send Assert(S,G) on iif
 337   }
 338   oiflist = oiflist (-) iif
 339   forward packet on all interfaces in oiflist
 340
 341   Macro:
 342   inherited_olist(S,G) =
 343     joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
 344
 345   Note:
 346   - The following test is performed as response to WRONGVIF kernel
 347     upcall:
 348     if (iif is in inherited_olist(S,G)) {
 349       send Assert(S,G) on iif
 350     }
 351     See pim_mroute.c mroute_msg().
 352 */
 353 int pim_macro_chisin_oiflist(const struct pim_ifchannel *ch)
 354 {
 355   if (ch->upstream->join_state != PIM_UPSTREAM_JOINED) {
 356     /* oiflist is NULL */
 357     return 0; /* false */
 358   }
 359
 360   /* oiflist = oiflist (-) iif */
 361   if (ch->interface == ch->upstream->rpf.source_nexthop.interface)
 362     return 0; /* false */
 363
 364   return pim_macro_chisin_inherited_olist(ch);
 365 }
 366
 367 /*
 368   RFC 4601: 4.6.1.  (S,G) Assert Message State Machine
 369
 370   AssertTrackingDesired(S,G,I) =
 371   (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
 372         (+) ( pim_include(*,G) (-) pim_exclude(S,G) )
 373         (-) lost_assert(*,G)
 374         (+) joins(S,G) ) )
 375      OR (local_receiver_include(S,G,I) == TRUE
 376          AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me)))
 377      OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == TRUE))
 378      OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == TRUE)
 379          AND (SPTbit(S,G) == FALSE))
 380
 381   AssertTrackingDesired(S,G,I) is true on any interface in which an
 382   (S,G) assert might affect our behavior.
 383 */
 384 int pim_macro_assert_tracking_desired_eval(const struct pim_ifchannel *ch)
 385 {
 386   struct pim_interface *pim_ifp;
 387   struct interface *ifp;
 388
 389   ifp = ch->interface;
 390   if (!ifp) {
 391     char src_str[100];
 392     char grp_str[100];
 393     pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
 394     pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
 395     zlog_warn("%s: (S,G)=(%s,%s): null interface",
 396               __PRETTY_FUNCTION__,
 397               src_str, grp_str);
 398     return 0; /* false */
 399   }
 400
 401   pim_ifp = ifp->info;
 402   if (!pim_ifp) {
 403     char src_str[100];
 404     char grp_str[100];
 405     pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
 406     pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
 407     zlog_warn("%s: (S,G)=(%s,%s): multicast not enabled on interface %s",
 408               __PRETTY_FUNCTION__,
 409               src_str, grp_str, ch->interface->name);
 410     return 0; /* false */
 411   }
 412
 413   /* I in joins(S,G) ? */
 414   if (pim_macro_chisin_joins(ch))
 415     return 1; /* true */
 416
 417   /* local_receiver_include(S,G,I) ? */
 418   if (local_receiver_include(ch)) {
 419     /* I_am_DR(I) ? */
 420     if (PIM_IFP_I_am_DR(pim_ifp))
 421       return 1; /* true */
 422
 423     /* AssertWinner(S,G,I) == me ? */
 424     if (ch->ifassert_winner.s_addr == pim_ifp->primary_address.s_addr)
 425       return 1; /* true */
 426   }
 427
 428   /* RPF_interface(S) == I ? */
 429   if (ch->upstream->rpf.source_nexthop.interface == ifp) {
 430     /* JoinDesired(S,G) ? */
 431     if (PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(ch->upstream->flags))
 432       return 1; /* true */
 433   }
 434
 435   return 0; /* false */
 436 }
 437