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