]> git.proxmox.com Git - mirror_frr.git/blob - pimd/pim_macro.c
pimd: merge pimd as of 2015-01-19
[mirror_frr.git] / 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