Annotation of embedaddon/quagga/ospfd/ospf_ism.c, revision 1.1.1.1
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: struct ospf_neighbor *dr, *bdr;
207:
208: /* backup current values. */
209: old_dr = DR (oi);
210: old_bdr = BDR (oi);
211: old_state = oi->state;
212:
213: el_list = list_new ();
214:
215: /* List eligible routers. */
216: ospf_dr_eligible_routers (oi->nbrs, el_list);
217:
218: /* First election of DR and BDR. */
219: bdr = ospf_elect_bdr (oi, el_list);
220: dr = ospf_elect_dr (oi, el_list);
221:
222: new_state = ospf_ism_state (oi);
223:
224: zlog_debug ("DR-Election[1st]: Backup %s", inet_ntoa (BDR (oi)));
225: zlog_debug ("DR-Election[1st]: DR %s", inet_ntoa (DR (oi)));
226:
227: if (new_state != old_state &&
228: !(new_state == ISM_DROther && old_state < ISM_DROther))
229: {
230: ospf_elect_bdr (oi, el_list);
231: ospf_elect_dr (oi, el_list);
232:
233: new_state = ospf_ism_state (oi);
234:
235: zlog_debug ("DR-Election[2nd]: Backup %s", inet_ntoa (BDR (oi)));
236: zlog_debug ("DR-Election[2nd]: DR %s", inet_ntoa (DR (oi)));
237: }
238:
239: list_delete (el_list);
240:
241: /* if DR or BDR changes, cause AdjOK? neighbor event. */
242: if (!IPV4_ADDR_SAME (&old_dr, &DR (oi)) ||
243: !IPV4_ADDR_SAME (&old_bdr, &BDR (oi)))
244: ospf_dr_change (oi->ospf, oi->nbrs);
245:
246: return new_state;
247: }
248:
249:
250: int
251: ospf_hello_timer (struct thread *thread)
252: {
253: struct ospf_interface *oi;
254:
255: oi = THREAD_ARG (thread);
256: oi->t_hello = NULL;
257:
258: if (IS_DEBUG_OSPF (ism, ISM_TIMERS))
259: zlog (NULL, LOG_DEBUG, "ISM[%s]: Timer (Hello timer expire)",
260: IF_NAME (oi));
261:
262: /* Sending hello packet. */
263: ospf_hello_send (oi);
264:
265: /* Hello timer set. */
266: OSPF_HELLO_TIMER_ON (oi);
267:
268: return 0;
269: }
270:
271: static int
272: ospf_wait_timer (struct thread *thread)
273: {
274: struct ospf_interface *oi;
275:
276: oi = THREAD_ARG (thread);
277: oi->t_wait = NULL;
278:
279: if (IS_DEBUG_OSPF (ism, ISM_TIMERS))
280: zlog (NULL, LOG_DEBUG, "ISM[%s]: Timer (Wait timer expire)",
281: IF_NAME (oi));
282:
283: OSPF_ISM_EVENT_SCHEDULE (oi, ISM_WaitTimer);
284:
285: return 0;
286: }
287:
288: /* Hook function called after ospf ISM event is occured. And vty's
289: network command invoke this function after making interface
290: structure. */
291: static void
292: ism_timer_set (struct ospf_interface *oi)
293: {
294: switch (oi->state)
295: {
296: case ISM_Down:
297: /* First entry point of ospf interface state machine. In this state
298: interface parameters must be set to initial values, and timers are
299: reset also. */
300: OSPF_ISM_TIMER_OFF (oi->t_hello);
301: OSPF_ISM_TIMER_OFF (oi->t_wait);
302: OSPF_ISM_TIMER_OFF (oi->t_ls_ack);
303: break;
304: case ISM_Loopback:
305: /* In this state, the interface may be looped back and will be
306: unavailable for regular data traffic. */
307: OSPF_ISM_TIMER_OFF (oi->t_hello);
308: OSPF_ISM_TIMER_OFF (oi->t_wait);
309: OSPF_ISM_TIMER_OFF (oi->t_ls_ack);
310: break;
311: case ISM_Waiting:
312: /* The router is trying to determine the identity of DRouter and
313: BDRouter. The router begin to receive and send Hello Packets. */
314: /* send first hello immediately */
315: OSPF_ISM_TIMER_MSEC_ON (oi->t_hello, ospf_hello_timer, 1);
316: OSPF_ISM_TIMER_ON (oi->t_wait, ospf_wait_timer,
317: OSPF_IF_PARAM (oi, v_wait));
318: OSPF_ISM_TIMER_OFF (oi->t_ls_ack);
319: break;
320: case ISM_PointToPoint:
321: /* The interface connects to a physical Point-to-point network or
322: virtual link. The router attempts to form an adjacency with
323: neighboring router. Hello packets are also sent. */
324: /* send first hello immediately */
325: OSPF_ISM_TIMER_MSEC_ON (oi->t_hello, ospf_hello_timer, 1);
326: OSPF_ISM_TIMER_OFF (oi->t_wait);
327: OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
328: break;
329: case ISM_DROther:
330: /* The network type of the interface is broadcast or NBMA network,
331: and the router itself is neither Designated Router nor
332: Backup Designated Router. */
333: OSPF_HELLO_TIMER_ON (oi);
334: OSPF_ISM_TIMER_OFF (oi->t_wait);
335: OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
336: break;
337: case ISM_Backup:
338: /* The network type of the interface is broadcast os NBMA network,
339: and the router is Backup Designated Router. */
340: OSPF_HELLO_TIMER_ON (oi);
341: OSPF_ISM_TIMER_OFF (oi->t_wait);
342: OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
343: break;
344: case ISM_DR:
345: /* The network type of the interface is broadcast or NBMA network,
346: and the router is Designated Router. */
347: OSPF_HELLO_TIMER_ON (oi);
348: OSPF_ISM_TIMER_OFF (oi->t_wait);
349: OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
350: break;
351: }
352: }
353:
354: static int
355: ism_interface_up (struct ospf_interface *oi)
356: {
357: int next_state = 0;
358:
359: /* if network type is point-to-point, Point-to-MultiPoint or virtual link,
360: the state transitions to Point-to-Point. */
361: if (oi->type == OSPF_IFTYPE_POINTOPOINT ||
362: oi->type == OSPF_IFTYPE_POINTOMULTIPOINT ||
363: oi->type == OSPF_IFTYPE_VIRTUALLINK)
364: next_state = ISM_PointToPoint;
365: /* Else if the router is not eligible to DR, the state transitions to
366: DROther. */
367: else if (PRIORITY (oi) == 0) /* router is eligible? */
368: next_state = ISM_DROther;
369: else
370: /* Otherwise, the state transitions to Waiting. */
371: next_state = ISM_Waiting;
372:
373: if (oi->type == OSPF_IFTYPE_NBMA)
374: ospf_nbr_nbma_if_update (oi->ospf, oi);
375:
376: /* ospf_ism_event (t); */
377: return next_state;
378: }
379:
380: static int
381: ism_loop_ind (struct ospf_interface *oi)
382: {
383: int ret = 0;
384:
385: /* call ism_interface_down. */
386: /* ret = ism_interface_down (oi); */
387:
388: return ret;
389: }
390:
391: /* Interface down event handler. */
392: static int
393: ism_interface_down (struct ospf_interface *oi)
394: {
395: ospf_if_cleanup (oi);
396: return 0;
397: }
398:
399:
400: static int
401: ism_backup_seen (struct ospf_interface *oi)
402: {
403: return ospf_dr_election (oi);
404: }
405:
406: static int
407: ism_wait_timer (struct ospf_interface *oi)
408: {
409: return ospf_dr_election (oi);
410: }
411:
412: static int
413: ism_neighbor_change (struct ospf_interface *oi)
414: {
415: return ospf_dr_election (oi);
416: }
417:
418: static int
419: ism_ignore (struct ospf_interface *oi)
420: {
421: if (IS_DEBUG_OSPF (ism, ISM_EVENTS))
422: zlog (NULL, LOG_DEBUG, "ISM[%s]: ism_ignore called", IF_NAME (oi));
423:
424: return 0;
425: }
426:
427: /* Interface State Machine */
428: struct {
429: int (*func) (struct ospf_interface *);
430: int next_state;
431: } ISM [OSPF_ISM_STATE_MAX][OSPF_ISM_EVENT_MAX] =
432: {
433: {
434: /* DependUpon: dummy state. */
435: { ism_ignore, ISM_DependUpon }, /* NoEvent */
436: { ism_ignore, ISM_DependUpon }, /* InterfaceUp */
437: { ism_ignore, ISM_DependUpon }, /* WaitTimer */
438: { ism_ignore, ISM_DependUpon }, /* BackupSeen */
439: { ism_ignore, ISM_DependUpon }, /* NeighborChange */
440: { ism_ignore, ISM_DependUpon }, /* LoopInd */
441: { ism_ignore, ISM_DependUpon }, /* UnloopInd */
442: { ism_ignore, ISM_DependUpon }, /* InterfaceDown */
443: },
444: {
445: /* Down:*/
446: { ism_ignore, ISM_DependUpon }, /* NoEvent */
447: { ism_interface_up, ISM_DependUpon }, /* InterfaceUp */
448: { ism_ignore, ISM_Down }, /* WaitTimer */
449: { ism_ignore, ISM_Down }, /* BackupSeen */
450: { ism_ignore, ISM_Down }, /* NeighborChange */
451: { ism_loop_ind, ISM_Loopback }, /* LoopInd */
452: { ism_ignore, ISM_Down }, /* UnloopInd */
453: { ism_interface_down, ISM_Down }, /* InterfaceDown */
454: },
455: {
456: /* Loopback: */
457: { ism_ignore, ISM_DependUpon }, /* NoEvent */
458: { ism_ignore, ISM_Loopback }, /* InterfaceUp */
459: { ism_ignore, ISM_Loopback }, /* WaitTimer */
460: { ism_ignore, ISM_Loopback }, /* BackupSeen */
461: { ism_ignore, ISM_Loopback }, /* NeighborChange */
462: { ism_ignore, ISM_Loopback }, /* LoopInd */
463: { ism_ignore, ISM_Down }, /* UnloopInd */
464: { ism_interface_down, ISM_Down }, /* InterfaceDown */
465: },
466: {
467: /* Waiting: */
468: { ism_ignore, ISM_DependUpon }, /* NoEvent */
469: { ism_ignore, ISM_Waiting }, /* InterfaceUp */
470: { ism_wait_timer, ISM_DependUpon }, /* WaitTimer */
471: { ism_backup_seen, ISM_DependUpon }, /* BackupSeen */
472: { ism_ignore, ISM_Waiting }, /* NeighborChange */
473: { ism_loop_ind, ISM_Loopback }, /* LoopInd */
474: { ism_ignore, ISM_Waiting }, /* UnloopInd */
475: { ism_interface_down, ISM_Down }, /* InterfaceDown */
476: },
477: {
478: /* Point-to-Point: */
479: { ism_ignore, ISM_DependUpon }, /* NoEvent */
480: { ism_ignore, ISM_PointToPoint }, /* InterfaceUp */
481: { ism_ignore, ISM_PointToPoint }, /* WaitTimer */
482: { ism_ignore, ISM_PointToPoint }, /* BackupSeen */
483: { ism_ignore, ISM_PointToPoint }, /* NeighborChange */
484: { ism_loop_ind, ISM_Loopback }, /* LoopInd */
485: { ism_ignore, ISM_PointToPoint }, /* UnloopInd */
486: { ism_interface_down, ISM_Down }, /* InterfaceDown */
487: },
488: {
489: /* DROther: */
490: { ism_ignore, ISM_DependUpon }, /* NoEvent */
491: { ism_ignore, ISM_DROther }, /* InterfaceUp */
492: { ism_ignore, ISM_DROther }, /* WaitTimer */
493: { ism_ignore, ISM_DROther }, /* BackupSeen */
494: { ism_neighbor_change, ISM_DependUpon }, /* NeighborChange */
495: { ism_loop_ind, ISM_Loopback }, /* LoopInd */
496: { ism_ignore, ISM_DROther }, /* UnloopInd */
497: { ism_interface_down, ISM_Down }, /* InterfaceDown */
498: },
499: {
500: /* Backup: */
501: { ism_ignore, ISM_DependUpon }, /* NoEvent */
502: { ism_ignore, ISM_Backup }, /* InterfaceUp */
503: { ism_ignore, ISM_Backup }, /* WaitTimer */
504: { ism_ignore, ISM_Backup }, /* BackupSeen */
505: { ism_neighbor_change, ISM_DependUpon }, /* NeighborChange */
506: { ism_loop_ind, ISM_Loopback }, /* LoopInd */
507: { ism_ignore, ISM_Backup }, /* UnloopInd */
508: { ism_interface_down, ISM_Down }, /* InterfaceDown */
509: },
510: {
511: /* DR: */
512: { ism_ignore, ISM_DependUpon }, /* NoEvent */
513: { ism_ignore, ISM_DR }, /* InterfaceUp */
514: { ism_ignore, ISM_DR }, /* WaitTimer */
515: { ism_ignore, ISM_DR }, /* BackupSeen */
516: { ism_neighbor_change, ISM_DependUpon }, /* NeighborChange */
517: { ism_loop_ind, ISM_Loopback }, /* LoopInd */
518: { ism_ignore, ISM_DR }, /* UnloopInd */
519: { ism_interface_down, ISM_Down }, /* InterfaceDown */
520: },
521: };
522:
523: static const char *ospf_ism_event_str[] =
524: {
525: "NoEvent",
526: "InterfaceUp",
527: "WaitTimer",
528: "BackupSeen",
529: "NeighborChange",
530: "LoopInd",
531: "UnLoopInd",
532: "InterfaceDown",
533: };
534:
535: static void
536: ism_change_state (struct ospf_interface *oi, int state)
537: {
538: int old_state;
539: struct ospf_lsa *lsa;
540:
541: /* Logging change of state. */
542: if (IS_DEBUG_OSPF (ism, ISM_STATUS))
543: zlog (NULL, LOG_DEBUG, "ISM[%s]: State change %s -> %s", IF_NAME (oi),
544: LOOKUP (ospf_ism_state_msg, oi->state),
545: LOOKUP (ospf_ism_state_msg, state));
546:
547: old_state = oi->state;
548: oi->state = state;
549: oi->state_change++;
550:
551: #ifdef HAVE_SNMP
552: /* Terminal state or regression */
553: if ((state == ISM_DR) || (state == ISM_Backup) || (state == ISM_DROther) ||
554: (state == ISM_PointToPoint) || (state < old_state))
555: {
556: /* ospfVirtIfStateChange */
557: if (oi->type == OSPF_IFTYPE_VIRTUALLINK)
558: ospfTrapVirtIfStateChange (oi);
559: /* ospfIfStateChange */
560: else
561: ospfTrapIfStateChange (oi);
562: }
563: #endif
564:
565: /* Set multicast memberships appropriately for new state. */
566: ospf_if_set_multicast(oi);
567:
568: if (old_state == ISM_Down || state == ISM_Down)
569: ospf_check_abr_status (oi->ospf);
570:
571: /* Originate router-LSA. */
572: if (state == ISM_Down)
573: {
574: if (oi->area->act_ints > 0)
575: oi->area->act_ints--;
576: }
577: else if (old_state == ISM_Down)
578: oi->area->act_ints++;
579:
580: /* schedule router-LSA originate. */
581: ospf_router_lsa_update_area (oi->area);
582:
583: /* Originate network-LSA. */
584: if (old_state != ISM_DR && state == ISM_DR)
585: ospf_network_lsa_update (oi);
586: else if (old_state == ISM_DR && state != ISM_DR)
587: {
588: /* Free self originated network LSA. */
589: lsa = oi->network_lsa_self;
590: if (lsa)
591: ospf_lsa_flush_area (lsa, oi->area);
592:
593: ospf_lsa_unlock (&oi->network_lsa_self);
594: oi->network_lsa_self = NULL;
595: }
596:
597: #ifdef HAVE_OPAQUE_LSA
598: ospf_opaque_ism_change (oi, old_state);
599: #endif /* HAVE_OPAQUE_LSA */
600:
601: /* Check area border status. */
602: ospf_check_abr_status (oi->ospf);
603: }
604:
605: /* Execute ISM event process. */
606: int
607: ospf_ism_event (struct thread *thread)
608: {
609: int event;
610: int next_state;
611: struct ospf_interface *oi;
612:
613: oi = THREAD_ARG (thread);
614: event = THREAD_VAL (thread);
615:
616: /* Call function. */
617: next_state = (*(ISM [oi->state][event].func))(oi);
618:
619: if (! next_state)
620: next_state = ISM [oi->state][event].next_state;
621:
622: if (IS_DEBUG_OSPF (ism, ISM_EVENTS))
623: zlog (NULL, LOG_DEBUG, "ISM[%s]: %s (%s)", IF_NAME (oi),
624: LOOKUP (ospf_ism_state_msg, oi->state),
625: ospf_ism_event_str[event]);
626:
627: /* If state is changed. */
628: if (next_state != oi->state)
629: ism_change_state (oi, next_state);
630:
631: /* Make sure timer is set. */
632: ism_timer_set (oi);
633:
634: return 0;
635: }
636:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>