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