New upstream version 1.2.4
[quagga-debian.git] / ospfd / ospf_ism.c
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 */
49 static struct ospf_neighbor *
50 ospf_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
74 static struct ospf_neighbor *
75 ospf_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
112 static struct ospf_neighbor *
113 ospf_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
154 static int
155 ospf_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
165 static void
166 ospf_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. */
183 static void
184 ospf_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
200 static int
201 ospf_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
249 int
250 ospf_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
270 static int
271 ospf_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. */
290 static void
291 ism_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
353 static int
354 ism_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
379 static int
380 ism_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. */
391 static int
392 ism_interface_down (struct ospf_interface *oi)
393 {
394   ospf_if_cleanup (oi);
395   return 0;
396 }
397
398
399 static int
400 ism_backup_seen (struct ospf_interface *oi)
401 {
402   return ospf_dr_election (oi);
403 }
404
405 static int
406 ism_wait_timer (struct ospf_interface *oi)
407 {
408   return ospf_dr_election (oi);
409 }
410
411 static int
412 ism_neighbor_change (struct ospf_interface *oi)
413 {
414   return ospf_dr_election (oi);
415 }
416
417 static int
418 ism_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 */
427 struct {
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
522 static 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
534 static void
535 ism_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   ospf_opaque_ism_change (oi, old_state);
597
598   /* Check area border status.  */
599   ospf_check_abr_status (oi->ospf);
600 }
601
602 /* Execute ISM event process. */
603 int
604 ospf_ism_event (struct thread *thread)
605 {
606   int event;
607   int next_state;
608   struct ospf_interface *oi;
609
610   oi = THREAD_ARG (thread);
611   event = THREAD_VAL (thread);
612
613   /* Call function. */
614   next_state = (*(ISM [oi->state][event].func))(oi);
615
616   if (! next_state)
617     next_state = ISM [oi->state][event].next_state;
618
619   if (IS_DEBUG_OSPF (ism, ISM_EVENTS))
620     zlog (NULL, LOG_DEBUG, "ISM[%s]: %s (%s)", IF_NAME (oi),
621           LOOKUP (ospf_ism_state_msg, oi->state),
622           ospf_ism_event_str[event]);
623
624   /* If state is changed. */
625   if (next_state != oi->state)
626     ism_change_state (oi, next_state);
627
628   /* Make sure timer is set. */
629   ism_timer_set (oi);
630
631   return 0;
632 }
633