summaryrefslogtreecommitdiffstats
path: root/pimd/pim_macro.c
blob: 908026ab1419b2d7f27a2a77937a499d9c546ade (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
/*
 * PIM for Quagga
 * Copyright (C) 2008  Everton da Silva Marques
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; see the file COPYING; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <zebra.h>

#include "log.h"
#include "prefix.h"
#include "vty.h"
#include "plist.h"

#include "pimd.h"
#include "pim_macro.h"
#include "pim_iface.h"
#include "pim_ifchannel.h"
#include "pim_rp.h"

/*
  DownstreamJPState(S,G,I) is the per-interface state machine for
  receiving (S,G) Join/Prune messages.

  DownstreamJPState(S,G,I) is either Join or Prune-Pending
  DownstreamJPState(*,G,I) is either Join or Prune-Pending
*/
static int downstream_jpstate_isjoined(const struct pim_ifchannel *ch)
{
	switch (ch->ifjoin_state) {
	case PIM_IFJOIN_NOINFO:
	case PIM_IFJOIN_PRUNE:
	case PIM_IFJOIN_PRUNE_TMP:
	case PIM_IFJOIN_PRUNE_PENDING_TMP:
		return 0;
		break;
	case PIM_IFJOIN_JOIN:
	case PIM_IFJOIN_PRUNE_PENDING:
		return 1;
		break;
	}
	return 0;
}

/*
  The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD
  module or other local membership mechanism has determined that local
  members on interface I desire to receive traffic sent specifically
  by S to G.
*/
static int local_receiver_include(const struct pim_ifchannel *ch)
{
	/* local_receiver_include(S,G,I) ? */
	return ch->local_ifmembership == PIM_IFMEMBERSHIP_INCLUDE;
}

/*
  RFC 4601: 4.1.6.  State Summarization Macros

   The set "joins(S,G)" is the set of all interfaces on which the
   router has received (S,G) Joins:

   joins(S,G) =
       { all interfaces I such that
	 DownstreamJPState(S,G,I) is either Join or Prune-Pending }

  DownstreamJPState(S,G,I) is either Join or Prune-Pending ?
*/
int pim_macro_chisin_joins(const struct pim_ifchannel *ch)
{
	return downstream_jpstate_isjoined(ch);
}

/*
  RFC 4601: 4.6.5.  Assert State Macros

   The set "lost_assert(S,G)" is the set of all interfaces on which the
   router has received (S,G) joins but has lost an (S,G) assert.

   lost_assert(S,G) =
       { all interfaces I such that
	 lost_assert(S,G,I) == TRUE }

     bool lost_assert(S,G,I) {
       if ( RPF_interface(S) == I ) {
	  return FALSE
       } else {
	  return ( AssertWinner(S,G,I) != NULL AND
		   AssertWinner(S,G,I) != me  AND
		   (AssertWinnerMetric(S,G,I) is better
		      than spt_assert_metric(S,I) )
       }
     }

  AssertWinner(S,G,I) is the IP source address of the Assert(S,G)
  packet that won an Assert.
*/
int pim_macro_ch_lost_assert(const struct pim_ifchannel *ch)
{
	struct interface *ifp;
	struct pim_interface *pim_ifp;
	struct pim_assert_metric spt_assert_metric;

	ifp = ch->interface;
	if (!ifp) {
		zlog_warn("%s: (S,G)=%s: null interface", __PRETTY_FUNCTION__,
			  ch->sg_str);
		return 0; /* false */
	}

	/* RPF_interface(S) == I ? */
	if (ch->upstream->rpf.source_nexthop.interface == ifp)
		return 0; /* false */

	pim_ifp = ifp->info;
	if (!pim_ifp) {
		zlog_warn("%s: (S,G)=%s: multicast not enabled on interface %s",
			  __PRETTY_FUNCTION__, ch->sg_str, ifp->name);
		return 0; /* false */
	}

	if (PIM_INADDR_IS_ANY(ch->ifassert_winner))
		return 0; /* false */

	/* AssertWinner(S,G,I) == me ? */
	if (ch->ifassert_winner.s_addr == pim_ifp->primary_address.s_addr)
		return 0; /* false */

	spt_assert_metric = pim_macro_spt_assert_metric(
		&ch->upstream->rpf, pim_ifp->primary_address);

	return pim_assert_metric_better(&ch->ifassert_winner_metric,
					&spt_assert_metric);
}

/*
  RFC 4601: 4.1.6.  State Summarization Macros

   pim_include(S,G) =
       { all interfaces I such that:
	 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE )
	   OR AssertWinner(S,G,I) == me )
	  AND  local_receiver_include(S,G,I) }

   AssertWinner(S,G,I) is the IP source address of the Assert(S,G)
   packet that won an Assert.
*/
int pim_macro_chisin_pim_include(const struct pim_ifchannel *ch)
{
	struct pim_interface *pim_ifp = ch->interface->info;

	if (!pim_ifp) {
		zlog_warn("%s: (S,G)=%s: multicast not enabled on interface %s",
			  __PRETTY_FUNCTION__, ch->sg_str, ch->interface->name);
		return 0; /* false */
	}

	/* local_receiver_include(S,G,I) ? */
	if (!local_receiver_include(ch))
		return 0; /* false */

	/* OR AssertWinner(S,G,I) == me ? */
	if (ch->ifassert_winner.s_addr == pim_ifp->primary_address.s_addr)
		return 1; /* true */

	return (
		/* I_am_DR( I ) ? */
		PIM_I_am_DR(pim_ifp) &&
		/* lost_assert(S,G,I) == FALSE ? */
		(!pim_macro_ch_lost_assert(ch)));
}

int pim_macro_chisin_joins_or_include(const struct pim_ifchannel *ch)
{
	if (pim_macro_chisin_joins(ch))
		return 1; /* true */

	return pim_macro_chisin_pim_include(ch);
}

/*
  RFC 4601: 4.6.1.  (S,G) Assert Message State Machine

  CouldAssert(S,G,I) =
  SPTbit(S,G)==TRUE
  AND (RPF_interface(S) != I)
  AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
		 (+) ( pim_include(*,G) (-) pim_exclude(S,G) )
		 (-) lost_assert(*,G)
		 (+) joins(S,G) (+) pim_include(S,G) ) )

  CouldAssert(S,G,I) is true for downstream interfaces that would be in
  the inherited_olist(S,G) if (S,G) assert information was not taken
  into account.

  CouldAssert(S,G,I) may be affected by changes in the following:

  pim_ifp->primary_address
  pim_ifp->pim_dr_addr
  ch->ifassert_winner_metric
  ch->ifassert_winner
  ch->local_ifmembership
  ch->ifjoin_state
  ch->upstream->rpf.source_nexthop.mrib_metric_preference
  ch->upstream->rpf.source_nexthop.mrib_route_metric
  ch->upstream->rpf.source_nexthop.interface
*/
int pim_macro_ch_could_assert_eval(const struct pim_ifchannel *ch)
{
	struct interface *ifp;

	ifp = ch->interface;
	if (!ifp) {
		zlog_warn("%s: (S,G)=%s: null interface", __PRETTY_FUNCTION__,
			  ch->sg_str);
		return 0; /* false */
	}

	/* SPTbit(S,G) == TRUE */
	if (ch->upstream->sptbit == PIM_UPSTREAM_SPTBIT_FALSE)
		return 0; /* false */

	/* RPF_interface(S) != I ? */
	if (ch->upstream->rpf.source_nexthop.interface == ifp)
		return 0; /* false */

	/* I in joins(S,G) (+) pim_include(S,G) ? */
	return pim_macro_chisin_joins_or_include(ch);
}

/*
  RFC 4601: 4.6.3.  Assert Metrics

   spt_assert_metric(S,I) gives the assert metric we use if we're
   sending an assert based on active (S,G) forwarding state:

    assert_metric
    spt_assert_metric(S,I) {
      return {0,MRIB.pref(S),MRIB.metric(S),my_ip_address(I)}
    }
*/
struct pim_assert_metric pim_macro_spt_assert_metric(const struct pim_rpf *rpf,
						     struct in_addr ifaddr)
{
	struct pim_assert_metric metric;

	metric.rpt_bit_flag = 0;
	metric.metric_preference = rpf->source_nexthop.mrib_metric_preference;
	metric.route_metric = rpf->source_nexthop.mrib_route_metric;
	metric.ip_address = ifaddr;

	return metric;
}

/*
  RFC 4601: 4.6.3.  Assert Metrics

   An assert metric for (S,G) to include in (or compare against) an
   Assert message sent on interface I should be computed using the
   following pseudocode:

  assert_metric  my_assert_metric(S,G,I) {
    if( CouldAssert(S,G,I) == TRUE ) {
      return spt_assert_metric(S,I)
    } else if( CouldAssert(*,G,I) == TRUE ) {
      return rpt_assert_metric(G,I)
    } else {
      return infinite_assert_metric()
    }
  }
*/
struct pim_assert_metric
pim_macro_ch_my_assert_metric_eval(const struct pim_ifchannel *ch)
{
	struct pim_interface *pim_ifp;

	pim_ifp = ch->interface->info;

	if (pim_ifp) {
		if (PIM_IF_FLAG_TEST_COULD_ASSERT(ch->flags)) {
			return pim_macro_spt_assert_metric(
				&ch->upstream->rpf, pim_ifp->primary_address);
		}
	}

	return router->infinite_assert_metric;
}

/*
  RFC 4601 4.2.  Data Packet Forwarding Rules

  Macro:
  inherited_olist(S,G) =
    inherited_olist(S,G,rpt) (+)
    joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
*/
static int pim_macro_chisin_inherited_olist(const struct pim_ifchannel *ch)
{
	if (pim_macro_ch_lost_assert(ch))
		return 0; /* false */

	return pim_macro_chisin_joins_or_include(ch);
}

/*
  RFC 4601 4.2.  Data Packet Forwarding Rules
  RFC 4601 4.8.2.  PIM-SSM-Only Routers

  Additionally, the Packet forwarding rules of Section 4.2 can be
  simplified in a PIM-SSM-only router:

  iif is the incoming interface of the packet.
  oiflist = NULL
  if (iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined) {
    oiflist = inherited_olist(S,G)
  } else if (iif is in inherited_olist(S,G)) {
    send Assert(S,G) on iif
  }
  oiflist = oiflist (-) iif
  forward packet on all interfaces in oiflist

  Macro:
  inherited_olist(S,G) =
    joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)

  Note:
  - The following test is performed as response to WRONGVIF kernel
    upcall:
    if (iif is in inherited_olist(S,G)) {
      send Assert(S,G) on iif
    }
    See pim_mroute.c mroute_msg().
*/
int pim_macro_chisin_oiflist(const struct pim_ifchannel *ch)
{
	if (ch->upstream->join_state == PIM_UPSTREAM_NOTJOINED) {
		/* oiflist is NULL */
		return 0; /* false */
	}

	/* oiflist = oiflist (-) iif */
	if (ch->interface == ch->upstream->rpf.source_nexthop.interface)
		return 0; /* false */

	return pim_macro_chisin_inherited_olist(ch);
}

/*
  RFC 4601: 4.6.1.  (S,G) Assert Message State Machine

  AssertTrackingDesired(S,G,I) =
  (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
	(+) ( pim_include(*,G) (-) pim_exclude(S,G) )
	(-) lost_assert(*,G)
	(+) joins(S,G) ) )
     OR (local_receiver_include(S,G,I) == TRUE
	 AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me)))
     OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == TRUE))
     OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == TRUE)
	 AND (SPTbit(S,G) == FALSE))

  AssertTrackingDesired(S,G,I) is true on any interface in which an
  (S,G) assert might affect our behavior.
*/
int pim_macro_assert_tracking_desired_eval(const struct pim_ifchannel *ch)
{
	struct pim_interface *pim_ifp;
	struct interface *ifp;

	ifp = ch->interface;
	if (!ifp) {
		zlog_warn("%s: (S,G)=%s: null interface", __PRETTY_FUNCTION__,
			  ch->sg_str);
		return 0; /* false */
	}

	pim_ifp = ifp->info;
	if (!pim_ifp) {
		zlog_warn("%s: (S,G)=%s: multicast not enabled on interface %s",
			  __PRETTY_FUNCTION__, ch->sg_str, ch->interface->name);
		return 0; /* false */
	}

	/* I in joins(S,G) ? */
	if (pim_macro_chisin_joins(ch))
		return 1; /* true */

	/* local_receiver_include(S,G,I) ? */
	if (local_receiver_include(ch)) {
		/* I_am_DR(I) ? */
		if (PIM_I_am_DR(pim_ifp))
			return 1; /* true */

		/* AssertWinner(S,G,I) == me ? */
		if (ch->ifassert_winner.s_addr
		    == pim_ifp->primary_address.s_addr)
			return 1; /* true */
	}

	/* RPF_interface(S) == I ? */
	if (ch->upstream->rpf.source_nexthop.interface == ifp) {
		/* JoinDesired(S,G) ? */
		if (PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(ch->upstream->flags))
			return 1; /* true */
	}

	return 0; /* false */
}