]> git.proxmox.com Git - mirror_frr.git/blob - ospfd/ospf_spf.c
projects / mirror_frr.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Merge pull request #13649 from donaldsharp/unlock_the_node_or_else
[mirror_frr.git] / ospfd / ospf_spf.c
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* OSPF SPF calculation.
3 * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
4 */
5
6 #include <zebra.h>
7
8 #include "monotime.h"
9 #include "frrevent.h"
10 #include "memory.h"
11 #include "hash.h"
12 #include "linklist.h"
13 #include "prefix.h"
14 #include "if.h"
15 #include "table.h"
16 #include "log.h"
17 #include "sockunion.h" /* for inet_ntop () */
18
19 #include "ospfd/ospfd.h"
20 #include "ospfd/ospf_interface.h"
21 #include "ospfd/ospf_ism.h"
22 #include "ospfd/ospf_asbr.h"
23 #include "ospfd/ospf_lsa.h"
24 #include "ospfd/ospf_lsdb.h"
25 #include "ospfd/ospf_neighbor.h"
26 #include "ospfd/ospf_nsm.h"
27 #include "ospfd/ospf_spf.h"
28 #include "ospfd/ospf_route.h"
29 #include "ospfd/ospf_ia.h"
30 #include "ospfd/ospf_ase.h"
31 #include "ospfd/ospf_abr.h"
32 #include "ospfd/ospf_dump.h"
33 #include "ospfd/ospf_sr.h"
34 #include "ospfd/ospf_ti_lfa.h"
35 #include "ospfd/ospf_errors.h"
36
37 #ifdef SUPPORT_OSPF_API
38 #include "ospfd/ospf_apiserver.h"
39 #endif
40
41 /* Variables to ensure a SPF scheduled log message is printed only once */
42
43 static unsigned int spf_reason_flags = 0;
44
45 /* dummy vertex to flag "in spftree" */
46 static const struct vertex vertex_in_spftree = {};
47 #define LSA_SPF_IN_SPFTREE (struct vertex *)&vertex_in_spftree
48 #define LSA_SPF_NOT_EXPLORED NULL
49
50 static void ospf_clear_spf_reason_flags(void)
51 {
52 spf_reason_flags = 0;
53 }
54
55 static void ospf_spf_set_reason(ospf_spf_reason_t reason)
56 {
57 spf_reason_flags |= 1 << reason;
58 }
59
60 static void ospf_vertex_free(void *);
61
62 /*
63 * Heap related functions, for the managment of the candidates, to
64 * be used with pqueue.
65 */
66 static int vertex_cmp(const struct vertex *v1, const struct vertex *v2)
67 {
68 if (v1->distance != v2->distance)
69 return v1->distance - v2->distance;
70
71 if (v1->type != v2->type) {
72 switch (v1->type) {
73 case OSPF_VERTEX_NETWORK:
74 return -1;
75 case OSPF_VERTEX_ROUTER:
76 return 1;
77 }
78 }
79 return 0;
80 }
81 DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue, struct vertex, pqi, vertex_cmp);
82
83 static void lsdb_clean_stat(struct ospf_lsdb *lsdb)
84 {
85 struct route_table *table;
86 struct route_node *rn;
87 struct ospf_lsa *lsa;
88 int i;
89
90 for (i = OSPF_MIN_LSA; i < OSPF_MAX_LSA; i++) {
91 table = lsdb->type[i].db;
92 for (rn = route_top(table); rn; rn = route_next(rn))
93 if ((lsa = (rn->info)) != NULL)
94 lsa->stat = LSA_SPF_NOT_EXPLORED;
95 }
96 }
97
98 static struct vertex_nexthop *vertex_nexthop_new(void)
99 {
100 return XCALLOC(MTYPE_OSPF_NEXTHOP, sizeof(struct vertex_nexthop));
101 }
102
103 static void vertex_nexthop_free(struct vertex_nexthop *nh)
104 {
105 XFREE(MTYPE_OSPF_NEXTHOP, nh);
106 }
107
108 /*
109 * Free the canonical nexthop objects for an area, ie the nexthop objects
110 * attached to the first-hop router vertices, and any intervening network
111 * vertices.
112 */
113 static void ospf_canonical_nexthops_free(struct vertex *root)
114 {
115 struct listnode *node, *nnode;
116 struct vertex *child;
117
118 for (ALL_LIST_ELEMENTS(root->children, node, nnode, child)) {
119 struct listnode *n2, *nn2;
120 struct vertex_parent *vp;
121
122 /*
123 * router vertices through an attached network each
124 * have a distinct (canonical / not inherited) nexthop
125 * which must be freed.
126 *
127 * A network vertex can only have router vertices as its
128 * children, so only one level of recursion is possible.
129 */
130 if (child->type == OSPF_VERTEX_NETWORK)
131 ospf_canonical_nexthops_free(child);
132
133 /* Free child nexthops pointing back to this root vertex */
134 for (ALL_LIST_ELEMENTS(child->parents, n2, nn2, vp)) {
135 if (vp->parent == root && vp->nexthop) {
136 vertex_nexthop_free(vp->nexthop);
137 vp->nexthop = NULL;
138 if (vp->local_nexthop) {
139 vertex_nexthop_free(vp->local_nexthop);
140 vp->local_nexthop = NULL;
141 }
142 }
143 }
144 }
145 }
146
147 /*
148 * TODO: Parent list should be excised, in favour of maintaining only
149 * vertex_nexthop, with refcounts.
150 */
151 static struct vertex_parent *vertex_parent_new(struct vertex *v, int backlink,
152 struct vertex_nexthop *hop,
153 struct vertex_nexthop *lhop)
154 {
155 struct vertex_parent *new;
156
157 new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT, sizeof(struct vertex_parent));
158
159 new->parent = v;
160 new->backlink = backlink;
161 new->nexthop = hop;
162 new->local_nexthop = lhop;
163
164 return new;
165 }
166
167 static void vertex_parent_free(struct vertex_parent *p)
168 {
169 vertex_nexthop_free(p->local_nexthop);
170 vertex_nexthop_free(p->nexthop);
171 XFREE(MTYPE_OSPF_VERTEX_PARENT, p);
172 }
173
174 int vertex_parent_cmp(void *aa, void *bb)
175 {
176 struct vertex_parent *a = aa, *b = bb;
177 return IPV4_ADDR_CMP(&a->nexthop->router, &b->nexthop->router);
178 }
179
180 static struct vertex *ospf_vertex_new(struct ospf_area *area,
181 struct ospf_lsa *lsa)
182 {
183 struct vertex *new;
184
185 new = XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex));
186
187 new->flags = 0;
188 new->type = lsa->data->type;
189 new->id = lsa->data->id;
190 new->lsa = lsa->data;
191 new->children = list_new();
192 new->parents = list_new();
193 new->parents->del = (void (*)(void *))vertex_parent_free;
194 new->parents->cmp = vertex_parent_cmp;
195 new->lsa_p = lsa;
196
197 lsa->stat = new;
198
199 listnode_add(area->spf_vertex_list, new);
200
201 if (IS_DEBUG_OSPF_EVENT)
202 zlog_debug("%s: Created %s vertex %pI4", __func__,
203 new->type == OSPF_VERTEX_ROUTER ? "Router"
204 : "Network",
205 &new->lsa->id);
206
207 return new;
208 }
209
210 static void ospf_vertex_free(void *data)
211 {
212 struct vertex *v = data;
213
214 if (IS_DEBUG_OSPF_EVENT)
215 zlog_debug("%s: Free %s vertex %pI4", __func__,
216 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
217 &v->lsa->id);
218
219 if (v->children)
220 list_delete(&v->children);
221
222 if (v->parents)
223 list_delete(&v->parents);
224
225 v->lsa = NULL;
226
227 XFREE(MTYPE_OSPF_VERTEX, v);
228 }
229
230 static void ospf_vertex_dump(const char *msg, struct vertex *v,
231 int print_parents, int print_children)
232 {
233 if (!IS_DEBUG_OSPF_EVENT)
234 return;
235
236 zlog_debug("%s %s vertex %pI4 distance %u flags %u", msg,
237 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
238 &v->lsa->id, v->distance, (unsigned int)v->flags);
239
240 if (print_parents) {
241 struct listnode *node;
242 struct vertex_parent *vp;
243
244 for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) {
245 if (vp) {
246 zlog_debug(
247 "parent %pI4 backlink %d nexthop %pI4 lsa pos %d",
248 &vp->parent->lsa->id, vp->backlink,
249 &vp->nexthop->router,
250 vp->nexthop->lsa_pos);
251 }
252 }
253 }
254
255 if (print_children) {
256 struct listnode *cnode;
257 struct vertex *cv;
258
259 for (ALL_LIST_ELEMENTS_RO(v->children, cnode, cv))
260 ospf_vertex_dump(" child:", cv, 0, 0);
261 }
262 }
263
264
265 /* Add a vertex to the list of children in each of its parents. */
266 static void ospf_vertex_add_parent(struct vertex *v)
267 {
268 struct vertex_parent *vp;
269 struct listnode *node;
270
271 assert(v && v->parents);
272
273 for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) {
274 assert(vp->parent && vp->parent->children);
275
276 /* No need to add two links from the same parent. */
277 if (listnode_lookup(vp->parent->children, v) == NULL)
278 listnode_add(vp->parent->children, v);
279 }
280 }
281
282 /* Find a vertex according to its router id */
283 struct vertex *ospf_spf_vertex_find(struct in_addr id, struct list *vertex_list)
284 {
285 struct listnode *node;
286 struct vertex *found;
287
288 for (ALL_LIST_ELEMENTS_RO(vertex_list, node, found)) {
289 if (found->id.s_addr == id.s_addr)
290 return found;
291 }
292
293 return NULL;
294 }
295
296 /* Find a vertex parent according to its router id */
297 struct vertex_parent *ospf_spf_vertex_parent_find(struct in_addr id,
298 struct vertex *vertex)
299 {
300 struct listnode *node;
301 struct vertex_parent *found;
302
303 for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, found)) {
304 if (found->parent->id.s_addr == id.s_addr)
305 return found;
306 }
307
308 return NULL;
309 }
310
311 struct vertex *ospf_spf_vertex_by_nexthop(struct vertex *root,
312 struct in_addr *nexthop)
313 {
314 struct listnode *node;
315 struct vertex *child;
316 struct vertex_parent *vertex_parent;
317
318 for (ALL_LIST_ELEMENTS_RO(root->children, node, child)) {
319 vertex_parent = ospf_spf_vertex_parent_find(root->id, child);
320 if (vertex_parent->nexthop->router.s_addr == nexthop->s_addr)
321 return child;
322 }
323
324 return NULL;
325 }
326
327 /* Create a deep copy of a SPF vertex without children and parents */
328 static struct vertex *ospf_spf_vertex_copy(struct vertex *vertex)
329 {
330 struct vertex *copy;
331
332 copy = XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex));
333
334 memcpy(copy, vertex, sizeof(struct vertex));
335 copy->parents = list_new();
336 copy->parents->del = (void (*)(void *))vertex_parent_free;
337 copy->parents->cmp = vertex_parent_cmp;
338 copy->children = list_new();
339
340 return copy;
341 }
342
343 /* Create a deep copy of a SPF vertex_parent */
344 static struct vertex_parent *
345 ospf_spf_vertex_parent_copy(struct vertex_parent *vertex_parent)
346 {
347 struct vertex_parent *vertex_parent_copy;
348 struct vertex_nexthop *nexthop_copy, *local_nexthop_copy;
349
350 vertex_parent_copy =
351 XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex_parent));
352
353 nexthop_copy = vertex_nexthop_new();
354 local_nexthop_copy = vertex_nexthop_new();
355
356 memcpy(vertex_parent_copy, vertex_parent, sizeof(struct vertex_parent));
357 memcpy(nexthop_copy, vertex_parent->nexthop,
358 sizeof(struct vertex_nexthop));
359 memcpy(local_nexthop_copy, vertex_parent->local_nexthop,
360 sizeof(struct vertex_nexthop));
361
362 vertex_parent_copy->nexthop = nexthop_copy;
363 vertex_parent_copy->local_nexthop = local_nexthop_copy;
364
365 return vertex_parent_copy;
366 }
367
368 /* Create a deep copy of a SPF tree */
369 void ospf_spf_copy(struct vertex *vertex, struct list *vertex_list)
370 {
371 struct listnode *node;
372 struct vertex *vertex_copy, *child, *child_copy, *parent_copy;
373 struct vertex_parent *vertex_parent, *vertex_parent_copy;
374
375 /* First check if the node is already in the vertex list */
376 vertex_copy = ospf_spf_vertex_find(vertex->id, vertex_list);
377 if (!vertex_copy) {
378 vertex_copy = ospf_spf_vertex_copy(vertex);
379 listnode_add(vertex_list, vertex_copy);
380 }
381
382 /* Copy all parents, create parent nodes if necessary */
383 for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, vertex_parent)) {
384 parent_copy = ospf_spf_vertex_find(vertex_parent->parent->id,
385 vertex_list);
386 if (!parent_copy) {
387 parent_copy =
388 ospf_spf_vertex_copy(vertex_parent->parent);
389 listnode_add(vertex_list, parent_copy);
390 }
391 vertex_parent_copy = ospf_spf_vertex_parent_copy(vertex_parent);
392 vertex_parent_copy->parent = parent_copy;
393 listnode_add(vertex_copy->parents, vertex_parent_copy);
394 }
395
396 /* Copy all children, create child nodes if necessary */
397 for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) {
398 child_copy = ospf_spf_vertex_find(child->id, vertex_list);
399 if (!child_copy) {
400 child_copy = ospf_spf_vertex_copy(child);
401 listnode_add(vertex_list, child_copy);
402 }
403 listnode_add(vertex_copy->children, child_copy);
404 }
405
406 /* Finally continue copying with child nodes */
407 for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child))
408 ospf_spf_copy(child, vertex_list);
409 }
410
411 static void ospf_spf_remove_branch(struct vertex_parent *vertex_parent,
412 struct vertex *child,
413 struct list *vertex_list)
414 {
415 struct listnode *node, *nnode, *inner_node, *inner_nnode;
416 struct vertex *grandchild;
417 struct vertex_parent *vertex_parent_found;
418 bool has_more_links = false;
419
420 /*
421 * First check if there are more nexthops for that parent to that child
422 */
423 for (ALL_LIST_ELEMENTS_RO(child->parents, node, vertex_parent_found)) {
424 if (vertex_parent_found->parent->id.s_addr
425 == vertex_parent->parent->id.s_addr
426 && vertex_parent_found->nexthop->router.s_addr
427 != vertex_parent->nexthop->router.s_addr)
428 has_more_links = true;
429 }
430
431 /*
432 * No more links from that parent? Then delete the child from its
433 * children list.
434 */
435 if (!has_more_links)
436 listnode_delete(vertex_parent->parent->children, child);
437
438 /*
439 * Delete the vertex_parent from the child parents list, this needs to
440 * be done anyway.
441 */
442 listnode_delete(child->parents, vertex_parent);
443
444 /*
445 * Are there actually more parents left? If not, then delete the child!
446 * This is done by recursively removing the links to the grandchildren,
447 * such that finally the child can be removed without leaving unused
448 * partial branches.
449 */
450 if (child->parents->count == 0) {
451 for (ALL_LIST_ELEMENTS(child->children, node, nnode,
452 grandchild)) {
453 for (ALL_LIST_ELEMENTS(grandchild->parents, inner_node,
454 inner_nnode,
455 vertex_parent_found)) {
456 ospf_spf_remove_branch(vertex_parent_found,
457 grandchild, vertex_list);
458 }
459 }
460 listnode_delete(vertex_list, child);
461 ospf_vertex_free(child);
462 }
463 }
464
465 static int ospf_spf_remove_link(struct vertex *vertex, struct list *vertex_list,
466 struct router_lsa_link *link)
467 {
468 struct listnode *node, *inner_node;
469 struct vertex *child;
470 struct vertex_parent *vertex_parent;
471
472 /*
473 * Identify the node who shares a subnet (given by the link) with a
474 * child and remove the branch of this particular child.
475 */
476 for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) {
477 for (ALL_LIST_ELEMENTS_RO(child->parents, inner_node,
478 vertex_parent)) {
479 if ((vertex_parent->local_nexthop->router.s_addr
480 & link->link_data.s_addr)
481 == (link->link_id.s_addr
482 & link->link_data.s_addr)) {
483 ospf_spf_remove_branch(vertex_parent, child,
484 vertex_list);
485 return 0;
486 }
487 }
488 }
489
490 /* No link found yet, move on recursively */
491 for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) {
492 if (ospf_spf_remove_link(child, vertex_list, link) == 0)
493 return 0;
494 }
495
496 /* link was not removed yet */
497 return 1;
498 }
499
500 void ospf_spf_remove_resource(struct vertex *vertex, struct list *vertex_list,
501 struct protected_resource *resource)
502 {
503 struct listnode *node, *nnode;
504 struct vertex *found;
505 struct vertex_parent *vertex_parent;
506
507 switch (resource->type) {
508 case OSPF_TI_LFA_LINK_PROTECTION:
509 ospf_spf_remove_link(vertex, vertex_list, resource->link);
510 break;
511 case OSPF_TI_LFA_NODE_PROTECTION:
512 found = ospf_spf_vertex_find(resource->router_id, vertex_list);
513 if (!found)
514 break;
515
516 /*
517 * Remove the node by removing all links from its parents. Note
518 * that the child is automatically removed here with the last
519 * link from a parent, hence no explicit removal of the node.
520 */
521 for (ALL_LIST_ELEMENTS(found->parents, node, nnode,
522 vertex_parent))
523 ospf_spf_remove_branch(vertex_parent, found,
524 vertex_list);
525
526 break;
527 case OSPF_TI_LFA_UNDEFINED_PROTECTION:
528 /* do nothing */
529 break;
530 }
531 }
532
533 static void ospf_spf_init(struct ospf_area *area, struct ospf_lsa *root_lsa,
534 bool is_dry_run, bool is_root_node)
535 {
536 struct list *vertex_list;
537 struct vertex *v;
538
539 /* Create vertex list */
540 vertex_list = list_new();
541 vertex_list->del = ospf_vertex_free;
542 area->spf_vertex_list = vertex_list;
543
544 /* Create root node. */
545 v = ospf_vertex_new(area, root_lsa);
546 area->spf = v;
547
548 area->spf_dry_run = is_dry_run;
549 area->spf_root_node = is_root_node;
550
551 /* Reset ABR and ASBR router counts. */
552 area->abr_count = 0;
553 area->asbr_count = 0;
554 }
555
556 /* return index of link back to V from W, or -1 if no link found */
557 static int ospf_lsa_has_link(struct lsa_header *w, struct lsa_header *v)
558 {
559 unsigned int i, length;
560 struct router_lsa *rl;
561 struct network_lsa *nl;
562
563 /* In case of W is Network LSA. */
564 if (w->type == OSPF_NETWORK_LSA) {
565 if (v->type == OSPF_NETWORK_LSA)
566 return -1;
567
568 nl = (struct network_lsa *)w;
569 length = (ntohs(w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;
570
571 for (i = 0; i < length; i++)
572 if (IPV4_ADDR_SAME(&nl->routers[i], &v->id))
573 return i;
574 return -1;
575 }
576
577 /* In case of W is Router LSA. */
578 if (w->type == OSPF_ROUTER_LSA) {
579 rl = (struct router_lsa *)w;
580
581 length = ntohs(w->length);
582
583 for (i = 0; i < ntohs(rl->links)
584 && length >= sizeof(struct router_lsa);
585 i++, length -= 12) {
586 switch (rl->link[i].type) {
587 case LSA_LINK_TYPE_POINTOPOINT:
588 case LSA_LINK_TYPE_VIRTUALLINK:
589 /* Router LSA ID. */
590 if (v->type == OSPF_ROUTER_LSA
591 && IPV4_ADDR_SAME(&rl->link[i].link_id,
592 &v->id)) {
593 return i;
594 }
595 break;
596 case LSA_LINK_TYPE_TRANSIT:
597 /* Network LSA ID. */
598 if (v->type == OSPF_NETWORK_LSA
599 && IPV4_ADDR_SAME(&rl->link[i].link_id,
600 &v->id)) {
601 return i;
602 }
603 break;
604 case LSA_LINK_TYPE_STUB:
605 /* Stub can't lead anywhere, carry on */
606 continue;
607 default:
608 break;
609 }
610 }
611 }
612 return -1;
613 }
614
615 /*
616 * Find the next link after prev_link from v to w. If prev_link is
617 * NULL, return the first link from v to w. Ignore stub and virtual links;
618 * these link types will never be returned.
619 */
620 static struct router_lsa_link *
621 ospf_get_next_link(struct vertex *v, struct vertex *w,
622 struct router_lsa_link *prev_link)
623 {
624 uint8_t *p;
625 uint8_t *lim;
626 uint8_t lsa_type = LSA_LINK_TYPE_TRANSIT;
627 struct router_lsa_link *l;
628
629 if (w->type == OSPF_VERTEX_ROUTER)
630 lsa_type = LSA_LINK_TYPE_POINTOPOINT;
631
632 if (prev_link == NULL)
633 p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
634 else {
635 p = (uint8_t *)prev_link;
636 p += (OSPF_ROUTER_LSA_LINK_SIZE
637 + (prev_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
638 }
639
640 lim = ((uint8_t *)v->lsa) + ntohs(v->lsa->length);
641
642 while (p < lim) {
643 l = (struct router_lsa_link *)p;
644
645 p += (OSPF_ROUTER_LSA_LINK_SIZE
646 + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
647
648 if (l->m[0].type != lsa_type)
649 continue;
650
651 if (IPV4_ADDR_SAME(&l->link_id, &w->id))
652 return l;
653 }
654
655 return NULL;
656 }
657
658 static void ospf_spf_flush_parents(struct vertex *w)
659 {
660 struct vertex_parent *vp;
661 struct listnode *ln, *nn;
662
663 /* delete the existing nexthops */
664 for (ALL_LIST_ELEMENTS(w->parents, ln, nn, vp)) {
665 list_delete_node(w->parents, ln);
666 vertex_parent_free(vp);
667 }
668 }
669
670 /*
671 * Consider supplied next-hop for inclusion to the supplied list of
672 * equal-cost next-hops, adjust list as necessary.
673 *
674 * Returns vertex parent pointer if created otherwise `NULL` if it already
675 * exists.
676 */
677 static struct vertex_parent *ospf_spf_add_parent(struct vertex *v,
678 struct vertex *w,
679 struct vertex_nexthop *newhop,
680 struct vertex_nexthop *newlhop,
681 unsigned int distance)
682 {
683 struct vertex_parent *vp, *wp;
684 struct listnode *node;
685
686 /* we must have a newhop, and a distance */
687 assert(v && w && newhop);
688 assert(distance);
689
690 /*
691 * IFF w has already been assigned a distance, then we shouldn't get
692 * here unless callers have determined V(l)->W is shortest /
693 * equal-shortest path (0 is a special case distance (no distance yet
694 * assigned)).
695 */
696 if (w->distance)
697 assert(distance <= w->distance);
698 else
699 w->distance = distance;
700
701 if (IS_DEBUG_OSPF_EVENT)
702 zlog_debug("%s: Adding %pI4 as parent of %pI4", __func__,
703 &v->lsa->id, &w->lsa->id);
704
705 /*
706 * Adding parent for a new, better path: flush existing parents from W.
707 */
708 if (distance < w->distance) {
709 if (IS_DEBUG_OSPF_EVENT)
710 zlog_debug(
711 "%s: distance %d better than %d, flushing existing parents",
712 __func__, distance, w->distance);
713 ospf_spf_flush_parents(w);
714 w->distance = distance;
715 }
716
717 /*
718 * new parent is <= existing parents, add it to parent list (if nexthop
719 * not on parent list)
720 */
721 for (ALL_LIST_ELEMENTS_RO(w->parents, node, wp)) {
722 if (memcmp(newhop, wp->nexthop, sizeof(*newhop)) == 0) {
723 if (IS_DEBUG_OSPF_EVENT)
724 zlog_debug(
725 "%s: ... nexthop already on parent list, skipping add",
726 __func__);
727
728 return NULL;
729 }
730 }
731
732 vp = vertex_parent_new(v, ospf_lsa_has_link(w->lsa, v->lsa), newhop,
733 newlhop);
734 listnode_add_sort(w->parents, vp);
735
736 return vp;
737 }
738
739 static int match_stub_prefix(struct lsa_header *lsa, struct in_addr v_link_addr,
740 struct in_addr w_link_addr)
741 {
742 uint8_t *p, *lim;
743 struct router_lsa_link *l = NULL;
744 struct in_addr masked_lsa_addr;
745
746 if (lsa->type != OSPF_ROUTER_LSA)
747 return 0;
748
749 p = ((uint8_t *)lsa) + OSPF_LSA_HEADER_SIZE + 4;
750 lim = ((uint8_t *)lsa) + ntohs(lsa->length);
751
752 while (p < lim) {
753 l = (struct router_lsa_link *)p;
754 p += (OSPF_ROUTER_LSA_LINK_SIZE
755 + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
756
757 if (l->m[0].type != LSA_LINK_TYPE_STUB)
758 continue;
759
760 masked_lsa_addr.s_addr =
761 (l->link_id.s_addr & l->link_data.s_addr);
762
763 /* check that both links belong to the same stub subnet */
764 if ((masked_lsa_addr.s_addr
765 == (v_link_addr.s_addr & l->link_data.s_addr))
766 && (masked_lsa_addr.s_addr
767 == (w_link_addr.s_addr & l->link_data.s_addr)))
768 return 1;
769 }
770
771 return 0;
772 }
773
774 /*
775 * 16.1.1. Calculate nexthop from root through V (parent) to
776 * vertex W (destination), with given distance from root->W.
777 *
778 * The link must be supplied if V is the root vertex. In all other cases
779 * it may be NULL.
780 *
781 * Note that this function may fail, hence the state of the destination
782 * vertex, W, should /not/ be modified in a dependent manner until
783 * this function returns. This function will update the W vertex with the
784 * provided distance as appropriate.
785 */
786 static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
787 struct vertex *v, struct vertex *w,
788 struct router_lsa_link *l,
789 unsigned int distance, int lsa_pos)
790 {
791 struct listnode *node, *nnode;
792 struct vertex_nexthop *nh, *lnh;
793 struct vertex_parent *vp;
794 unsigned int added = 0;
795
796 if (IS_DEBUG_OSPF_EVENT) {
797 zlog_debug("%s: Start", __func__);
798 ospf_vertex_dump("V (parent):", v, 1, 1);
799 ospf_vertex_dump("W (dest) :", w, 1, 1);
800 zlog_debug("V->W distance: %d", distance);
801 }
802
803 if (v == area->spf) {
804 /*
805 * 16.1.1 para 4. In the first case, the parent vertex (V) is
806 * the root (the calculating router itself). This means that
807 * the destination is either a directly connected network or
808 * directly connected router. The outgoing interface in this
809 * case is simply the OSPF interface connecting to the
810 * destination network/router.
811 */
812
813 /* we *must* be supplied with the link data */
814 assert(l != NULL);
815
816 if (IS_DEBUG_OSPF_EVENT)
817 zlog_debug(
818 "%s: considering link type:%d link_id:%pI4 link_data:%pI4",
819 __func__, l->m[0].type, &l->link_id,
820 &l->link_data);
821
822 if (w->type == OSPF_VERTEX_ROUTER) {
823 /*
824 * l is a link from v to w l2 will be link from w to v
825 */
826 struct router_lsa_link *l2 = NULL;
827
828 if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) {
829 struct ospf_interface *oi = NULL;
830 struct in_addr nexthop = {.s_addr = 0};
831
832 if (area->spf_root_node) {
833 oi = ospf_if_lookup_by_lsa_pos(area,
834 lsa_pos);
835 if (!oi) {
836 zlog_debug(
837 "%s: OI not found in LSA: lsa_pos: %d link_id:%pI4 link_data:%pI4",
838 __func__, lsa_pos,
839 &l->link_id,
840 &l->link_data);
841 return 0;
842 }
843 }
844
845 /*
846 * If the destination is a router which connects
847 * to the calculating router via a
848 * Point-to-MultiPoint network, the
849 * destination's next hop IP address(es) can be
850 * determined by examining the destination's
851 * router-LSA: each link pointing back to the
852 * calculating router and having a Link Data
853 * field belonging to the Point-to-MultiPoint
854 * network provides an IP address of the next
855 * hop router.
856 *
857 * At this point l is a link from V to W, and V
858 * is the root ("us"). If it is a point-to-
859 * multipoint interface, then look through the
860 * links in the opposite direction (W to V).
861 * If any of them have an address that lands
862 * within the subnet declared by the PtMP link,
863 * then that link is a constituent of the PtMP
864 * link, and its address is a nexthop address
865 * for V.
866 *
867 * Note for point-to-point interfaces:
868 *
869 * Having nexthop = 0 (as proposed in the RFC)
870 * is tempting, but NOT acceptable. It breaks
871 * AS-External routes with a forwarding address,
872 * since ospf_ase_complete_direct_routes() will
873 * mistakenly assume we've reached the last hop
874 * and should place the forwarding address as
875 * nexthop. Also, users may configure multi-
876 * access links in p2p mode, so we need the IP
877 * to ARP the nexthop.
878 *
879 * If the calculating router is the SPF root
880 * node and the link is P2P then access the
881 * interface information directly. This can be
882 * crucial when e.g. IP unnumbered is used
883 * where 'correct' nexthop information are not
884 * available via Router LSAs.
885 *
886 * Otherwise handle P2P and P2MP the same way
887 * as described above using a reverse lookup to
888 * figure out the nexthop.
889 */
890
891 /*
892 * HACK: we don't know (yet) how to distinguish
893 * between P2P and P2MP interfaces by just
894 * looking at LSAs, which is important for
895 * TI-LFA since you want to do SPF calculations
896 * from the perspective of other nodes. Since
897 * TI-LFA is currently not implemented for P2MP
898 * we just check here if it is enabled and then
899 * blindly assume that P2P is used. Ultimately
900 * the interface code needs to be removed
901 * somehow.
902 */
903 if (area->ospf->ti_lfa_enabled
904 || (oi && oi->type == OSPF_IFTYPE_POINTOPOINT)
905 || (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT
906 && oi->address->prefixlen == IPV4_MAX_BITLEN)) {
907 struct ospf_neighbor *nbr_w = NULL;
908
909 /* Calculating node is root node, link
910 * is P2P */
911 if (area->spf_root_node) {
912 nbr_w = ospf_nbr_lookup_by_routerid(
913 oi->nbrs, &l->link_id);
914 if (nbr_w) {
915 added = 1;
916 nexthop = nbr_w->src;
917 }
918 }
919
920 /* Reverse lookup */
921 if (!added) {
922 while ((l2 = ospf_get_next_link(
923 w, v, l2))) {
924 if (match_stub_prefix(
925 v->lsa,
926 l->link_data,
927 l2->link_data)) {
928 added = 1;
929 nexthop =
930 l2->link_data;
931 break;
932 }
933 }
934 }
935 } else if (oi && oi->type
936 == OSPF_IFTYPE_POINTOMULTIPOINT) {
937 struct prefix_ipv4 la;
938
939 la.family = AF_INET;
940 la.prefixlen = oi->address->prefixlen;
941
942 /*
943 * V links to W on PtMP interface;
944 * find the interface address on W
945 */
946 while ((l2 = ospf_get_next_link(w, v,
947 l2))) {
948 la.prefix = l2->link_data;
949
950 if (prefix_cmp((struct prefix
951 *)&la,
952 oi->address)
953 != 0)
954 continue;
955 added = 1;
956 nexthop = l2->link_data;
957 break;
958 }
959 }
960
961 if (added) {
962 nh = vertex_nexthop_new();
963 nh->router = nexthop;
964 nh->lsa_pos = lsa_pos;
965
966 /*
967 * Since v is the root the nexthop and
968 * local nexthop are the same.
969 */
970 lnh = vertex_nexthop_new();
971 memcpy(lnh, nh,
972 sizeof(struct vertex_nexthop));
973
974 if (ospf_spf_add_parent(v, w, nh, lnh,
975 distance) ==
976 NULL) {
977 vertex_nexthop_free(nh);
978 vertex_nexthop_free(lnh);
979 }
980 return 1;
981 } else
982 zlog_info(
983 "%s: could not determine nexthop for link %s",
984 __func__, oi ? oi->ifp->name : "");
985 } /* end point-to-point link from V to W */
986 else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK) {
987 /*
988 * VLink implementation limitations:
989 * a) vl_data can only reference one nexthop,
990 * so no ECMP to backbone through VLinks.
991 * Though transit-area summaries may be
992 * considered, and those can be ECMP.
993 * b) We can only use /one/ VLink, even if
994 * multiple ones exist this router through
995 * multiple transit-areas.
996 */
997
998 struct ospf_vl_data *vl_data;
999
1000 vl_data = ospf_vl_lookup(area->ospf, NULL,
1001 l->link_id);
1002
1003 if (vl_data
1004 && CHECK_FLAG(vl_data->flags,
1005 OSPF_VL_FLAG_APPROVED)) {
1006 nh = vertex_nexthop_new();
1007 nh->router = vl_data->nexthop.router;
1008 nh->lsa_pos = vl_data->nexthop.lsa_pos;
1009
1010 /*
1011 * Since v is the root the nexthop and
1012 * local nexthop are the same.
1013 */
1014 lnh = vertex_nexthop_new();
1015 memcpy(lnh, nh,
1016 sizeof(struct vertex_nexthop));
1017
1018 if (ospf_spf_add_parent(v, w, nh, lnh,
1019 distance) ==
1020 NULL) {
1021 vertex_nexthop_free(nh);
1022 vertex_nexthop_free(lnh);
1023 }
1024
1025 return 1;
1026 } else
1027 zlog_info(
1028 "%s: vl_data for VL link not found",
1029 __func__);
1030 } /* end virtual-link from V to W */
1031 return 0;
1032 } /* end W is a Router vertex */
1033 else {
1034 assert(w->type == OSPF_VERTEX_NETWORK);
1035
1036 nh = vertex_nexthop_new();
1037 nh->router.s_addr = 0; /* Nexthop not required */
1038 nh->lsa_pos = lsa_pos;
1039
1040 /*
1041 * Since v is the root the nexthop and
1042 * local nexthop are the same.
1043 */
1044 lnh = vertex_nexthop_new();
1045 memcpy(lnh, nh, sizeof(struct vertex_nexthop));
1046
1047 if (ospf_spf_add_parent(v, w, nh, lnh, distance) ==
1048 NULL) {
1049 vertex_nexthop_free(nh);
1050 vertex_nexthop_free(lnh);
1051 }
1052
1053 return 1;
1054 }
1055 } /* end V is the root */
1056 /* Check if W's parent is a network connected to root. */
1057 else if (v->type == OSPF_VERTEX_NETWORK) {
1058 /* See if any of V's parents are the root. */
1059 for (ALL_LIST_ELEMENTS(v->parents, node, nnode, vp)) {
1060 if (vp->parent == area->spf) {
1061 /*
1062 * 16.1.1 para 5. ...the parent vertex is a
1063 * network that directly connects the
1064 * calculating router to the destination
1065 * router. The list of next hops is then
1066 * determined by examining the destination's
1067 * router-LSA ...
1068 */
1069
1070 assert(w->type == OSPF_VERTEX_ROUTER);
1071 while ((l = ospf_get_next_link(w, v, l))) {
1072 /*
1073 * ... For each link in the router-LSA
1074 * that points back to the parent
1075 * network, the link's Link Data field
1076 * provides the IP address of a next hop
1077 * router. The outgoing interface to use
1078 * can then be derived from the next
1079 * hop IP address (or it can be
1080 * inherited from the parent network).
1081 */
1082 nh = vertex_nexthop_new();
1083 nh->router = l->link_data;
1084 nh->lsa_pos = vp->nexthop->lsa_pos;
1085
1086 /*
1087 * Since v is the root the nexthop and
1088 * local nexthop are the same.
1089 */
1090 lnh = vertex_nexthop_new();
1091 memcpy(lnh, nh,
1092 sizeof(struct vertex_nexthop));
1093
1094 added = 1;
1095 if (ospf_spf_add_parent(v, w, nh, lnh,
1096 distance) ==
1097 NULL) {
1098 vertex_nexthop_free(nh);
1099 vertex_nexthop_free(lnh);
1100 }
1101 }
1102 /*
1103 * Note lack of return is deliberate. See next
1104 * comment.
1105 */
1106 }
1107 }
1108 /*
1109 * NB: This code is non-trivial.
1110 *
1111 * E.g. it is not enough to know that V connects to the root. It
1112 * is also important that the while above, looping through all
1113 * links from W->V found at least one link, so that we know
1114 * there is bi-directional connectivity between V and W (which
1115 * need not be the case, e.g. when OSPF has not yet converged
1116 * fully). Otherwise, if we /always/ return here, without having
1117 * checked that root->V->-W actually resulted in a valid nexthop
1118 * being created, then we we will prevent SPF from finding/using
1119 * higher cost paths.
1120 *
1121 * It is important, if root->V->W has not been added, that we
1122 * continue through to the intervening-router nexthop code
1123 * below. So as to ensure other paths to V may be used. This
1124 * avoids unnecessary blackholes while OSPF is converging.
1125 *
1126 * I.e. we may have arrived at this function, examining V -> W,
1127 * via workable paths other than root -> V, and it's important
1128 * to avoid getting "confused" by non-working root->V->W path
1129 * - it's important to *not* lose the working non-root paths,
1130 * just because of a non-viable root->V->W.
1131 */
1132 if (added)
1133 return added;
1134 }
1135
1136 /*
1137 * 16.1.1 para 4. If there is at least one intervening router in the
1138 * current shortest path between the destination and the root, the
1139 * destination simply inherits the set of next hops from the
1140 * parent.
1141 */
1142 if (IS_DEBUG_OSPF_EVENT)
1143 zlog_debug("%s: Intervening routers, adding parent(s)",
1144 __func__);
1145
1146 for (ALL_LIST_ELEMENTS(v->parents, node, nnode, vp)) {
1147 added = 1;
1148
1149 /*
1150 * The nexthop is inherited, but the local nexthop still needs
1151 * to be created.
1152 */
1153 if (l) {
1154 lnh = vertex_nexthop_new();
1155 lnh->router = l->link_data;
1156 lnh->lsa_pos = lsa_pos;
1157 } else {
1158 lnh = NULL;
1159 }
1160
1161 nh = vertex_nexthop_new();
1162 *nh = *vp->nexthop;
1163
1164 if (ospf_spf_add_parent(v, w, nh, lnh, distance) == NULL) {
1165 vertex_nexthop_free(nh);
1166 vertex_nexthop_free(lnh);
1167 }
1168 }
1169
1170 return added;
1171 }
1172
1173 static int ospf_spf_is_protected_resource(struct ospf_area *area,
1174 struct router_lsa_link *link,
1175 struct lsa_header *lsa)
1176 {
1177 uint8_t *p, *lim;
1178 struct router_lsa_link *p_link;
1179 struct router_lsa_link *l = NULL;
1180 struct in_addr router_id;
1181 int link_type;
1182
1183 if (!area->spf_protected_resource)
1184 return 0;
1185
1186 link_type = link->m[0].type;
1187
1188 switch (area->spf_protected_resource->type) {
1189 case OSPF_TI_LFA_LINK_PROTECTION:
1190 p_link = area->spf_protected_resource->link;
1191 if (!p_link)
1192 return 0;
1193
1194 /* For P2P: check if the link belongs to the same subnet */
1195 if (link_type == LSA_LINK_TYPE_POINTOPOINT
1196 && (p_link->link_id.s_addr & p_link->link_data.s_addr)
1197 == (link->link_data.s_addr
1198 & p_link->link_data.s_addr))
1199 return 1;
1200
1201 /* For stub: check if this the same subnet */
1202 if (link_type == LSA_LINK_TYPE_STUB
1203 && (p_link->link_id.s_addr == link->link_id.s_addr)
1204 && (p_link->link_data.s_addr == link->link_data.s_addr))
1205 return 1;
1206
1207 break;
1208 case OSPF_TI_LFA_NODE_PROTECTION:
1209 router_id = area->spf_protected_resource->router_id;
1210 if (router_id.s_addr == INADDR_ANY)
1211 return 0;
1212
1213 /* For P2P: check if the link leads to the protected node */
1214 if (link_type == LSA_LINK_TYPE_POINTOPOINT
1215 && link->link_id.s_addr == router_id.s_addr)
1216 return 1;
1217
1218 /* The rest is about stub links! */
1219 if (link_type != LSA_LINK_TYPE_STUB)
1220 return 0;
1221
1222 /*
1223 * Check if there's a P2P link in the router LSA with the
1224 * corresponding link data in the same subnet.
1225 */
1226
1227 p = ((uint8_t *)lsa) + OSPF_LSA_HEADER_SIZE + 4;
1228 lim = ((uint8_t *)lsa) + ntohs(lsa->length);
1229
1230 while (p < lim) {
1231 l = (struct router_lsa_link *)p;
1232 p += (OSPF_ROUTER_LSA_LINK_SIZE
1233 + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
1234
1235 /* We only care about P2P with the proper link id */
1236 if ((l->m[0].type != LSA_LINK_TYPE_POINTOPOINT)
1237 || (l->link_id.s_addr != router_id.s_addr))
1238 continue;
1239
1240 /* Link data in the subnet given by the link? */
1241 if ((link->link_id.s_addr & link->link_data.s_addr)
1242 == (l->link_data.s_addr & link->link_data.s_addr))
1243 return 1;
1244 }
1245
1246 break;
1247 case OSPF_TI_LFA_UNDEFINED_PROTECTION:
1248 break;
1249 }
1250
1251 return 0;
1252 }
1253
1254 /*
1255 * For TI-LFA we need the reverse SPF for Q spaces. The reverse SPF is created
1256 * by honoring the weight of the reverse 'edge', e.g. the edge from W to V, and
1257 * NOT the weight of the 'edge' from V to W as usual. Hence we need to find the
1258 * corresponding link in the LSA of W and extract the particular weight.
1259 *
1260 * TODO: Only P2P supported by now!
1261 */
1262 static uint16_t get_reverse_distance(struct vertex *v,
1263 struct router_lsa_link *l,
1264 struct ospf_lsa *w_lsa)
1265 {
1266 uint8_t *p, *lim;
1267 struct router_lsa_link *w_link;
1268 uint16_t distance = 0;
1269
1270 assert(w_lsa && w_lsa->data);
1271
1272 p = ((uint8_t *)w_lsa->data) + OSPF_LSA_HEADER_SIZE + 4;
1273 lim = ((uint8_t *)w_lsa->data) + ntohs(w_lsa->data->length);
1274
1275 while (p < lim) {
1276 w_link = (struct router_lsa_link *)p;
1277 p += (OSPF_ROUTER_LSA_LINK_SIZE
1278 + (w_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
1279
1280 /* Only care about P2P with link ID equal to V's router id */
1281 if (w_link->m[0].type == LSA_LINK_TYPE_POINTOPOINT
1282 && w_link->link_id.s_addr == v->id.s_addr) {
1283 distance = ntohs(w_link->m[0].metric);
1284 break;
1285 }
1286 }
1287
1288 /*
1289 * This might happen if the LSA for W is not complete yet. In this
1290 * case we take the weight of the 'forward' link from V. When the LSA
1291 * for W is completed the reverse SPF is run again anyway.
1292 */
1293 if (distance == 0)
1294 distance = ntohs(l->m[0].metric);
1295
1296 if (IS_DEBUG_OSPF_EVENT)
1297 zlog_debug("%s: reversed distance is %u", __func__, distance);
1298
1299 return distance;
1300 }
1301
1302 /*
1303 * RFC2328 16.1 (2).
1304 * v is on the SPF tree. Examine the links in v's LSA. Update the list of
1305 * candidates with any vertices not already on the list. If a lower-cost path
1306 * is found to a vertex already on the candidate list, store the new cost.
1307 */
1308 static void ospf_spf_next(struct vertex *v, struct ospf_area *area,
1309 struct vertex_pqueue_head *candidate)
1310 {
1311 struct ospf_lsa *w_lsa = NULL;
1312 uint8_t *p;
1313 uint8_t *lim;
1314 struct router_lsa_link *l = NULL;
1315 struct in_addr *r;
1316 int type = 0, lsa_pos = -1, lsa_pos_next = 0;
1317 uint16_t link_distance;
1318
1319 /*
1320 * If this is a router-LSA, and bit V of the router-LSA (see Section
1321 * A.4.2:RFC2328) is set, set Area A's TransitCapability to true.
1322 */
1323 if (v->type == OSPF_VERTEX_ROUTER) {
1324 if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa *)v->lsa))
1325 area->transit = OSPF_TRANSIT_TRUE;
1326 }
1327
1328 if (IS_DEBUG_OSPF_EVENT)
1329 zlog_debug("%s: Next vertex of %s vertex %pI4", __func__,
1330 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
1331 &v->lsa->id);
1332
1333 p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
1334 lim = ((uint8_t *)v->lsa) + ntohs(v->lsa->length);
1335
1336 while (p < lim) {
1337 struct vertex *w;
1338 unsigned int distance;
1339
1340 /* In case of V is Router-LSA. */
1341 if (v->lsa->type == OSPF_ROUTER_LSA) {
1342 l = (struct router_lsa_link *)p;
1343
1344 lsa_pos = lsa_pos_next; /* LSA link position */
1345 lsa_pos_next++;
1346
1347 p += (OSPF_ROUTER_LSA_LINK_SIZE
1348 + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
1349
1350 /*
1351 * (a) If this is a link to a stub network, examine the
1352 * next link in V's LSA. Links to stub networks will
1353 * be considered in the second stage of the shortest
1354 * path calculation.
1355 */
1356 if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
1357 continue;
1358
1359 /*
1360 * Don't process TI-LFA protected resources.
1361 *
1362 * TODO: Replace this by a proper solution, e.g. remove
1363 * corresponding links from the LSDB and run the SPF
1364 * algo with the stripped-down LSDB.
1365 */
1366 if (ospf_spf_is_protected_resource(area, l, v->lsa))
1367 continue;
1368
1369 /*
1370 * (b) Otherwise, W is a transit vertex (router or
1371 * transit network). Look up the vertex W's LSA
1372 * (router-LSA or network-LSA) in Area A's link state
1373 * database.
1374 */
1375 switch (type) {
1376 case LSA_LINK_TYPE_POINTOPOINT:
1377 case LSA_LINK_TYPE_VIRTUALLINK:
1378 if (type == LSA_LINK_TYPE_VIRTUALLINK
1379 && IS_DEBUG_OSPF_EVENT)
1380 zlog_debug(
1381 "looking up LSA through VL: %pI4",
1382 &l->link_id);
1383 w_lsa = ospf_lsa_lookup(area->ospf, area,
1384 OSPF_ROUTER_LSA,
1385 l->link_id, l->link_id);
1386 if (w_lsa && IS_DEBUG_OSPF_EVENT)
1387 zlog_debug("found Router LSA %pI4",
1388 &l->link_id);
1389 break;
1390 case LSA_LINK_TYPE_TRANSIT:
1391 if (IS_DEBUG_OSPF_EVENT)
1392 zlog_debug(
1393 "Looking up Network LSA, ID: %pI4",
1394 &l->link_id);
1395 w_lsa = ospf_lsa_lookup_by_id(
1396 area, OSPF_NETWORK_LSA, l->link_id);
1397 if (w_lsa && IS_DEBUG_OSPF_EVENT)
1398 zlog_debug("found the LSA");
1399 break;
1400 default:
1401 flog_warn(EC_OSPF_LSA,
1402 "Invalid LSA link type %d", type);
1403 continue;
1404 }
1405
1406 /*
1407 * For TI-LFA we might need the reverse SPF.
1408 * Currently only works with P2P!
1409 */
1410 if (type == LSA_LINK_TYPE_POINTOPOINT
1411 && area->spf_reversed)
1412 link_distance =
1413 get_reverse_distance(v, l, w_lsa);
1414 else
1415 link_distance = ntohs(l->m[0].metric);
1416
1417 /* step (d) below */
1418 distance = v->distance + link_distance;
1419 } else {
1420 /* In case of V is Network-LSA. */
1421 r = (struct in_addr *)p;
1422 p += sizeof(struct in_addr);
1423
1424 /* Lookup the vertex W's LSA. */
1425 w_lsa = ospf_lsa_lookup_by_id(area, OSPF_ROUTER_LSA,
1426 *r);
1427 if (w_lsa && IS_DEBUG_OSPF_EVENT)
1428 zlog_debug("found Router LSA %pI4",
1429 &w_lsa->data->id);
1430
1431 /* step (d) below */
1432 distance = v->distance;
1433 }
1434
1435 /*
1436 * (b cont.) If the LSA does not exist, or its LS age is equal
1437 * to MaxAge, or it does not have a link back to vertex V,
1438 * examine the next link in V's LSA.[23]
1439 */
1440 if (w_lsa == NULL) {
1441 if (IS_DEBUG_OSPF_EVENT)
1442 zlog_debug("No LSA found");
1443 continue;
1444 }
1445
1446 if (IS_LSA_MAXAGE(w_lsa)) {
1447 if (IS_DEBUG_OSPF_EVENT)
1448 zlog_debug("LSA is MaxAge");
1449 continue;
1450 }
1451
1452 if (ospf_lsa_has_link(w_lsa->data, v->lsa) < 0) {
1453 if (IS_DEBUG_OSPF_EVENT)
1454 zlog_debug("The LSA doesn't have a link back");
1455 continue;
1456 }
1457
1458 /*
1459 * (c) If vertex W is already on the shortest-path tree, examine
1460 * the next link in the LSA.
1461 */
1462 if (w_lsa->stat == LSA_SPF_IN_SPFTREE) {
1463 if (IS_DEBUG_OSPF_EVENT)
1464 zlog_debug("The LSA is already in SPF");
1465 continue;
1466 }
1467
1468 /*
1469 * (d) Calculate the link state cost D of the resulting path
1470 * from the root to vertex W. D is equal to the sum of the link
1471 * state cost of the (already calculated) shortest path to
1472 * vertex V and the advertised cost of the link between vertices
1473 * V and W. If D is:
1474 */
1475
1476 /* calculate link cost D -- moved above */
1477
1478 /* Is there already vertex W in candidate list? */
1479 if (w_lsa->stat == LSA_SPF_NOT_EXPLORED) {
1480 /* prepare vertex W. */
1481 w = ospf_vertex_new(area, w_lsa);
1482
1483 /* Calculate nexthop to W. */
1484 if (ospf_nexthop_calculation(area, v, w, l, distance,
1485 lsa_pos))
1486 vertex_pqueue_add(candidate, w);
1487 else {
1488 listnode_delete(area->spf_vertex_list, w);
1489 ospf_vertex_free(w);
1490 w_lsa->stat = LSA_SPF_NOT_EXPLORED;
1491 if (IS_DEBUG_OSPF_EVENT)
1492 zlog_debug("Nexthop Calc failed");
1493 }
1494 } else if (w_lsa->stat != LSA_SPF_IN_SPFTREE) {
1495 w = w_lsa->stat;
1496 if (w->distance < distance) {
1497 continue;
1498 }
1499 else if (w->distance == distance) {
1500 /*
1501 * Found an equal-cost path to W.
1502 * Calculate nexthop of to W from V.
1503 */
1504 ospf_nexthop_calculation(area, v, w, l,
1505 distance, lsa_pos);
1506 }
1507 else {
1508 /*
1509 * Found a lower-cost path to W.
1510 * nexthop_calculation is conditional, if it
1511 * finds valid nexthop it will call
1512 * spf_add_parents, which will flush the old
1513 * parents.
1514 */
1515 vertex_pqueue_del(candidate, w);
1516 ospf_nexthop_calculation(area, v, w, l,
1517 distance, lsa_pos);
1518 vertex_pqueue_add(candidate, w);
1519 }
1520 } /* end W is already on the candidate list */
1521 } /* end loop over the links in V's LSA */
1522 }
1523
1524 static void ospf_spf_dump(struct vertex *v, int i)
1525 {
1526 struct listnode *cnode;
1527 struct listnode *nnode;
1528 struct vertex_parent *parent;
1529
1530 if (v->type == OSPF_VERTEX_ROUTER) {
1531 if (IS_DEBUG_OSPF_EVENT)
1532 zlog_debug("SPF Result: %d [R] %pI4", i,
1533 &v->lsa->id);
1534 } else {
1535 struct network_lsa *lsa = (struct network_lsa *)v->lsa;
1536 if (IS_DEBUG_OSPF_EVENT)
1537 zlog_debug("SPF Result: %d [N] %pI4/%d", i,
1538 &v->lsa->id,
1539 ip_masklen(lsa->mask));
1540 }
1541
1542 if (IS_DEBUG_OSPF_EVENT)
1543 for (ALL_LIST_ELEMENTS_RO(v->parents, nnode, parent)) {
1544 zlog_debug(" nexthop %p %pI4 %d",
1545 (void *)parent->nexthop,
1546 &parent->nexthop->router,
1547 parent->nexthop->lsa_pos);
1548 }
1549
1550 i++;
1551
1552 for (ALL_LIST_ELEMENTS_RO(v->children, cnode, v))
1553 ospf_spf_dump(v, i);
1554 }
1555
1556 void ospf_spf_print(struct vty *vty, struct vertex *v, int i)
1557 {
1558 struct listnode *cnode;
1559 struct listnode *nnode;
1560 struct vertex_parent *parent;
1561
1562 if (v->type == OSPF_VERTEX_ROUTER) {
1563 vty_out(vty, "SPF Result: depth %d [R] %pI4\n", i, &v->lsa->id);
1564 } else {
1565 struct network_lsa *lsa = (struct network_lsa *)v->lsa;
1566 vty_out(vty, "SPF Result: depth %d [N] %pI4/%d\n", i,
1567 &v->lsa->id, ip_masklen(lsa->mask));
1568 }
1569
1570 for (ALL_LIST_ELEMENTS_RO(v->parents, nnode, parent)) {
1571 vty_out(vty,
1572 " nexthop %pI4 lsa pos %d -- local nexthop %pI4 lsa pos %d\n",
1573 &parent->nexthop->router, parent->nexthop->lsa_pos,
1574 &parent->local_nexthop->router,
1575 parent->local_nexthop->lsa_pos);
1576 }
1577
1578 i++;
1579
1580 for (ALL_LIST_ELEMENTS_RO(v->children, cnode, v))
1581 ospf_spf_print(vty, v, i);
1582 }
1583
1584 /* Second stage of SPF calculation. */
1585 static void ospf_spf_process_stubs(struct ospf_area *area, struct vertex *v,
1586 struct route_table *rt, int parent_is_root)
1587 {
1588 struct listnode *cnode, *cnnode;
1589 struct vertex *child;
1590
1591 if (IS_DEBUG_OSPF_EVENT)
1592 zlog_debug("%s: processing stubs for area %pI4", __func__,
1593 &area->area_id);
1594
1595 if (v->type == OSPF_VERTEX_ROUTER) {
1596 uint8_t *p;
1597 uint8_t *lim;
1598 struct router_lsa_link *l;
1599 struct router_lsa *router_lsa;
1600 int lsa_pos = 0;
1601
1602 if (IS_DEBUG_OSPF_EVENT)
1603 zlog_debug("%s: processing router LSA, id: %pI4",
1604 __func__, &v->lsa->id);
1605
1606 router_lsa = (struct router_lsa *)v->lsa;
1607
1608 if (IS_DEBUG_OSPF_EVENT)
1609 zlog_debug("%s: we have %d links to process", __func__,
1610 ntohs(router_lsa->links));
1611
1612 p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
1613 lim = ((uint8_t *)v->lsa) + ntohs(v->lsa->length);
1614
1615 while (p < lim) {
1616 l = (struct router_lsa_link *)p;
1617
1618 p += (OSPF_ROUTER_LSA_LINK_SIZE
1619 + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
1620
1621 /* Don't process TI-LFA protected resources */
1622 if (l->m[0].type == LSA_LINK_TYPE_STUB
1623 && !ospf_spf_is_protected_resource(area, l, v->lsa))
1624 ospf_intra_add_stub(rt, l, v, area,
1625 parent_is_root, lsa_pos);
1626 lsa_pos++;
1627 }
1628 }
1629
1630 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1,
1631 1);
1632
1633 for (ALL_LIST_ELEMENTS(v->children, cnode, cnnode, child)) {
1634 if (CHECK_FLAG(child->flags, OSPF_VERTEX_PROCESSED))
1635 continue;
1636
1637 /*
1638 * The first level of routers connected to the root
1639 * should have 'parent_is_root' set, including those
1640 * connected via a network vertex.
1641 */
1642 if (area->spf == v)
1643 parent_is_root = 1;
1644 else if (v->type == OSPF_VERTEX_ROUTER)
1645 parent_is_root = 0;
1646
1647 ospf_spf_process_stubs(area, child, rt, parent_is_root);
1648
1649 SET_FLAG(child->flags, OSPF_VERTEX_PROCESSED);
1650 }
1651 }
1652
1653 void ospf_rtrs_free(struct route_table *rtrs)
1654 {
1655 struct route_node *rn;
1656 struct list *or_list;
1657 struct ospf_route * or ;
1658 struct listnode *node, *nnode;
1659
1660 if (IS_DEBUG_OSPF_EVENT)
1661 zlog_debug("Route: Router Routing Table free");
1662
1663 for (rn = route_top(rtrs); rn; rn = route_next(rn))
1664 if ((or_list = rn->info) != NULL) {
1665 for (ALL_LIST_ELEMENTS(or_list, node, nnode, or))
1666 ospf_route_free(or);
1667
1668 list_delete(&or_list);
1669
1670 /* Unlock the node. */
1671 rn->info = NULL;
1672 route_unlock_node(rn);
1673 }
1674
1675 route_table_finish(rtrs);
1676 }
1677
1678 void ospf_spf_cleanup(struct vertex *spf, struct list *vertex_list)
1679 {
1680 /*
1681 * Free nexthop information, canonical versions of which are
1682 * attached the first level of router vertices attached to the
1683 * root vertex, see ospf_nexthop_calculation.
1684 */
1685 if (spf)
1686 ospf_canonical_nexthops_free(spf);
1687
1688 /* Free SPF vertices list with deconstructor ospf_vertex_free. */
1689 if (vertex_list)
1690 list_delete(&vertex_list);
1691 }
1692
1693 /* Calculating the shortest-path tree for an area, see RFC2328 16.1. */
1694 void ospf_spf_calculate(struct ospf_area *area, struct ospf_lsa *root_lsa,
1695 struct route_table *new_table,
1696 struct route_table *all_rtrs,
1697 struct route_table *new_rtrs, bool is_dry_run,
1698 bool is_root_node)
1699 {
1700 struct vertex_pqueue_head candidate;
1701 struct vertex *v;
1702
1703 if (IS_DEBUG_OSPF_EVENT) {
1704 zlog_debug("%s: Start: running Dijkstra for area %pI4",
1705 __func__, &area->area_id);
1706 }
1707
1708 /*
1709 * If the router LSA of the root is not yet allocated, return this
1710 * area's calculation. In the 'usual' case the root_lsa is the
1711 * self-originated router LSA of the node itself.
1712 */
1713 if (!root_lsa) {
1714 if (IS_DEBUG_OSPF_EVENT)
1715 zlog_debug(
1716 "%s: Skip area %pI4's calculation due to empty root LSA",
1717 __func__, &area->area_id);
1718 return;
1719 }
1720
1721 /* Initialize the algorithm's data structures, see RFC2328 16.1. (1). */
1722
1723 /*
1724 * This function scans all the LSA database and set the stat field to
1725 * LSA_SPF_NOT_EXPLORED.
1726 */
1727 lsdb_clean_stat(area->lsdb);
1728
1729 /* Create a new heap for the candidates. */
1730 vertex_pqueue_init(&candidate);
1731
1732 /*
1733 * Initialize the shortest-path tree to only the root (which is usually
1734 * the router doing the calculation).
1735 */
1736 ospf_spf_init(area, root_lsa, is_dry_run, is_root_node);
1737
1738 /* Set Area A's TransitCapability to false. */
1739 area->transit = OSPF_TRANSIT_FALSE;
1740 area->shortcut_capability = 1;
1741
1742 /*
1743 * Use the root vertex for the start of the SPF algorithm and make it
1744 * part of the tree.
1745 */
1746 v = area->spf;
1747 v->lsa_p->stat = LSA_SPF_IN_SPFTREE;
1748
1749 for (;;) {
1750 /* RFC2328 16.1. (2). */
1751 ospf_spf_next(v, area, &candidate);
1752
1753 /* RFC2328 16.1. (3). */
1754 v = vertex_pqueue_pop(&candidate);
1755 if (!v)
1756 /* No more vertices left. */
1757 break;
1758
1759 v->lsa_p->stat = LSA_SPF_IN_SPFTREE;
1760
1761 ospf_vertex_add_parent(v);
1762
1763 /* RFC2328 16.1. (4). */
1764 if (v->type != OSPF_VERTEX_ROUTER)
1765 ospf_intra_add_transit(new_table, v, area);
1766 else {
1767 if (new_rtrs)
1768 ospf_intra_add_router(new_rtrs, v, area, false);
1769 if (all_rtrs)
1770 ospf_intra_add_router(all_rtrs, v, area, true);
1771 }
1772
1773 /* Iterate back to (2), see RFC2328 16.1. (5). */
1774 }
1775
1776 if (IS_DEBUG_OSPF_EVENT) {
1777 ospf_spf_dump(area->spf, 0);
1778 ospf_route_table_dump(new_table);
1779 if (all_rtrs)
1780 ospf_router_route_table_dump(all_rtrs);
1781 }
1782
1783 /*
1784 * Second stage of SPF calculation procedure's, add leaves to the tree
1785 * for stub networks.
1786 */
1787 ospf_spf_process_stubs(area, area->spf, new_table, 0);
1788
1789 ospf_vertex_dump(__func__, area->spf, 0, 1);
1790
1791 /* Increment SPF Calculation Counter. */
1792 area->spf_calculation++;
1793
1794 monotime(&area->ospf->ts_spf);
1795 area->ts_spf = area->ospf->ts_spf;
1796
1797 if (IS_DEBUG_OSPF_EVENT)
1798 zlog_debug("%s: Stop. %zd vertices", __func__,
1799 mtype_stats_alloc(MTYPE_OSPF_VERTEX));
1800 }
1801
1802 void ospf_spf_calculate_area(struct ospf *ospf, struct ospf_area *area,
1803 struct route_table *new_table,
1804 struct route_table *all_rtrs,
1805 struct route_table *new_rtrs)
1806 {
1807 ospf_spf_calculate(area, area->router_lsa_self, new_table, all_rtrs,
1808 new_rtrs, false, true);
1809
1810 if (ospf->ti_lfa_enabled)
1811 ospf_ti_lfa_compute(area, new_table,
1812 ospf->ti_lfa_protection_type);
1813
1814 ospf_spf_cleanup(area->spf, area->spf_vertex_list);
1815
1816 area->spf = NULL;
1817 area->spf_vertex_list = NULL;
1818 }
1819
1820 void ospf_spf_calculate_areas(struct ospf *ospf, struct route_table *new_table,
1821 struct route_table *all_rtrs,
1822 struct route_table *new_rtrs)
1823 {
1824 struct ospf_area *area;
1825 struct listnode *node, *nnode;
1826
1827 /* Calculate SPF for each area. */
1828 for (ALL_LIST_ELEMENTS(ospf->areas, node, nnode, area)) {
1829 /* Do backbone last, so as to first discover intra-area paths
1830 * for any back-bone virtual-links */
1831 if (ospf->backbone && ospf->backbone == area)
1832 continue;
1833
1834 ospf_spf_calculate_area(ospf, area, new_table, all_rtrs,
1835 new_rtrs);
1836 }
1837
1838 /* SPF for backbone, if required */
1839 if (ospf->backbone)
1840 ospf_spf_calculate_area(ospf, ospf->backbone, new_table,
1841 all_rtrs, new_rtrs);
1842 }
1843
1844 /* Worker for SPF calculation scheduler. */
1845 static void ospf_spf_calculate_schedule_worker(struct event *thread)
1846 {
1847 struct ospf *ospf = EVENT_ARG(thread);
1848 struct route_table *new_table, *new_rtrs;
1849 struct route_table *all_rtrs = NULL;
1850 struct timeval start_time, spf_start_time;
1851 unsigned long ia_time, prune_time, rt_time;
1852 unsigned long abr_time, total_spf_time, spf_time;
1853 char rbuf[32]; /* reason_buf */
1854
1855 if (IS_DEBUG_OSPF_EVENT)
1856 zlog_debug("SPF: Timer (SPF calculation expire)");
1857
1858 ospf->t_spf_calc = NULL;
1859
1860 ospf_vl_unapprove(ospf);
1861
1862 /* Execute SPF for each area including backbone, see RFC 2328 16.1. */
1863 monotime(&spf_start_time);
1864 new_table = route_table_init(); /* routing table */
1865 new_rtrs = route_table_init(); /* ABR/ASBR routing table */
1866
1867 /* If we have opaque enabled then track all router reachability */
1868 if (CHECK_FLAG(ospf->opaque, OPAQUE_OPERATION_READY_BIT))
1869 all_rtrs = route_table_init();
1870
1871 ospf_spf_calculate_areas(ospf, new_table, all_rtrs, new_rtrs);
1872 spf_time = monotime_since(&spf_start_time, NULL);
1873
1874 ospf_vl_shut_unapproved(ospf);
1875
1876 /* Calculate inter-area routes, see RFC 2328 16.2. */
1877 monotime(&start_time);
1878 ospf_ia_routing(ospf, new_table, new_rtrs);
1879 ia_time = monotime_since(&start_time, NULL);
1880
1881 /* Get rid of transit networks and routers we cannot reach anyway. */
1882 monotime(&start_time);
1883 ospf_prune_unreachable_networks(new_table);
1884 if (all_rtrs)
1885 ospf_prune_unreachable_routers(all_rtrs);
1886 ospf_prune_unreachable_routers(new_rtrs);
1887 prune_time = monotime_since(&start_time, NULL);
1888
1889 /* Note: RFC 2328 16.3. is apparently missing. */
1890
1891 /*
1892 * Calculate AS external routes, see RFC 2328 16.4.
1893 * There is a dedicated routing table for external routes which is not
1894 * handled here directly
1895 */
1896 ospf_ase_calculate_schedule(ospf);
1897 ospf_ase_calculate_timer_add(ospf);
1898
1899 if (IS_DEBUG_OSPF_EVENT)
1900 zlog_debug(
1901 "%s: ospf install new route, vrf %s id %u new_table count %lu",
1902 __func__, ospf_vrf_id_to_name(ospf->vrf_id),
1903 ospf->vrf_id, new_table->count);
1904
1905 /* Update routing table. */
1906 monotime(&start_time);
1907 ospf_route_install(ospf, new_table);
1908 rt_time = monotime_since(&start_time, NULL);
1909
1910 /* Free old all routers routing table */
1911 if (ospf->oall_rtrs) {
1912 ospf_rtrs_free(ospf->oall_rtrs);
1913 ospf->oall_rtrs = NULL;
1914 }
1915
1916 /* Update all routers routing table */
1917 ospf->oall_rtrs = ospf->all_rtrs;
1918 ospf->all_rtrs = all_rtrs;
1919 #ifdef SUPPORT_OSPF_API
1920 ospf_apiserver_notify_reachable(ospf->oall_rtrs, ospf->all_rtrs);
1921 #endif
1922
1923 /* Free old ABR/ASBR routing table */
1924 if (ospf->old_rtrs) {
1925 ospf_rtrs_free(ospf->old_rtrs);
1926 ospf->old_rtrs = NULL;
1927 }
1928
1929 /* Update ABR/ASBR routing table */
1930 ospf->old_rtrs = ospf->new_rtrs;
1931 ospf->new_rtrs = new_rtrs;
1932
1933 /* ABRs may require additional changes, see RFC 2328 16.7. */
1934 monotime(&start_time);
1935 if (IS_OSPF_ABR(ospf)) {
1936 if (ospf->anyNSSA)
1937 ospf_abr_nssa_check_status(ospf);
1938 ospf_abr_task(ospf);
1939 }
1940 abr_time = monotime_since(&start_time, NULL);
1941
1942 /* Schedule Segment Routing update */
1943 ospf_sr_update_task(ospf);
1944
1945 total_spf_time =
1946 monotime_since(&spf_start_time, &ospf->ts_spf_duration);
1947
1948 rbuf[0] = '\0';
1949 if (spf_reason_flags) {
1950 if (spf_reason_flags & (1 << SPF_FLAG_ROUTER_LSA_INSTALL))
1951 strlcat(rbuf, "R, ", sizeof(rbuf));
1952 if (spf_reason_flags & (1 << SPF_FLAG_NETWORK_LSA_INSTALL))
1953 strlcat(rbuf, "N, ", sizeof(rbuf));
1954 if (spf_reason_flags & (1 << SPF_FLAG_SUMMARY_LSA_INSTALL))
1955 strlcat(rbuf, "S, ", sizeof(rbuf));
1956 if (spf_reason_flags & (1 << SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL))
1957 strlcat(rbuf, "AS, ", sizeof(rbuf));
1958 if (spf_reason_flags & (1 << SPF_FLAG_ABR_STATUS_CHANGE))
1959 strlcat(rbuf, "ABR, ", sizeof(rbuf));
1960 if (spf_reason_flags & (1 << SPF_FLAG_ASBR_STATUS_CHANGE))
1961 strlcat(rbuf, "ASBR, ", sizeof(rbuf));
1962 if (spf_reason_flags & (1 << SPF_FLAG_MAXAGE))
1963 strlcat(rbuf, "M, ", sizeof(rbuf));
1964 if (spf_reason_flags & (1 << SPF_FLAG_GR_FINISH))
1965 strlcat(rbuf, "GR, ", sizeof(rbuf));
1966
1967 size_t rbuflen = strlen(rbuf);
1968 if (rbuflen >= 2)
1969 rbuf[rbuflen - 2] = '\0'; /* skip the last ", " */
1970 else
1971 rbuf[0] = '\0';
1972 }
1973
1974 if (IS_DEBUG_OSPF_EVENT) {
1975 zlog_info("SPF Processing Time(usecs): %ld", total_spf_time);
1976 zlog_info(" SPF Time: %ld", spf_time);
1977 zlog_info(" InterArea: %ld", ia_time);
1978 zlog_info(" Prune: %ld", prune_time);
1979 zlog_info(" RouteInstall: %ld", rt_time);
1980 if (IS_OSPF_ABR(ospf))
1981 zlog_info(" ABR: %ld (%d areas)",
1982 abr_time, ospf->areas->count);
1983 zlog_info("Reason(s) for SPF: %s", rbuf);
1984 }
1985
1986 ospf_clear_spf_reason_flags();
1987 }
1988
1989 /*
1990 * Add schedule for SPF calculation. To avoid frequenst SPF calc, we set timer
1991 * for SPF calc.
1992 */
1993 void ospf_spf_calculate_schedule(struct ospf *ospf, ospf_spf_reason_t reason)
1994 {
1995 unsigned long delay, elapsed, ht;
1996
1997 if (IS_DEBUG_OSPF_EVENT)
1998 zlog_debug("SPF: calculation timer scheduled");
1999
2000 /* OSPF instance does not exist. */
2001 if (ospf == NULL)
2002 return;
2003
2004 ospf_spf_set_reason(reason);
2005
2006 /* SPF calculation timer is already scheduled. */
2007 if (ospf->t_spf_calc) {
2008 if (IS_DEBUG_OSPF_EVENT)
2009 zlog_debug(
2010 "SPF: calculation timer is already scheduled: %p",
2011 (void *)ospf->t_spf_calc);
2012 return;
2013 }
2014
2015 elapsed = monotime_since(&ospf->ts_spf, NULL) / 1000;
2016
2017 ht = ospf->spf_holdtime * ospf->spf_hold_multiplier;
2018
2019 if (ht > ospf->spf_max_holdtime)
2020 ht = ospf->spf_max_holdtime;
2021
2022 /* Get SPF calculation delay time. */
2023 if (elapsed < ht) {
2024 /*
2025 * Got an event within the hold time of last SPF. We need to
2026 * increase the hold_multiplier, if it's not already at/past
2027 * maximum value, and wasn't already increased.
2028 */
2029 if (ht < ospf->spf_max_holdtime)
2030 ospf->spf_hold_multiplier++;
2031
2032 /* always honour the SPF initial delay */
2033 if ((ht - elapsed) < ospf->spf_delay)
2034 delay = ospf->spf_delay;
2035 else
2036 delay = ht - elapsed;
2037 } else {
2038 /* Event is past required hold-time of last SPF */
2039 delay = ospf->spf_delay;
2040 ospf->spf_hold_multiplier = 1;
2041 }
2042
2043 if (IS_DEBUG_OSPF_EVENT)
2044 zlog_debug("SPF: calculation timer delay = %ld msec", delay);
2045
2046 ospf->t_spf_calc = NULL;
2047 event_add_timer_msec(master, ospf_spf_calculate_schedule_worker, ospf,
2048 delay, &ospf->t_spf_calc);
2049 }
2050
2051 /* Restart OSPF SPF algorithm*/
2052 void ospf_restart_spf(struct ospf *ospf)
2053 {
2054 if (IS_DEBUG_OSPF_EVENT)
2055 zlog_debug("%s: Restart SPF.", __func__);
2056
2057 /* Handling inter area and intra area routes*/
2058 if (ospf->new_table) {
2059 ospf_route_delete(ospf, ospf->new_table);
2060 ospf_route_table_free(ospf->new_table);
2061 ospf->new_table = route_table_init();
2062 }
2063
2064 /* Handling of TYPE-5 lsa(external routes) */
2065 if (ospf->old_external_route) {
2066 ospf_route_delete(ospf, ospf->old_external_route);
2067 ospf_route_table_free(ospf->old_external_route);
2068 ospf->old_external_route = route_table_init();
2069 }
2070
2071 /* Trigger SPF */
2072 ospf_spf_calculate_schedule(ospf, SPF_FLAG_CONFIG_CHANGE);
2073 }
FRRouting mirror