Annotation of embedaddon/quagga/ospfd/ospf_ism.c, revision 1.1.1.2
1.1 misho 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. */
1.1.1.2 ! misho 218: ospf_elect_bdr (oi, el_list);
! 219: ospf_elect_dr (oi, el_list);
1.1 misho 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: #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. */
605: int
606: ospf_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:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>