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