1/*
2 * OSPF version 2  Interface State Machine
3 *   From RFC2328 [OSPF Version 2]
4 * Copyright (C) 1999, 2000 Toshiaki Takada
5 *
6 * This file is part of GNU Zebra.
7 *
8 * GNU Zebra is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation; either version 2, or (at your option) any
11 * later version.
12 *
13 * GNU Zebra is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with GNU Zebra; see the file COPYING.  If not, write to the Free
20 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
21 * 02111-1307, USA.
22 */
23
24#include <zebra.h>
25
26#include "thread.h"
27#include "linklist.h"
28#include "prefix.h"
29#include "if.h"
30#include "table.h"
31#include "log.h"
32
33#include "ospfd/ospfd.h"
34#include "ospfd/ospf_interface.h"
35#include "ospfd/ospf_ism.h"
36#include "ospfd/ospf_asbr.h"
37#include "ospfd/ospf_lsa.h"
38#include "ospfd/ospf_lsdb.h"
39#include "ospfd/ospf_neighbor.h"
40#include "ospfd/ospf_nsm.h"
41#include "ospfd/ospf_network.h"
42#include "ospfd/ospf_dump.h"
43#include "ospfd/ospf_packet.h"
44#include "ospfd/ospf_flood.h"
45#include "ospfd/ospf_abr.h"
46#include "ospfd/ospf_snmp.h"
47
48/* elect DR and BDR. Refer to RFC2319 section 9.4 */
49static struct ospf_neighbor *
50ospf_dr_election_sub (struct list *routers)
51{
52  struct listnode *node;
53  struct ospf_neighbor *nbr, *max = NULL;
54
55  /* Choose highest router priority.
56     In case of tie, choose highest Router ID. */
57  for (ALL_LIST_ELEMENTS_RO (routers, node, nbr))
58    {
59      if (max == NULL)
60	max = nbr;
61      else
62	{
63	  if (max->priority < nbr->priority)
64	    max = nbr;
65	  else if (max->priority == nbr->priority)
66	    if (IPV4_ADDR_CMP (&max->router_id, &nbr->router_id) < 0)
67	      max = nbr;
68	}
69    }
70
71  return max;
72}
73
74static struct ospf_neighbor *
75ospf_elect_dr (struct ospf_interface *oi, struct list *el_list)
76{
77  struct list *dr_list;
78  struct listnode *node;
79  struct ospf_neighbor *nbr, *dr = NULL, *bdr = NULL;
80
81  dr_list = list_new ();
82
83  /* Add neighbors to the list. */
84  for (ALL_LIST_ELEMENTS_RO (el_list, node, nbr))
85    {
86      /* neighbor declared to be DR. */
87      if (NBR_IS_DR (nbr))
88	listnode_add (dr_list, nbr);
89
90      /* Preserve neighbor BDR. */
91      if (IPV4_ADDR_SAME (&BDR (oi), &nbr->address.u.prefix4))
92	bdr = nbr;
93    }
94
95  /* Elect Designated Router. */
96  if (listcount (dr_list) > 0)
97    dr = ospf_dr_election_sub (dr_list);
98  else
99    dr = bdr;
100
101  /* Set DR to interface. */
102  if (dr)
103    DR (oi) = dr->address.u.prefix4;
104  else
105    DR (oi).s_addr = 0;
106
107  list_delete (dr_list);
108
109  return dr;
110}
111
112static struct ospf_neighbor *
113ospf_elect_bdr (struct ospf_interface *oi, struct list *el_list)
114{
115  struct list *bdr_list, *no_dr_list;
116  struct listnode *node;
117  struct ospf_neighbor *nbr, *bdr = NULL;
118
119  bdr_list = list_new ();
120  no_dr_list = list_new ();
121
122  /* Add neighbors to the list. */
123  for (ALL_LIST_ELEMENTS_RO (el_list, node, nbr))
124    {
125      /* neighbor declared to be DR. */
126      if (NBR_IS_DR (nbr))
127	continue;
128
129      /* neighbor declared to be BDR. */
130      if (NBR_IS_BDR (nbr))
131	listnode_add (bdr_list, nbr);
132
133      listnode_add (no_dr_list, nbr);
134    }
135
136  /* Elect Backup Designated Router. */
137  if (listcount (bdr_list) > 0)
138    bdr = ospf_dr_election_sub (bdr_list);
139  else
140    bdr = ospf_dr_election_sub (no_dr_list);
141
142  /* Set BDR to interface. */
143  if (bdr)
144    BDR (oi) = bdr->address.u.prefix4;
145  else
146    BDR (oi).s_addr = 0;
147
148  list_delete (bdr_list);
149  list_delete (no_dr_list);
150
151  return bdr;
152}
153
154static int
155ospf_ism_state (struct ospf_interface *oi)
156{
157  if (IPV4_ADDR_SAME (&DR (oi), &oi->address->u.prefix4))
158    return ISM_DR;
159  else if (IPV4_ADDR_SAME (&BDR (oi), &oi->address->u.prefix4))
160    return ISM_Backup;
161  else
162    return ISM_DROther;
163}
164
165static void
166ospf_dr_eligible_routers (struct route_table *nbrs, struct list *el_list)
167{
168  struct route_node *rn;
169  struct ospf_neighbor *nbr;
170
171  for (rn = route_top (nbrs); rn; rn = route_next (rn))
172    if ((nbr = rn->info) != NULL)
173      /* Ignore 0.0.0.0 node*/
174      if (nbr->router_id.s_addr != 0)
175	/* Is neighbor eligible? */
176	if (nbr->priority > 0)
177	  /* Is neighbor upper 2-Way? */
178	  if (nbr->state >= NSM_TwoWay)
179	    listnode_add (el_list, nbr);
180}
181
182/* Generate AdjOK? NSM event. */
183static void
184ospf_dr_change (struct ospf *ospf, struct route_table *nbrs)
185{
186  struct route_node *rn;
187  struct ospf_neighbor *nbr;
188
189  for (rn = route_top (nbrs); rn; rn = route_next (rn))
190    if ((nbr = rn->info) != NULL)
191      /* Ignore 0.0.0.0 node*/
192      if (nbr->router_id.s_addr != 0)
193	/* Is neighbor upper 2-Way? */
194	if (nbr->state >= NSM_TwoWay)
195	  /* Ignore myself. */
196	  if (!IPV4_ADDR_SAME (&nbr->router_id, &ospf->router_id))
197	    OSPF_NSM_EVENT_SCHEDULE (nbr, NSM_AdjOK);
198}
199
200static int
201ospf_dr_election (struct ospf_interface *oi)
202{
203  struct in_addr old_dr, old_bdr;
204  int old_state, new_state;
205  struct list *el_list;
206
207  /* backup current values. */
208  old_dr = DR (oi);
209  old_bdr = BDR (oi);
210  old_state = oi->state;
211
212  el_list = list_new ();
213
214  /* List eligible routers. */
215  ospf_dr_eligible_routers (oi->nbrs, el_list);
216
217  /* First election of DR and BDR. */
218  ospf_elect_bdr (oi, el_list);
219  ospf_elect_dr (oi, el_list);
220
221  new_state = ospf_ism_state (oi);
222
223  zlog_debug ("DR-Election[1st]: Backup %s", inet_ntoa (BDR (oi)));
224  zlog_debug ("DR-Election[1st]: DR     %s", inet_ntoa (DR (oi)));
225
226  if (new_state != old_state &&
227      !(new_state == ISM_DROther && old_state < ISM_DROther))
228    {
229      ospf_elect_bdr (oi, el_list);
230      ospf_elect_dr (oi, el_list);
231
232      new_state = ospf_ism_state (oi);
233
234      zlog_debug ("DR-Election[2nd]: Backup %s", inet_ntoa (BDR (oi)));
235      zlog_debug ("DR-Election[2nd]: DR     %s", inet_ntoa (DR (oi)));
236    }
237
238  list_delete (el_list);
239
240  /* if DR or BDR changes, cause AdjOK? neighbor event. */
241  if (!IPV4_ADDR_SAME (&old_dr, &DR (oi)) ||
242      !IPV4_ADDR_SAME (&old_bdr, &BDR (oi)))
243    ospf_dr_change (oi->ospf, oi->nbrs);
244
245  return new_state;
246}
247
248
249int
250ospf_hello_timer (struct thread *thread)
251{
252  struct ospf_interface *oi;
253
254  oi = THREAD_ARG (thread);
255  oi->t_hello = NULL;
256
257  if (IS_DEBUG_OSPF (ism, ISM_TIMERS))
258    zlog (NULL, LOG_DEBUG, "ISM[%s]: Timer (Hello timer expire)",
259	  IF_NAME (oi));
260
261  /* Sending hello packet. */
262  ospf_hello_send (oi);
263
264  /* Hello timer set. */
265  OSPF_HELLO_TIMER_ON (oi);
266
267  return 0;
268}
269
270static int
271ospf_wait_timer (struct thread *thread)
272{
273  struct ospf_interface *oi;
274
275  oi = THREAD_ARG (thread);
276  oi->t_wait = NULL;
277
278  if (IS_DEBUG_OSPF (ism, ISM_TIMERS))
279    zlog (NULL, LOG_DEBUG, "ISM[%s]: Timer (Wait timer expire)",
280	  IF_NAME (oi));
281
282  OSPF_ISM_EVENT_SCHEDULE (oi, ISM_WaitTimer);
283
284  return 0;
285}
286
287/* Hook function called after ospf ISM event is occured. And vty's
288   network command invoke this function after making interface
289   structure. */
290static void
291ism_timer_set (struct ospf_interface *oi)
292{
293  switch (oi->state)
294    {
295    case ISM_Down:
296      /* First entry point of ospf interface state machine. In this state
297	 interface parameters must be set to initial values, and timers are
298	 reset also. */
299      OSPF_ISM_TIMER_OFF (oi->t_hello);
300      OSPF_ISM_TIMER_OFF (oi->t_wait);
301      OSPF_ISM_TIMER_OFF (oi->t_ls_ack);
302      break;
303    case ISM_Loopback:
304      /* In this state, the interface may be looped back and will be
305	 unavailable for regular data traffic. */
306      OSPF_ISM_TIMER_OFF (oi->t_hello);
307      OSPF_ISM_TIMER_OFF (oi->t_wait);
308      OSPF_ISM_TIMER_OFF (oi->t_ls_ack);
309      break;
310    case ISM_Waiting:
311      /* The router is trying to determine the identity of DRouter and
312	 BDRouter. The router begin to receive and send Hello Packets. */
313      /* send first hello immediately */
314      OSPF_ISM_TIMER_MSEC_ON (oi->t_hello, ospf_hello_timer, 1);
315      OSPF_ISM_TIMER_ON (oi->t_wait, ospf_wait_timer,
316			 OSPF_IF_PARAM (oi, v_wait));
317      OSPF_ISM_TIMER_OFF (oi->t_ls_ack);
318      break;
319    case ISM_PointToPoint:
320      /* The interface connects to a physical Point-to-point network or
321	 virtual link. The router attempts to form an adjacency with
322	 neighboring router. Hello packets are also sent. */
323      /* send first hello immediately */
324      OSPF_ISM_TIMER_MSEC_ON (oi->t_hello, ospf_hello_timer, 1);
325      OSPF_ISM_TIMER_OFF (oi->t_wait);
326      OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
327      break;
328    case ISM_DROther:
329      /* The network type of the interface is broadcast or NBMA network,
330	 and the router itself is neither Designated Router nor
331	 Backup Designated Router. */
332      OSPF_HELLO_TIMER_ON (oi);
333      OSPF_ISM_TIMER_OFF (oi->t_wait);
334      OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
335      break;
336    case ISM_Backup:
337      /* The network type of the interface is broadcast os NBMA network,
338	 and the router is Backup Designated Router. */
339      OSPF_HELLO_TIMER_ON (oi);
340      OSPF_ISM_TIMER_OFF (oi->t_wait);
341      OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
342      break;
343    case ISM_DR:
344      /* The network type of the interface is broadcast or NBMA network,
345	 and the router is Designated Router. */
346      OSPF_HELLO_TIMER_ON (oi);
347      OSPF_ISM_TIMER_OFF (oi->t_wait);
348      OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
349      break;
350    }
351}
352
353static int
354ism_interface_up (struct ospf_interface *oi)
355{
356  int next_state = 0;
357
358  /* if network type is point-to-point, Point-to-MultiPoint or virtual link,
359     the state transitions to Point-to-Point. */
360  if (oi->type == OSPF_IFTYPE_POINTOPOINT ||
361      oi->type == OSPF_IFTYPE_POINTOMULTIPOINT ||
362      oi->type == OSPF_IFTYPE_VIRTUALLINK)
363    next_state = ISM_PointToPoint;
364  /* Else if the router is not eligible to DR, the state transitions to
365     DROther. */
366  else if (PRIORITY (oi) == 0) /* router is eligible? */
367    next_state = ISM_DROther;
368  else
369    /* Otherwise, the state transitions to Waiting. */
370    next_state = ISM_Waiting;
371
372  if (oi->type == OSPF_IFTYPE_NBMA)
373    ospf_nbr_nbma_if_update (oi->ospf, oi);
374
375  /*  ospf_ism_event (t); */
376  return next_state;
377}
378
379static int
380ism_loop_ind (struct ospf_interface *oi)
381{
382  int ret = 0;
383
384  /* call ism_interface_down. */
385  /* ret = ism_interface_down (oi); */
386
387  return ret;
388}
389
390/* Interface down event handler. */
391static int
392ism_interface_down (struct ospf_interface *oi)
393{
394  ospf_if_cleanup (oi);
395  return 0;
396}
397
398
399static int
400ism_backup_seen (struct ospf_interface *oi)
401{
402  return ospf_dr_election (oi);
403}
404
405static int
406ism_wait_timer (struct ospf_interface *oi)
407{
408  return ospf_dr_election (oi);
409}
410
411static int
412ism_neighbor_change (struct ospf_interface *oi)
413{
414  return ospf_dr_election (oi);
415}
416
417static int
418ism_ignore (struct ospf_interface *oi)
419{
420  if (IS_DEBUG_OSPF (ism, ISM_EVENTS))
421    zlog (NULL, LOG_DEBUG, "ISM[%s]: ism_ignore called", IF_NAME (oi));
422
423  return 0;
424}
425
426/* Interface State Machine */
427struct {
428  int (*func) (struct ospf_interface *);
429  int next_state;
430} ISM [OSPF_ISM_STATE_MAX][OSPF_ISM_EVENT_MAX] =
431{
432  {
433    /* DependUpon: dummy state. */
434    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
435    { ism_ignore,          ISM_DependUpon },    /* InterfaceUp    */
436    { ism_ignore,          ISM_DependUpon },    /* WaitTimer      */
437    { ism_ignore,          ISM_DependUpon },    /* BackupSeen     */
438    { ism_ignore,          ISM_DependUpon },    /* NeighborChange */
439    { ism_ignore,          ISM_DependUpon },    /* LoopInd        */
440    { ism_ignore,          ISM_DependUpon },    /* UnloopInd      */
441    { ism_ignore,          ISM_DependUpon },    /* InterfaceDown  */
442  },
443  {
444    /* Down:*/
445    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
446    { ism_interface_up,    ISM_DependUpon },    /* InterfaceUp    */
447    { ism_ignore,          ISM_Down },          /* WaitTimer      */
448    { ism_ignore,          ISM_Down },          /* BackupSeen     */
449    { ism_ignore,          ISM_Down },          /* NeighborChange */
450    { ism_loop_ind,        ISM_Loopback },      /* LoopInd        */
451    { ism_ignore,          ISM_Down },          /* UnloopInd      */
452    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
453  },
454  {
455    /* Loopback: */
456    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
457    { ism_ignore,          ISM_Loopback },      /* InterfaceUp    */
458    { ism_ignore,          ISM_Loopback },      /* WaitTimer      */
459    { ism_ignore,          ISM_Loopback },      /* BackupSeen     */
460    { ism_ignore,          ISM_Loopback },      /* NeighborChange */
461    { ism_ignore,          ISM_Loopback },      /* LoopInd        */
462    { ism_ignore,          ISM_Down },          /* UnloopInd      */
463    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
464  },
465  {
466    /* Waiting: */
467    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
468    { ism_ignore,          ISM_Waiting },       /* InterfaceUp    */
469    { ism_wait_timer,	   ISM_DependUpon },    /* WaitTimer      */
470    { ism_backup_seen,     ISM_DependUpon },    /* BackupSeen     */
471    { ism_ignore,          ISM_Waiting },       /* NeighborChange */
472    { ism_loop_ind,	   ISM_Loopback },      /* LoopInd        */
473    { ism_ignore,          ISM_Waiting },       /* UnloopInd      */
474    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
475  },
476  {
477    /* Point-to-Point: */
478    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
479    { ism_ignore,          ISM_PointToPoint },  /* InterfaceUp    */
480    { ism_ignore,          ISM_PointToPoint },  /* WaitTimer      */
481    { ism_ignore,          ISM_PointToPoint },  /* BackupSeen     */
482    { ism_ignore,          ISM_PointToPoint },  /* NeighborChange */
483    { ism_loop_ind,	   ISM_Loopback },      /* LoopInd        */
484    { ism_ignore,          ISM_PointToPoint },  /* UnloopInd      */
485    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
486  },
487  {
488    /* DROther: */
489    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
490    { ism_ignore,          ISM_DROther },       /* InterfaceUp    */
491    { ism_ignore,          ISM_DROther },       /* WaitTimer      */
492    { ism_ignore,          ISM_DROther },       /* BackupSeen     */
493    { ism_neighbor_change, ISM_DependUpon },    /* NeighborChange */
494    { ism_loop_ind,        ISM_Loopback },      /* LoopInd        */
495    { ism_ignore,          ISM_DROther },       /* UnloopInd      */
496    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
497  },
498  {
499    /* Backup: */
500    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
501    { ism_ignore,          ISM_Backup },        /* InterfaceUp    */
502    { ism_ignore,          ISM_Backup },        /* WaitTimer      */
503    { ism_ignore,          ISM_Backup },        /* BackupSeen     */
504    { ism_neighbor_change, ISM_DependUpon },    /* NeighborChange */
505    { ism_loop_ind,        ISM_Loopback },      /* LoopInd        */
506    { ism_ignore,          ISM_Backup },        /* UnloopInd      */
507    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
508  },
509  {
510    /* DR: */
511    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
512    { ism_ignore,          ISM_DR },            /* InterfaceUp    */
513    { ism_ignore,          ISM_DR },            /* WaitTimer      */
514    { ism_ignore,          ISM_DR },            /* BackupSeen     */
515    { ism_neighbor_change, ISM_DependUpon },    /* NeighborChange */
516    { ism_loop_ind,        ISM_Loopback },      /* LoopInd        */
517    { ism_ignore,          ISM_DR },            /* UnloopInd      */
518    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
519  },
520};
521
522static const char *ospf_ism_event_str[] =
523{
524  "NoEvent",
525  "InterfaceUp",
526  "WaitTimer",
527  "BackupSeen",
528  "NeighborChange",
529  "LoopInd",
530  "UnLoopInd",
531  "InterfaceDown",
532};
533
534static void
535ism_change_state (struct ospf_interface *oi, int state)
536{
537  int old_state;
538  struct ospf_lsa *lsa;
539
540  /* Logging change of state. */
541  if (IS_DEBUG_OSPF (ism, ISM_STATUS))
542    zlog (NULL, LOG_DEBUG, "ISM[%s]: State change %s -> %s", IF_NAME (oi),
543	  LOOKUP (ospf_ism_state_msg, oi->state),
544	  LOOKUP (ospf_ism_state_msg, state));
545
546  old_state = oi->state;
547  oi->state = state;
548  oi->state_change++;
549
550#ifdef HAVE_SNMP
551  /* Terminal state or regression */
552  if ((state == ISM_DR) || (state == ISM_Backup) || (state == ISM_DROther) ||
553      (state == ISM_PointToPoint) || (state < old_state))
554    {
555      /* ospfVirtIfStateChange */
556      if (oi->type == OSPF_IFTYPE_VIRTUALLINK)
557        ospfTrapVirtIfStateChange (oi);
558      /* ospfIfStateChange */
559      else
560        ospfTrapIfStateChange (oi);
561    }
562#endif
563
564  /* Set multicast memberships appropriately for new state. */
565  ospf_if_set_multicast(oi);
566
567  if (old_state == ISM_Down || state == ISM_Down)
568    ospf_check_abr_status (oi->ospf);
569
570  /* Originate router-LSA. */
571  if (state == ISM_Down)
572    {
573      if (oi->area->act_ints > 0)
574        oi->area->act_ints--;
575    }
576  else if (old_state == ISM_Down)
577    oi->area->act_ints++;
578
579  /* schedule router-LSA originate. */
580  ospf_router_lsa_update_area (oi->area);
581
582  /* Originate network-LSA. */
583  if (old_state != ISM_DR && state == ISM_DR)
584    ospf_network_lsa_update (oi);
585  else if (old_state == ISM_DR && state != ISM_DR)
586    {
587      /* Free self originated network LSA. */
588      lsa = oi->network_lsa_self;
589      if (lsa)
590        ospf_lsa_flush_area (lsa, oi->area);
591
592      ospf_lsa_unlock (&oi->network_lsa_self);
593      oi->network_lsa_self = NULL;
594    }
595
596#ifdef HAVE_OPAQUE_LSA
597  ospf_opaque_ism_change (oi, old_state);
598#endif /* HAVE_OPAQUE_LSA */
599
600  /* Check area border status.  */
601  ospf_check_abr_status (oi->ospf);
602}
603
604/* Execute ISM event process. */
605int
606ospf_ism_event (struct thread *thread)
607{
608  int event;
609  int next_state;
610  struct ospf_interface *oi;
611
612  oi = THREAD_ARG (thread);
613  event = THREAD_VAL (thread);
614
615  /* Call function. */
616  next_state = (*(ISM [oi->state][event].func))(oi);
617
618  if (! next_state)
619    next_state = ISM [oi->state][event].next_state;
620
621  if (IS_DEBUG_OSPF (ism, ISM_EVENTS))
622    zlog (NULL, LOG_DEBUG, "ISM[%s]: %s (%s)", IF_NAME (oi),
623	  LOOKUP (ospf_ism_state_msg, oi->state),
624	  ospf_ism_event_str[event]);
625
626  /* If state is changed. */
627  if (next_state != oi->state)
628    ism_change_state (oi, next_state);
629
630  /* Make sure timer is set. */
631  ism_timer_set (oi);
632
633  return 0;
634}
635
636