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*/ 41static 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*/ 52static 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*/ 70int 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*/ 99int 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*/ 159int 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 191int 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*/ 226int 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*/ 263struct 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*/ 293struct 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*/ 316static 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*/ 353int 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*/ 384int 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 438