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