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 "zebra/rib.h"
26
27#include "log.h"
28#include "zclient.h"
29#include "memory.h"
30#include "thread.h"
31#include "linklist.h"
32
33#include "pimd.h"
34#include "pim_pim.h"
35#include "pim_str.h"
36#include "pim_time.h"
37#include "pim_iface.h"
38#include "pim_join.h"
39#include "pim_zlookup.h"
40#include "pim_upstream.h"
41#include "pim_ifchannel.h"
42#include "pim_neighbor.h"
43#include "pim_rpf.h"
44#include "pim_zebra.h"
45#include "pim_oil.h"
46#include "pim_macro.h"
47
48static void join_timer_start(struct pim_upstream *up);
49static void pim_upstream_update_assert_tracking_desired(struct pim_upstream *up);
50
51void pim_upstream_free(struct pim_upstream *up)
52{
53  XFREE(MTYPE_PIM_UPSTREAM, up);
54}
55
56static void upstream_channel_oil_detach(struct pim_upstream *up)
57{
58  if (up->channel_oil) {
59    pim_channel_oil_del(up->channel_oil);
60    up->channel_oil = 0;
61  }
62}
63
64void pim_upstream_delete(struct pim_upstream *up)
65{
66  THREAD_OFF(up->t_join_timer);
67
68  upstream_channel_oil_detach(up);
69
70  /*
71    notice that listnode_delete() can't be moved
72    into pim_upstream_free() because the later is
73    called by list_delete_all_node()
74  */
75  listnode_delete(qpim_upstream_list, up);
76
77  pim_upstream_free(up);
78}
79
80static void send_join(struct pim_upstream *up)
81{
82  zassert(up->join_state == PIM_UPSTREAM_JOINED);
83
84
85  if (PIM_DEBUG_PIM_TRACE) {
86    if (PIM_INADDR_IS_ANY(up->rpf.rpf_addr)) {
87      char src_str[100];
88      char grp_str[100];
89      char rpf_str[100];
90      pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str));
91      pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str));
92      pim_inet4_dump("<rpf?>", up->rpf.rpf_addr, rpf_str, sizeof(rpf_str));
93      zlog_warn("%s: can't send join upstream: RPF'(%s,%s)=%s",
94		__PRETTY_FUNCTION__,
95		src_str, grp_str, rpf_str);
96      /* warning only */
97    }
98  }
99
100  /* send Join(S,G) to the current upstream neighbor */
101  pim_joinprune_send(up->rpf.source_nexthop.interface,
102  		     up->rpf.rpf_addr,
103		     up->source_addr,
104		     up->group_addr,
105		     1 /* join */);
106}
107
108static int on_join_timer(struct thread *t)
109{
110  struct pim_upstream *up;
111
112  zassert(t);
113  up = THREAD_ARG(t);
114  zassert(up);
115
116  send_join(up);
117
118  up->t_join_timer = 0;
119  join_timer_start(up);
120
121  return 0;
122}
123
124static void join_timer_start(struct pim_upstream *up)
125{
126  if (PIM_DEBUG_PIM_EVENTS) {
127    char src_str[100];
128    char grp_str[100];
129    pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str));
130    pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str));
131    zlog_debug("%s: starting %d sec timer for upstream (S,G)=(%s,%s)",
132	       __PRETTY_FUNCTION__,
133	       qpim_t_periodic,
134	       src_str, grp_str);
135  }
136
137  zassert(!up->t_join_timer);
138
139  THREAD_TIMER_ON(master, up->t_join_timer,
140		  on_join_timer,
141		  up, qpim_t_periodic);
142}
143
144void pim_upstream_join_timer_restart(struct pim_upstream *up)
145{
146  THREAD_OFF(up->t_join_timer);
147  join_timer_start(up);
148}
149
150static void pim_upstream_join_timer_restart_msec(struct pim_upstream *up,
151						 int interval_msec)
152{
153  if (PIM_DEBUG_PIM_EVENTS) {
154    char src_str[100];
155    char grp_str[100];
156    pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str));
157    pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str));
158    zlog_debug("%s: restarting %d msec timer for upstream (S,G)=(%s,%s)",
159	       __PRETTY_FUNCTION__,
160	       interval_msec,
161	       src_str, grp_str);
162  }
163
164  THREAD_OFF(up->t_join_timer);
165  THREAD_TIMER_MSEC_ON(master, up->t_join_timer,
166		       on_join_timer,
167		       up, interval_msec);
168}
169
170void pim_upstream_join_suppress(struct pim_upstream *up,
171				struct in_addr rpf_addr,
172				int holdtime)
173{
174  long t_joinsuppress_msec;
175  long join_timer_remain_msec;
176
177  t_joinsuppress_msec = MIN(pim_if_t_suppressed_msec(up->rpf.source_nexthop.interface),
178			    1000 * holdtime);
179
180  join_timer_remain_msec = pim_time_timer_remain_msec(up->t_join_timer);
181
182  if (PIM_DEBUG_PIM_TRACE) {
183    char src_str[100];
184    char grp_str[100];
185    char rpf_str[100];
186    pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str));
187    pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str));
188    pim_inet4_dump("<rpf?>", rpf_addr, rpf_str, sizeof(rpf_str));
189    zlog_debug("%s %s: detected Join(%s,%s) to RPF'(S,G)=%s: join_timer=%ld msec t_joinsuppress=%ld msec",
190	       __FILE__, __PRETTY_FUNCTION__,
191	       src_str, grp_str,
192	       rpf_str,
193	       join_timer_remain_msec, t_joinsuppress_msec);
194  }
195
196  if (join_timer_remain_msec < t_joinsuppress_msec) {
197    if (PIM_DEBUG_PIM_TRACE) {
198      char src_str[100];
199      char grp_str[100];
200      pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str));
201      pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str));
202      zlog_debug("%s %s: suppressing Join(S,G)=(%s,%s) for %ld msec",
203		 __FILE__, __PRETTY_FUNCTION__,
204		 src_str, grp_str, t_joinsuppress_msec);
205    }
206
207    pim_upstream_join_timer_restart_msec(up, t_joinsuppress_msec);
208  }
209}
210
211void pim_upstream_join_timer_decrease_to_t_override(const char *debug_label,
212						    struct pim_upstream *up,
213						    struct in_addr rpf_addr)
214{
215  long join_timer_remain_msec;
216  int t_override_msec;
217
218  join_timer_remain_msec = pim_time_timer_remain_msec(up->t_join_timer);
219  t_override_msec = pim_if_t_override_msec(up->rpf.source_nexthop.interface);
220
221  if (PIM_DEBUG_PIM_TRACE) {
222    char src_str[100];
223    char grp_str[100];
224    char rpf_str[100];
225    pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str));
226    pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str));
227    pim_inet4_dump("<rpf?>", rpf_addr, rpf_str, sizeof(rpf_str));
228    zlog_debug("%s: to RPF'(%s,%s)=%s: join_timer=%ld msec t_override=%d msec",
229	       debug_label,
230	       src_str, grp_str, rpf_str,
231	       join_timer_remain_msec, t_override_msec);
232  }
233
234  if (join_timer_remain_msec > t_override_msec) {
235    if (PIM_DEBUG_PIM_TRACE) {
236      char src_str[100];
237      char grp_str[100];
238      pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str));
239      pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str));
240      zlog_debug("%s: decreasing (S,G)=(%s,%s) join timer to t_override=%d msec",
241		 debug_label,
242		 src_str, grp_str,
243		 t_override_msec);
244    }
245
246    pim_upstream_join_timer_restart_msec(up, t_override_msec);
247  }
248}
249
250static void forward_on(struct pim_upstream *up)
251{
252  struct listnode      *ifnode;
253  struct listnode      *ifnextnode;
254  struct listnode      *chnode;
255  struct listnode      *chnextnode;
256  struct interface     *ifp;
257  struct pim_interface *pim_ifp;
258  struct pim_ifchannel *ch;
259
260  /* scan all interfaces */
261  for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) {
262    pim_ifp = ifp->info;
263    if (!pim_ifp)
264      continue;
265
266    /* scan per-interface (S,G) state */
267    for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) {
268
269      if (ch->upstream != up)
270	continue;
271
272      if (pim_macro_chisin_oiflist(ch))
273	pim_forward_start(ch);
274
275    } /* scan iface channel list */
276  } /* scan iflist */
277}
278
279static void forward_off(struct pim_upstream *up)
280{
281  struct listnode      *ifnode;
282  struct listnode      *ifnextnode;
283  struct listnode      *chnode;
284  struct listnode      *chnextnode;
285  struct interface     *ifp;
286  struct pim_interface *pim_ifp;
287  struct pim_ifchannel *ch;
288
289  /* scan all interfaces */
290  for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) {
291    pim_ifp = ifp->info;
292    if (!pim_ifp)
293      continue;
294
295    /* scan per-interface (S,G) state */
296    for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) {
297
298      if (ch->upstream != up)
299	continue;
300
301      pim_forward_stop(ch);
302
303    } /* scan iface channel list */
304  } /* scan iflist */
305}
306
307static void pim_upstream_switch(struct pim_upstream *up,
308				enum pim_upstream_state new_state)
309{
310  enum pim_upstream_state old_state = up->join_state;
311
312  zassert(old_state != new_state);
313
314  up->join_state       = new_state;
315  up->state_transition = pim_time_monotonic_sec();
316
317  if (PIM_DEBUG_PIM_EVENTS) {
318    char src_str[100];
319    char grp_str[100];
320    pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str));
321    pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str));
322    zlog_debug("%s: PIM_UPSTREAM_%s: (S,G)=(%s,%s)",
323	       __PRETTY_FUNCTION__,
324	       ((new_state == PIM_UPSTREAM_JOINED) ? "JOINED" : "NOTJOINED"),
325	       src_str, grp_str);
326  }
327
328  pim_upstream_update_assert_tracking_desired(up);
329
330  if (new_state == PIM_UPSTREAM_JOINED) {
331    forward_on(up);
332    send_join(up);
333    join_timer_start(up);
334  }
335  else {
336    forward_off(up);
337    pim_joinprune_send(up->rpf.source_nexthop.interface,
338		       up->rpf.rpf_addr,
339		       up->source_addr,
340		       up->group_addr,
341		       0 /* prune */);
342    zassert(up->t_join_timer);
343    THREAD_OFF(up->t_join_timer);
344  }
345
346}
347
348static struct pim_upstream *pim_upstream_new(struct in_addr source_addr,
349					     struct in_addr group_addr)
350{
351  struct pim_upstream *up;
352
353  up = XMALLOC(MTYPE_PIM_UPSTREAM, sizeof(*up));
354  if (!up) {
355    zlog_err("%s: PIM XMALLOC(%zu) failure",
356	     __PRETTY_FUNCTION__, sizeof(*up));
357    return 0;
358  }
359
360  up->source_addr                = source_addr;
361  up->group_addr                 = group_addr;
362  up->flags                      = 0;
363  up->ref_count                  = 1;
364  up->t_join_timer               = 0;
365  up->join_state                 = 0;
366  up->state_transition           = pim_time_monotonic_sec();
367  up->channel_oil                = 0;
368
369  up->rpf.source_nexthop.interface                = 0;
370  up->rpf.source_nexthop.mrib_nexthop_addr.s_addr = PIM_NET_INADDR_ANY;
371  up->rpf.source_nexthop.mrib_metric_preference   = qpim_infinite_assert_metric.metric_preference;
372  up->rpf.source_nexthop.mrib_route_metric        = qpim_infinite_assert_metric.route_metric;
373  up->rpf.rpf_addr.s_addr                         = PIM_NET_INADDR_ANY;
374
375  pim_rpf_update(up, 0);
376
377  listnode_add(qpim_upstream_list, up);
378
379  return up;
380}
381
382struct pim_upstream *pim_upstream_find(struct in_addr source_addr,
383				       struct in_addr group_addr)
384{
385  struct listnode     *up_node;
386  struct pim_upstream *up;
387
388  for (ALL_LIST_ELEMENTS_RO(qpim_upstream_list, up_node, up)) {
389    if (
390	(source_addr.s_addr == up->source_addr.s_addr) &&
391	(group_addr.s_addr == up->group_addr.s_addr)
392	) {
393      return up;
394    }
395  }
396
397  return 0;
398}
399
400struct pim_upstream *pim_upstream_add(struct in_addr source_addr,
401				      struct in_addr group_addr)
402{
403  struct pim_upstream *up;
404
405  up = pim_upstream_find(source_addr, group_addr);
406  if (up) {
407    ++up->ref_count;
408  }
409  else {
410    up = pim_upstream_new(source_addr, group_addr);
411  }
412
413  return up;
414}
415
416void pim_upstream_del(struct pim_upstream *up)
417{
418  --up->ref_count;
419
420  if (up->ref_count < 1) {
421    pim_upstream_delete(up);
422  }
423}
424
425/*
426  Evaluate JoinDesired(S,G):
427
428  JoinDesired(S,G) is true if there is a downstream (S,G) interface I
429  in the set:
430
431  inherited_olist(S,G) =
432  joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
433
434  JoinDesired(S,G) may be affected by changes in the following:
435
436  pim_ifp->primary_address
437  pim_ifp->pim_dr_addr
438  ch->ifassert_winner_metric
439  ch->ifassert_winner
440  ch->local_ifmembership
441  ch->ifjoin_state
442  ch->upstream->rpf.source_nexthop.mrib_metric_preference
443  ch->upstream->rpf.source_nexthop.mrib_route_metric
444  ch->upstream->rpf.source_nexthop.interface
445
446  See also pim_upstream_update_join_desired() below.
447 */
448int pim_upstream_evaluate_join_desired(struct pim_upstream *up)
449{
450  struct listnode      *ifnode;
451  struct listnode      *ifnextnode;
452  struct listnode      *chnode;
453  struct listnode      *chnextnode;
454  struct interface     *ifp;
455  struct pim_interface *pim_ifp;
456  struct pim_ifchannel *ch;
457
458  /* scan all interfaces */
459  for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) {
460    pim_ifp = ifp->info;
461    if (!pim_ifp)
462      continue;
463
464    /* scan per-interface (S,G) state */
465    for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) {
466      if (ch->upstream != up)
467	continue;
468
469      if (pim_macro_ch_lost_assert(ch))
470	continue; /* keep searching */
471
472      if (pim_macro_chisin_joins_or_include(ch))
473	return 1; /* true */
474    } /* scan iface channel list */
475  } /* scan iflist */
476
477  return 0; /* false */
478}
479
480/*
481  See also pim_upstream_evaluate_join_desired() above.
482*/
483void pim_upstream_update_join_desired(struct pim_upstream *up)
484{
485  int was_join_desired; /* boolean */
486  int is_join_desired; /* boolean */
487
488  was_join_desired = PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(up->flags);
489
490  is_join_desired = pim_upstream_evaluate_join_desired(up);
491  if (is_join_desired)
492    PIM_UPSTREAM_FLAG_SET_DR_JOIN_DESIRED(up->flags);
493  else
494    PIM_UPSTREAM_FLAG_UNSET_DR_JOIN_DESIRED(up->flags);
495
496  /* switched from false to true */
497  if (is_join_desired && !was_join_desired) {
498    zassert(up->join_state == PIM_UPSTREAM_NOTJOINED);
499    pim_upstream_switch(up, PIM_UPSTREAM_JOINED);
500    return;
501  }
502
503  /* switched from true to false */
504  if (!is_join_desired && was_join_desired) {
505    zassert(up->join_state == PIM_UPSTREAM_JOINED);
506    pim_upstream_switch(up, PIM_UPSTREAM_NOTJOINED);
507    return;
508  }
509}
510
511/*
512  RFC 4601 4.5.7. Sending (S,G) Join/Prune Messages
513  Transitions from Joined State
514  RPF'(S,G) GenID changes
515
516  The upstream (S,G) state machine remains in Joined state.  If the
517  Join Timer is set to expire in more than t_override seconds, reset
518  it so that it expires after t_override seconds.
519*/
520void pim_upstream_rpf_genid_changed(struct in_addr neigh_addr)
521{
522  struct listnode     *up_node;
523  struct listnode     *up_nextnode;
524  struct pim_upstream *up;
525
526  /*
527    Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
528  */
529  for (ALL_LIST_ELEMENTS(qpim_upstream_list, up_node, up_nextnode, up)) {
530
531    if (PIM_DEBUG_PIM_TRACE) {
532      char neigh_str[100];
533      char src_str[100];
534      char grp_str[100];
535      char rpf_addr_str[100];
536      pim_inet4_dump("<neigh?>", neigh_addr, neigh_str, sizeof(neigh_str));
537      pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str));
538      pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str));
539      pim_inet4_dump("<rpf?>", up->rpf.rpf_addr, rpf_addr_str, sizeof(rpf_addr_str));
540      zlog_debug("%s: matching neigh=%s against upstream (S,G)=(%s,%s) joined=%d rpf_addr=%s",
541		 __PRETTY_FUNCTION__,
542		 neigh_str, src_str, grp_str,
543		 up->join_state == PIM_UPSTREAM_JOINED,
544		 rpf_addr_str);
545    }
546
547    /* consider only (S,G) upstream in Joined state */
548    if (up->join_state != PIM_UPSTREAM_JOINED)
549      continue;
550
551    /* match RPF'(S,G)=neigh_addr */
552    if (up->rpf.rpf_addr.s_addr != neigh_addr.s_addr)
553      continue;
554
555    pim_upstream_join_timer_decrease_to_t_override("RPF'(S,G) GenID change",
556						   up, neigh_addr);
557  }
558}
559
560
561void pim_upstream_rpf_interface_changed(struct pim_upstream *up,
562					struct interface *old_rpf_ifp)
563{
564  struct listnode  *ifnode;
565  struct listnode  *ifnextnode;
566  struct interface *ifp;
567
568  /* scan all interfaces */
569  for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) {
570    struct listnode      *chnode;
571    struct listnode      *chnextnode;
572    struct pim_ifchannel *ch;
573    struct pim_interface *pim_ifp;
574
575    pim_ifp = ifp->info;
576    if (!pim_ifp)
577      continue;
578
579    /* search all ifchannels */
580    for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) {
581      if (ch->upstream != up)
582	continue;
583
584      if (ch->ifassert_state == PIM_IFASSERT_I_AM_LOSER) {
585	if (
586	    /* RPF_interface(S) was NOT I */
587	    (old_rpf_ifp == ch->interface)
588	    &&
589	    /* RPF_interface(S) stopped being I */
590	    (ch->upstream->rpf.source_nexthop.interface != ch->interface)
591	    ) {
592	  assert_action_a5(ch);
593	}
594      } /* PIM_IFASSERT_I_AM_LOSER */
595
596      pim_ifchannel_update_assert_tracking_desired(ch);
597    }
598  }
599}
600
601void pim_upstream_update_could_assert(struct pim_upstream *up)
602{
603  struct listnode      *ifnode;
604  struct listnode      *ifnextnode;
605  struct listnode      *chnode;
606  struct listnode      *chnextnode;
607  struct interface     *ifp;
608  struct pim_interface *pim_ifp;
609  struct pim_ifchannel *ch;
610
611  /* scan all interfaces */
612  for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) {
613    pim_ifp = ifp->info;
614    if (!pim_ifp)
615      continue;
616
617    /* scan per-interface (S,G) state */
618    for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) {
619
620      if (ch->upstream != up)
621	continue;
622
623      pim_ifchannel_update_could_assert(ch);
624
625    } /* scan iface channel list */
626  } /* scan iflist */
627}
628
629void pim_upstream_update_my_assert_metric(struct pim_upstream *up)
630{
631  struct listnode      *ifnode;
632  struct listnode      *ifnextnode;
633  struct listnode      *chnode;
634  struct listnode      *chnextnode;
635  struct interface     *ifp;
636  struct pim_interface *pim_ifp;
637  struct pim_ifchannel *ch;
638
639  /* scan all interfaces */
640  for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) {
641    pim_ifp = ifp->info;
642    if (!pim_ifp)
643      continue;
644
645    /* scan per-interface (S,G) state */
646    for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) {
647
648      if (ch->upstream != up)
649	continue;
650
651      pim_ifchannel_update_my_assert_metric(ch);
652
653    } /* scan iface channel list */
654  } /* scan iflist */
655}
656
657static void pim_upstream_update_assert_tracking_desired(struct pim_upstream *up)
658{
659  struct listnode      *ifnode;
660  struct listnode      *ifnextnode;
661  struct listnode      *chnode;
662  struct listnode      *chnextnode;
663  struct interface     *ifp;
664  struct pim_interface *pim_ifp;
665  struct pim_ifchannel *ch;
666
667  /* scan all interfaces */
668  for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) {
669    pim_ifp = ifp->info;
670    if (!pim_ifp)
671      continue;
672
673    /* scan per-interface (S,G) state */
674    for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) {
675
676      if (ch->upstream != up)
677	continue;
678
679      pim_ifchannel_update_assert_tracking_desired(ch);
680
681    } /* scan iface channel list */
682  } /* scan iflist */
683}
684