]> 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
*: s/TRUE/true/, s/FALSE/false/
[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_errors.h"
50
51 /* Variables to ensure a SPF scheduled log message is printed only once */
52
53 static unsigned int spf_reason_flags = 0;
54
55 /* dummy vertex to flag "in spftree" */
56 static const struct vertex vertex_in_spftree = {};
57 #define LSA_SPF_IN_SPFTREE (struct vertex *)&vertex_in_spftree
58 #define LSA_SPF_NOT_EXPLORED NULL
59
60 static void ospf_clear_spf_reason_flags(void)
61 {
62 spf_reason_flags = 0;
63 }
64
65 static void ospf_spf_set_reason(ospf_spf_reason_t reason)
66 {
67 spf_reason_flags |= 1 << reason;
68 }
69
70 static void ospf_vertex_free(void *);
71 /* List of allocated vertices, to simplify cleanup of SPF.
72 * Not thread-safe obviously. If it ever needs to be, it'd have to be
73 * dynamically allocated at begin of ospf_spf_calculate
74 */
75 static struct list vertex_list = {.del = ospf_vertex_free};
76
77 /* Heap related functions, for the managment of the candidates, to
78 * be used with pqueue. */
79 static int vertex_cmp(const struct vertex *v1, const struct vertex *v2)
80 {
81 if (v1->distance != v2->distance)
82 return v1->distance - v2->distance;
83
84 if (v1->type != v2->type) {
85 switch (v1->type) {
86 case OSPF_VERTEX_NETWORK:
87 return -1;
88 case OSPF_VERTEX_ROUTER:
89 return 1;
90 }
91 }
92 return 0;
93 }
94 DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue, struct vertex, pqi, vertex_cmp)
95
96 static void lsdb_clean_stat(struct ospf_lsdb *lsdb)
97 {
98 struct route_table *table;
99 struct route_node *rn;
100 struct ospf_lsa *lsa;
101 int i;
102
103 for (i = OSPF_MIN_LSA; i < OSPF_MAX_LSA; i++) {
104 table = lsdb->type[i].db;
105 for (rn = route_top(table); rn; rn = route_next(rn))
106 if ((lsa = (rn->info)) != NULL)
107 lsa->stat = LSA_SPF_NOT_EXPLORED;
108 }
109 }
110
111 static struct vertex_nexthop *vertex_nexthop_new(void)
112 {
113 return XCALLOC(MTYPE_OSPF_NEXTHOP, sizeof(struct vertex_nexthop));
114 }
115
116 static void vertex_nexthop_free(struct vertex_nexthop *nh)
117 {
118 XFREE(MTYPE_OSPF_NEXTHOP, nh);
119 }
120
121 /* Free the canonical nexthop objects for an area, ie the nexthop objects
122 * attached to the first-hop router vertices, and any intervening network
123 * vertices.
124 */
125 static void ospf_canonical_nexthops_free(struct vertex *root)
126 {
127 struct listnode *node, *nnode;
128 struct vertex *child;
129
130 for (ALL_LIST_ELEMENTS(root->children, node, nnode, child)) {
131 struct listnode *n2, *nn2;
132 struct vertex_parent *vp;
133
134 /* router vertices through an attached network each
135 * have a distinct (canonical / not inherited) nexthop
136 * which must be freed.
137 *
138 * A network vertex can only have router vertices as its
139 * children, so only one level of recursion is possible.
140 */
141 if (child->type == OSPF_VERTEX_NETWORK)
142 ospf_canonical_nexthops_free(child);
143
144 /* Free child nexthops pointing back to this root vertex */
145 for (ALL_LIST_ELEMENTS(child->parents, n2, nn2, vp))
146 if (vp->parent == root && vp->nexthop) {
147 vertex_nexthop_free(vp->nexthop);
148 vp->nexthop = NULL;
149 }
150 }
151 }
152
153 /* TODO: Parent list should be excised, in favour of maintaining only
154 * vertex_nexthop, with refcounts.
155 */
156 static struct vertex_parent *vertex_parent_new(struct vertex *v, int backlink,
157 struct vertex_nexthop *hop)
158 {
159 struct vertex_parent *new;
160
161 new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT, sizeof(struct vertex_parent));
162
163 new->parent = v;
164 new->backlink = backlink;
165 new->nexthop = hop;
166 return new;
167 }
168
169 static void vertex_parent_free(void *p)
170 {
171 XFREE(MTYPE_OSPF_VERTEX_PARENT, p);
172 }
173
174 static 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_lsa *lsa)
181 {
182 struct vertex *new;
183
184 new = XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex));
185
186 new->flags = 0;
187 new->type = lsa->data->type;
188 new->id = lsa->data->id;
189 new->lsa = lsa->data;
190 new->children = list_new();
191 new->parents = list_new();
192 new->parents->del = vertex_parent_free;
193 new->parents->cmp = vertex_parent_cmp;
194 new->lsa_p = lsa;
195
196 lsa->stat = new;
197
198 listnode_add(&vertex_list, new);
199
200 if (IS_DEBUG_OSPF_EVENT)
201 zlog_debug("%s: Created %s vertex %s", __func__,
202 new->type == OSPF_VERTEX_ROUTER ? "Router"
203 : "Network",
204 inet_ntoa(new->lsa->id));
205 return new;
206 }
207
208 static void ospf_vertex_free(void *data)
209 {
210 struct vertex *v = data;
211
212 if (IS_DEBUG_OSPF_EVENT)
213 zlog_debug("%s: Free %s vertex %s", __func__,
214 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
215 inet_ntoa(v->lsa->id));
216
217 /* There should be no parents potentially holding references to this
218 * vertex
219 * Children however may still be there, but presumably referenced by
220 * other
221 * vertices
222 */
223 // assert (listcount (v->parents) == 0);
224
225 if (v->children)
226 list_delete(&v->children);
227
228 if (v->parents)
229 list_delete(&v->parents);
230
231 v->lsa = NULL;
232
233 XFREE(MTYPE_OSPF_VERTEX, v);
234 }
235
236 static void ospf_vertex_dump(const char *msg, struct vertex *v,
237 int print_parents, int print_children)
238 {
239 if (!IS_DEBUG_OSPF_EVENT)
240 return;
241
242 zlog_debug("%s %s vertex %s distance %u flags %u", msg,
243 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
244 inet_ntoa(v->lsa->id), v->distance, (unsigned int)v->flags);
245
246 if (print_parents) {
247 struct listnode *node;
248 struct vertex_parent *vp;
249
250 for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) {
251 char buf1[BUFSIZ];
252
253 if (vp) {
254 zlog_debug(
255 "parent %s backlink %d nexthop %s interface %s",
256 inet_ntoa(vp->parent->lsa->id),
257 vp->backlink,
258 inet_ntop(AF_INET, &vp->nexthop->router,
259 buf1, BUFSIZ),
260 vp->nexthop->oi
261 ? IF_NAME(vp->nexthop->oi)
262 : "NULL");
263 }
264 }
265 }
266
267 if (print_children) {
268 struct listnode *cnode;
269 struct vertex *cv;
270
271 for (ALL_LIST_ELEMENTS_RO(v->children, cnode, cv))
272 ospf_vertex_dump(" child:", cv, 0, 0);
273 }
274 }
275
276
277 /* Add a vertex to the list of children in each of its parents. */
278 static void ospf_vertex_add_parent(struct vertex *v)
279 {
280 struct vertex_parent *vp;
281 struct listnode *node;
282
283 assert(v && v->parents);
284
285 for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) {
286 assert(vp->parent && vp->parent->children);
287
288 /* No need to add two links from the same parent. */
289 if (listnode_lookup(vp->parent->children, v) == NULL)
290 listnode_add(vp->parent->children, v);
291 }
292 }
293
294 static void ospf_spf_init(struct ospf_area *area)
295 {
296 struct vertex *v;
297
298 /* Create root node. */
299 v = ospf_vertex_new(area->router_lsa_self);
300
301 area->spf = v;
302
303 /* Reset ABR and ASBR router counts. */
304 area->abr_count = 0;
305 area->asbr_count = 0;
306 }
307
308 /* return index of link back to V from W, or -1 if no link found */
309 static int ospf_lsa_has_link(struct lsa_header *w, struct lsa_header *v)
310 {
311 unsigned int i, length;
312 struct router_lsa *rl;
313 struct network_lsa *nl;
314
315 /* In case of W is Network LSA. */
316 if (w->type == OSPF_NETWORK_LSA) {
317 if (v->type == OSPF_NETWORK_LSA)
318 return -1;
319
320 nl = (struct network_lsa *)w;
321 length = (ntohs(w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;
322
323 for (i = 0; i < length; i++)
324 if (IPV4_ADDR_SAME(&nl->routers[i], &v->id))
325 return i;
326 return -1;
327 }
328
329 /* In case of W is Router LSA. */
330 if (w->type == OSPF_ROUTER_LSA) {
331 rl = (struct router_lsa *)w;
332
333 length = ntohs(w->length);
334
335 for (i = 0; i < ntohs(rl->links)
336 && length >= sizeof(struct router_lsa);
337 i++, length -= 12) {
338 switch (rl->link[i].type) {
339 case LSA_LINK_TYPE_POINTOPOINT:
340 case LSA_LINK_TYPE_VIRTUALLINK:
341 /* Router LSA ID. */
342 if (v->type == OSPF_ROUTER_LSA
343 && IPV4_ADDR_SAME(&rl->link[i].link_id,
344 &v->id)) {
345 return i;
346 }
347 break;
348 case LSA_LINK_TYPE_TRANSIT:
349 /* Network LSA ID. */
350 if (v->type == OSPF_NETWORK_LSA
351 && IPV4_ADDR_SAME(&rl->link[i].link_id,
352 &v->id)) {
353 return i;
354 }
355 break;
356 case LSA_LINK_TYPE_STUB:
357 /* Stub can't lead anywhere, carry on */
358 continue;
359 default:
360 break;
361 }
362 }
363 }
364 return -1;
365 }
366
367 /* Find the next link after prev_link from v to w. If prev_link is
368 * NULL, return the first link from v to w. Ignore stub and virtual links;
369 * these link types will never be returned.
370 */
371 static struct router_lsa_link *
372 ospf_get_next_link(struct vertex *v, struct vertex *w,
373 struct router_lsa_link *prev_link)
374 {
375 uint8_t *p;
376 uint8_t *lim;
377 uint8_t lsa_type = LSA_LINK_TYPE_TRANSIT;
378 struct router_lsa_link *l;
379
380 if (w->type == OSPF_VERTEX_ROUTER)
381 lsa_type = LSA_LINK_TYPE_POINTOPOINT;
382
383 if (prev_link == NULL)
384 p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
385 else {
386 p = (uint8_t *)prev_link;
387 p += (OSPF_ROUTER_LSA_LINK_SIZE
388 + (prev_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
389 }
390
391 lim = ((uint8_t *)v->lsa) + ntohs(v->lsa->length);
392
393 while (p < lim) {
394 l = (struct router_lsa_link *)p;
395
396 p += (OSPF_ROUTER_LSA_LINK_SIZE
397 + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
398
399 if (l->m[0].type != lsa_type)
400 continue;
401
402 if (IPV4_ADDR_SAME(&l->link_id, &w->id))
403 return l;
404 }
405
406 return NULL;
407 }
408
409 static void ospf_spf_flush_parents(struct vertex *w)
410 {
411 struct vertex_parent *vp;
412 struct listnode *ln, *nn;
413
414 /* delete the existing nexthops */
415 for (ALL_LIST_ELEMENTS(w->parents, ln, nn, vp)) {
416 list_delete_node(w->parents, ln);
417 vertex_parent_free(vp);
418 }
419 }
420
421 /*
422 * Consider supplied next-hop for inclusion to the supplied list of
423 * equal-cost next-hops, adjust list as neccessary.
424 */
425 static void ospf_spf_add_parent(struct vertex *v, struct vertex *w,
426 struct vertex_nexthop *newhop,
427 unsigned int distance)
428 {
429 struct vertex_parent *vp, *wp;
430 struct listnode *node;
431
432 /* we must have a newhop, and a distance */
433 assert(v && w && newhop);
434 assert(distance);
435
436 /* IFF w has already been assigned a distance, then we shouldn't get
437 * here
438 * unless callers have determined V(l)->W is shortest / equal-shortest
439 * path (0 is a special case distance (no distance yet assigned)).
440 */
441 if (w->distance)
442 assert(distance <= w->distance);
443 else
444 w->distance = distance;
445
446 if (IS_DEBUG_OSPF_EVENT) {
447 char buf[2][INET_ADDRSTRLEN];
448 zlog_debug(
449 "%s: Adding %s as parent of %s", __func__,
450 inet_ntop(AF_INET, &v->lsa->id, buf[0], sizeof(buf[0])),
451 inet_ntop(AF_INET, &w->lsa->id, buf[1],
452 sizeof(buf[1])));
453 }
454
455 /* Adding parent for a new, better path: flush existing parents from W.
456 */
457 if (distance < w->distance) {
458 if (IS_DEBUG_OSPF_EVENT)
459 zlog_debug(
460 "%s: distance %d better than %d, flushing existing parents",
461 __func__, distance, w->distance);
462 ospf_spf_flush_parents(w);
463 w->distance = distance;
464 }
465
466 /* new parent is <= existing parents, add it to parent list (if nexthop
467 * not on parent list)
468 */
469 for (ALL_LIST_ELEMENTS_RO(w->parents, node, wp)) {
470 if (memcmp(newhop, wp->nexthop, sizeof(*newhop)) == 0) {
471 if (IS_DEBUG_OSPF_EVENT)
472 zlog_debug(
473 "%s: ... nexthop already on parent list, skipping add",
474 __func__);
475 return;
476 }
477 }
478
479 vp = vertex_parent_new(v, ospf_lsa_has_link(w->lsa, v->lsa), newhop);
480 listnode_add_sort(w->parents, vp);
481
482 return;
483 }
484
485 /* 16.1.1. Calculate nexthop from root through V (parent) to
486 * vertex W (destination), with given distance from root->W.
487 *
488 * The link must be supplied if V is the root vertex. In all other cases
489 * it may be NULL.
490 *
491 * Note that this function may fail, hence the state of the destination
492 * vertex, W, should /not/ be modified in a dependent manner until
493 * this function returns. This function will update the W vertex with the
494 * provided distance as appropriate.
495 */
496 static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
497 struct vertex *v, struct vertex *w,
498 struct router_lsa_link *l,
499 unsigned int distance, int lsa_pos)
500 {
501 struct listnode *node, *nnode;
502 struct vertex_nexthop *nh;
503 struct vertex_parent *vp;
504 struct ospf_interface *oi = NULL;
505 unsigned int added = 0;
506 char buf1[BUFSIZ];
507 char buf2[BUFSIZ];
508
509 if (IS_DEBUG_OSPF_EVENT) {
510 zlog_debug("ospf_nexthop_calculation(): Start");
511 ospf_vertex_dump("V (parent):", v, 1, 1);
512 ospf_vertex_dump("W (dest) :", w, 1, 1);
513 zlog_debug("V->W distance: %d", distance);
514 }
515
516 if (v == area->spf) {
517 /* 16.1.1 para 4. In the first case, the parent vertex (V) is
518 the
519 root (the calculating router itself). This means that the
520 destination is either a directly connected network or
521 directly
522 connected router. The outgoing interface in this case is
523 simply
524 the OSPF interface connecting to the destination
525 network/router.
526 */
527
528 /* we *must* be supplied with the link data */
529 assert(l != NULL);
530 oi = ospf_if_lookup_by_lsa_pos(area, lsa_pos);
531 if (!oi) {
532 zlog_debug(
533 "%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
534 __func__, lsa_pos,
535 inet_ntop(AF_INET, &l->link_id, buf1, BUFSIZ),
536 inet_ntop(AF_INET, &l->link_data, buf2,
537 BUFSIZ));
538 return 0;
539 }
540
541 if (IS_DEBUG_OSPF_EVENT) {
542 zlog_debug(
543 "%s: considering link:%s "
544 "type:%d link_id:%s link_data:%s",
545 __func__, oi->ifp->name, l->m[0].type,
546 inet_ntop(AF_INET, &l->link_id, buf1, BUFSIZ),
547 inet_ntop(AF_INET, &l->link_data, buf2,
548 BUFSIZ));
549 }
550
551 if (w->type == OSPF_VERTEX_ROUTER) {
552 /* l is a link from v to w
553 * l2 will be link from w to v
554 */
555 struct router_lsa_link *l2 = NULL;
556
557 if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) {
558 struct in_addr nexthop = {.s_addr = 0};
559
560 /* If the destination is a router which connects
561 to
562 the calculating router via a
563 Point-to-MultiPoint
564 network, the destination's next hop IP
565 address(es)
566 can be determined by examining the
567 destination's
568 router-LSA: each link pointing back to the
569 calculating router and having a Link Data
570 field
571 belonging to the Point-to-MultiPoint network
572 provides an IP address of the next hop
573 router.
574
575 At this point l is a link from V to W, and V
576 is the
577 root ("us"). If it is a point-to-multipoint
578 interface,
579 then look through the links in the opposite
580 direction (W to V).
581 If any of them have an address that lands
582 within the
583 subnet declared by the PtMP link, then that
584 link
585 is a constituent of the PtMP link, and its
586 address is
587 a nexthop address for V.
588 */
589 if (oi->type == OSPF_IFTYPE_POINTOPOINT) {
590 /* Having nexthop = 0 is tempting, but
591 NOT acceptable.
592 It breaks AS-External routes with a
593 forwarding address,
594 since
595 ospf_ase_complete_direct_routes()
596 will mistakenly
597 assume we've reached the last hop and
598 should place the
599 forwarding address as nexthop.
600 Also, users may configure
601 multi-access links in p2p mode,
602 so we need the IP to ARP the nexthop.
603 */
604 struct ospf_neighbor *nbr_w;
605
606 nbr_w = ospf_nbr_lookup_by_routerid(
607 oi->nbrs, &l->link_id);
608 if (nbr_w != NULL) {
609 added = 1;
610 nexthop = nbr_w->src;
611 }
612 } else if (oi->type
613 == OSPF_IFTYPE_POINTOMULTIPOINT) {
614 struct prefix_ipv4 la;
615
616 la.family = AF_INET;
617 la.prefixlen = oi->address->prefixlen;
618
619 /* V links to W on PtMP interface
620 - find the interface address on W */
621 while ((l2 = ospf_get_next_link(w, v,
622 l2))) {
623 la.prefix = l2->link_data;
624
625 if (prefix_cmp((struct prefix
626 *)&la,
627 oi->address)
628 != 0)
629 continue;
630 /* link_data is on our PtMP
631 * network */
632 added = 1;
633 nexthop = l2->link_data;
634 break;
635 }
636 }
637
638 if (added) {
639 /* found all necessary info to build
640 * nexthop */
641 nh = vertex_nexthop_new();
642 nh->oi = oi;
643 nh->router = nexthop;
644 ospf_spf_add_parent(v, w, nh, distance);
645 return 1;
646 } else
647 zlog_info(
648 "%s: could not determine nexthop for link %s",
649 __func__, oi->ifp->name);
650 } /* end point-to-point link from V to W */
651 else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK) {
652 struct ospf_vl_data *vl_data;
653
654 /* VLink implementation limitations:
655 * a) vl_data can only reference one nexthop, so
656 * no ECMP
657 * to backbone through VLinks. Though
658 * transit-area
659 * summaries may be considered, and those can
660 * be ECMP.
661 * b) We can only use /one/ VLink, even if
662 * multiple ones
663 * exist this router through multiple
664 * transit-areas.
665 */
666 vl_data = ospf_vl_lookup(area->ospf, NULL,
667 l->link_id);
668
669 if (vl_data
670 && CHECK_FLAG(vl_data->flags,
671 OSPF_VL_FLAG_APPROVED)) {
672 nh = vertex_nexthop_new();
673 nh->oi = vl_data->nexthop.oi;
674 nh->router = vl_data->nexthop.router;
675 ospf_spf_add_parent(v, w, nh, distance);
676 return 1;
677 } else
678 zlog_info(
679 "ospf_nexthop_calculation(): "
680 "vl_data for VL link not found");
681 } /* end virtual-link from V to W */
682 return 0;
683 } /* end W is a Router vertex */
684 else {
685 assert(w->type == OSPF_VERTEX_NETWORK);
686
687 nh = vertex_nexthop_new();
688 nh->oi = oi;
689 nh->router.s_addr = 0; /* Nexthop not required */
690 ospf_spf_add_parent(v, w, nh, distance);
691 return 1;
692 }
693 } /* end V is the root */
694 /* Check if W's parent is a network connected to root. */
695 else if (v->type == OSPF_VERTEX_NETWORK) {
696 /* See if any of V's parents are the root. */
697 for (ALL_LIST_ELEMENTS(v->parents, node, nnode, vp)) {
698 if (vp->parent == area->spf) /* connects to root? */
699 {
700 /* 16.1.1 para 5. ...the parent vertex is a
701 * network that
702 * directly connects the calculating router to
703 * the destination
704 * router. The list of next hops is then
705 * determined by
706 * examining the destination's router-LSA...
707 */
708
709 assert(w->type == OSPF_VERTEX_ROUTER);
710 while ((l = ospf_get_next_link(w, v, l))) {
711 /* ...For each link in the router-LSA
712 * that points back to the
713 * parent network, the link's Link Data
714 * field provides the IP
715 * address of a next hop router. The
716 * outgoing interface to
717 * use can then be derived from the next
718 * hop IP address (or
719 * it can be inherited from the parent
720 * network).
721 */
722 nh = vertex_nexthop_new();
723 nh->oi = vp->nexthop->oi;
724 nh->router = l->link_data;
725 added = 1;
726 ospf_spf_add_parent(v, w, nh, distance);
727 }
728 /* Note lack of return is deliberate. See next
729 * comment. */
730 }
731 }
732 /* NB: This code is non-trivial.
733 *
734 * E.g. it is not enough to know that V connects to the root. It
735 * is
736 * also important that the while above, looping through all
737 * links from
738 * W->V found at least one link, so that we know there is
739 * bi-directional connectivity between V and W (which need not
740 * be the
741 * case, e.g. when OSPF has not yet converged fully).
742 * Otherwise, if
743 * we /always/ return here, without having checked that
744 * root->V->-W
745 * actually resulted in a valid nexthop being created, then we
746 * we will
747 * prevent SPF from finding/using higher cost paths.
748 *
749 * It is important, if root->V->W has not been added, that we
750 * continue
751 * through to the intervening-router nexthop code below. So as
752 * to
753 * ensure other paths to V may be used. This avoids unnecessary
754 * blackholes while OSPF is convergening.
755 *
756 * I.e. we may have arrived at this function, examining V -> W,
757 * via
758 * workable paths other than root -> V, and it's important to
759 * avoid
760 * getting "confused" by non-working root->V->W path - it's
761 * important
762 * to *not* lose the working non-root paths, just because of a
763 * non-viable root->V->W.
764 *
765 * See also bug #330 (required reading!), and:
766 *
767 * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
768 */
769 if (added)
770 return added;
771 }
772
773 /* 16.1.1 para 4. If there is at least one intervening router in the
774 * current shortest path between the destination and the root, the
775 * destination simply inherits the set of next hops from the
776 * parent.
777 */
778 if (IS_DEBUG_OSPF_EVENT)
779 zlog_debug("%s: Intervening routers, adding parent(s)",
780 __func__);
781
782 for (ALL_LIST_ELEMENTS(v->parents, node, nnode, vp)) {
783 added = 1;
784 ospf_spf_add_parent(v, w, vp->nexthop, distance);
785 }
786
787 return added;
788 }
789
790 /* RFC2328 Section 16.1 (2).
791 * v is on the SPF tree. Examine the links in v's LSA. Update the list
792 * of candidates with any vertices not already on the list. If a lower-cost
793 * path is found to a vertex already on the candidate list, store the new cost.
794 */
795 static void ospf_spf_next(struct vertex *v, struct ospf *ospf,
796 struct ospf_area *area,
797 struct vertex_pqueue_head *candidate)
798 {
799 struct ospf_lsa *w_lsa = NULL;
800 uint8_t *p;
801 uint8_t *lim;
802 struct router_lsa_link *l = NULL;
803 struct in_addr *r;
804 int type = 0, lsa_pos = -1, lsa_pos_next = 0;
805
806 /* If this is a router-LSA, and bit V of the router-LSA (see Section
807 A.4.2:RFC2328) is set, set Area A's TransitCapability to true. */
808 if (v->type == OSPF_VERTEX_ROUTER) {
809 if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa *)v->lsa))
810 area->transit = OSPF_TRANSIT_TRUE;
811 }
812
813 if (IS_DEBUG_OSPF_EVENT)
814 zlog_debug("%s: Next vertex of %s vertex %s", __func__,
815 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
816 inet_ntoa(v->lsa->id));
817
818 p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
819 lim = ((uint8_t *)v->lsa) + ntohs(v->lsa->length);
820
821 while (p < lim) {
822 struct vertex *w;
823 unsigned int distance;
824
825 /* In case of V is Router-LSA. */
826 if (v->lsa->type == OSPF_ROUTER_LSA) {
827 l = (struct router_lsa_link *)p;
828
829 lsa_pos = lsa_pos_next; /* LSA link position */
830 lsa_pos_next++;
831 p += (OSPF_ROUTER_LSA_LINK_SIZE
832 + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
833
834 /* (a) If this is a link to a stub network, examine the
835 next
836 link in V's LSA. Links to stub networks will be
837 considered in the second stage of the shortest path
838 calculation. */
839 if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
840 continue;
841
842 /* (b) Otherwise, W is a transit vertex (router or
843 transit
844 network). Look up the vertex W's LSA (router-LSA or
845 network-LSA) in Area A's link state database. */
846 switch (type) {
847 case LSA_LINK_TYPE_POINTOPOINT:
848 case LSA_LINK_TYPE_VIRTUALLINK:
849 if (type == LSA_LINK_TYPE_VIRTUALLINK) {
850 if (IS_DEBUG_OSPF_EVENT)
851 zlog_debug(
852 "looking up LSA through VL: %s",
853 inet_ntoa(l->link_id));
854 }
855
856 w_lsa = ospf_lsa_lookup(ospf, area,
857 OSPF_ROUTER_LSA,
858 l->link_id, l->link_id);
859 if (w_lsa) {
860 if (IS_DEBUG_OSPF_EVENT)
861 zlog_debug(
862 "found Router LSA %s",
863 inet_ntoa(l->link_id));
864 }
865 break;
866 case LSA_LINK_TYPE_TRANSIT:
867 if (IS_DEBUG_OSPF_EVENT)
868 zlog_debug(
869 "Looking up Network LSA, ID: %s",
870 inet_ntoa(l->link_id));
871 w_lsa = ospf_lsa_lookup_by_id(
872 area, OSPF_NETWORK_LSA, l->link_id);
873 if (w_lsa)
874 if (IS_DEBUG_OSPF_EVENT)
875 zlog_debug("found the LSA");
876 break;
877 default:
878 flog_warn(EC_OSPF_LSA,
879 "Invalid LSA link type %d", type);
880 continue;
881 }
882 } else {
883 /* In case of V is Network-LSA. */
884 r = (struct in_addr *)p;
885 p += sizeof(struct in_addr);
886
887 /* Lookup the vertex W's LSA. */
888 w_lsa = ospf_lsa_lookup_by_id(area, OSPF_ROUTER_LSA,
889 *r);
890 if (w_lsa) {
891 if (IS_DEBUG_OSPF_EVENT)
892 zlog_debug("found Router LSA %s",
893 inet_ntoa(w_lsa->data->id));
894 }
895 }
896
897 /* (b cont.) If the LSA does not exist, or its LS age is equal
898 to MaxAge, or it does not have a link back to vertex V,
899 examine the next link in V's LSA.[23] */
900 if (w_lsa == NULL) {
901 if (IS_DEBUG_OSPF_EVENT)
902 zlog_debug("No LSA found");
903 continue;
904 }
905
906 if (IS_LSA_MAXAGE(w_lsa)) {
907 if (IS_DEBUG_OSPF_EVENT)
908 zlog_debug("LSA is MaxAge");
909 continue;
910 }
911
912 if (ospf_lsa_has_link(w_lsa->data, v->lsa) < 0) {
913 if (IS_DEBUG_OSPF_EVENT)
914 zlog_debug("The LSA doesn't have a link back");
915 continue;
916 }
917
918 /* (c) If vertex W is already on the shortest-path tree, examine
919 the next link in the LSA. */
920 if (w_lsa->stat == LSA_SPF_IN_SPFTREE) {
921 if (IS_DEBUG_OSPF_EVENT)
922 zlog_debug("The LSA is already in SPF");
923 continue;
924 }
925
926 /* (d) Calculate the link state cost D of the resulting path
927 from the root to vertex W. D is equal to the sum of the link
928 state cost of the (already calculated) shortest path to
929 vertex V and the advertised cost of the link between vertices
930 V and W. If D is: */
931
932 /* calculate link cost D. */
933 if (v->lsa->type == OSPF_ROUTER_LSA)
934 distance = v->distance + ntohs(l->m[0].metric);
935 else /* v is not a Router-LSA */
936 distance = v->distance;
937
938 /* Is there already vertex W in candidate list? */
939 if (w_lsa->stat == LSA_SPF_NOT_EXPLORED) {
940 /* prepare vertex W. */
941 w = ospf_vertex_new(w_lsa);
942
943 /* Calculate nexthop to W. */
944 if (ospf_nexthop_calculation(area, v, w, l, distance,
945 lsa_pos))
946 vertex_pqueue_add(candidate, w);
947 else if (IS_DEBUG_OSPF_EVENT)
948 zlog_debug("Nexthop Calc failed");
949 } else if (w_lsa->stat != LSA_SPF_IN_SPFTREE) {
950 w = w_lsa->stat;
951 /* if D is greater than. */
952 if (w->distance < distance) {
953 continue;
954 }
955 /* equal to. */
956 else if (w->distance == distance) {
957 /* Found an equal-cost path to W.
958 * Calculate nexthop of to W from V. */
959 ospf_nexthop_calculation(area, v, w, l,
960 distance, lsa_pos);
961 }
962 /* less than. */
963 else {
964 /* Found a lower-cost path to W.
965 * nexthop_calculation is conditional, if it
966 * finds
967 * valid nexthop it will call spf_add_parents,
968 * which
969 * will flush the old parents
970 */
971 vertex_pqueue_del(candidate, w);
972 ospf_nexthop_calculation(area, v, w, l,
973 distance, lsa_pos);
974 vertex_pqueue_add(candidate, w);
975 }
976 } /* end W is already on the candidate list */
977 } /* end loop over the links in V's LSA */
978 }
979
980 static void ospf_spf_dump(struct vertex *v, int i)
981 {
982 struct listnode *cnode;
983 struct listnode *nnode;
984 struct vertex_parent *parent;
985
986 if (v->type == OSPF_VERTEX_ROUTER) {
987 if (IS_DEBUG_OSPF_EVENT)
988 zlog_debug("SPF Result: %d [R] %s", i,
989 inet_ntoa(v->lsa->id));
990 } else {
991 struct network_lsa *lsa = (struct network_lsa *)v->lsa;
992 if (IS_DEBUG_OSPF_EVENT)
993 zlog_debug("SPF Result: %d [N] %s/%d", i,
994 inet_ntoa(v->lsa->id),
995 ip_masklen(lsa->mask));
996 }
997
998 if (IS_DEBUG_OSPF_EVENT)
999 for (ALL_LIST_ELEMENTS_RO(v->parents, nnode, parent)) {
1000 zlog_debug(" nexthop %p %s %s", (void *)parent->nexthop,
1001 inet_ntoa(parent->nexthop->router),
1002 parent->nexthop->oi
1003 ? IF_NAME(parent->nexthop->oi)
1004 : "NULL");
1005 }
1006
1007 i++;
1008
1009 for (ALL_LIST_ELEMENTS_RO(v->children, cnode, v))
1010 ospf_spf_dump(v, i);
1011 }
1012
1013 /* Second stage of SPF calculation. */
1014 static void ospf_spf_process_stubs(struct ospf_area *area, struct vertex *v,
1015 struct route_table *rt, int parent_is_root)
1016 {
1017 struct listnode *cnode, *cnnode;
1018 struct vertex *child;
1019
1020 if (IS_DEBUG_OSPF_EVENT)
1021 zlog_debug("ospf_process_stub():processing stubs for area %s",
1022 inet_ntoa(area->area_id));
1023 if (v->type == OSPF_VERTEX_ROUTER) {
1024 uint8_t *p;
1025 uint8_t *lim;
1026 struct router_lsa_link *l;
1027 struct router_lsa *rlsa;
1028 int lsa_pos = 0;
1029
1030 if (IS_DEBUG_OSPF_EVENT)
1031 zlog_debug(
1032 "ospf_process_stubs():processing router LSA, id: %s",
1033 inet_ntoa(v->lsa->id));
1034 rlsa = (struct router_lsa *)v->lsa;
1035
1036
1037 if (IS_DEBUG_OSPF_EVENT)
1038 zlog_debug(
1039 "ospf_process_stubs(): we have %d links to process",
1040 ntohs(rlsa->links));
1041 p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
1042 lim = ((uint8_t *)v->lsa) + ntohs(v->lsa->length);
1043
1044 while (p < lim) {
1045 l = (struct router_lsa_link *)p;
1046
1047 p += (OSPF_ROUTER_LSA_LINK_SIZE
1048 + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
1049
1050 if (l->m[0].type == LSA_LINK_TYPE_STUB)
1051 ospf_intra_add_stub(rt, l, v, area,
1052 parent_is_root, lsa_pos);
1053 lsa_pos++;
1054 }
1055 }
1056
1057 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1,
1058 1);
1059
1060 for (ALL_LIST_ELEMENTS(v->children, cnode, cnnode, child)) {
1061 if (CHECK_FLAG(child->flags, OSPF_VERTEX_PROCESSED))
1062 continue;
1063
1064 /* the first level of routers connected to the root
1065 * should have 'parent_is_root' set, including those
1066 * connected via a network vertex.
1067 */
1068 if (area->spf == v)
1069 parent_is_root = 1;
1070 else if (v->type == OSPF_VERTEX_ROUTER)
1071 parent_is_root = 0;
1072
1073 ospf_spf_process_stubs(area, child, rt, parent_is_root);
1074
1075 SET_FLAG(child->flags, OSPF_VERTEX_PROCESSED);
1076 }
1077 }
1078
1079 void ospf_rtrs_free(struct route_table *rtrs)
1080 {
1081 struct route_node *rn;
1082 struct list *or_list;
1083 struct ospf_route * or ;
1084 struct listnode *node, *nnode;
1085
1086 if (IS_DEBUG_OSPF_EVENT)
1087 zlog_debug("Route: Router Routing Table free");
1088
1089 for (rn = route_top(rtrs); rn; rn = route_next(rn))
1090 if ((or_list = rn->info) != NULL) {
1091 for (ALL_LIST_ELEMENTS(or_list, node, nnode, or))
1092 ospf_route_free(or);
1093
1094 list_delete(&or_list);
1095
1096 /* Unlock the node. */
1097 rn->info = NULL;
1098 route_unlock_node(rn);
1099 }
1100 route_table_finish(rtrs);
1101 }
1102
1103 #if 0
1104 static void
1105 ospf_rtrs_print (struct route_table *rtrs)
1106 {
1107 struct route_node *rn;
1108 struct list *or_list;
1109 struct listnode *ln;
1110 struct listnode *pnode;
1111 struct ospf_route *or;
1112 struct ospf_path *path;
1113 char buf1[BUFSIZ];
1114 char buf2[BUFSIZ];
1115
1116 if (IS_DEBUG_OSPF_EVENT)
1117 zlog_debug ("ospf_rtrs_print() start");
1118
1119 for (rn = route_top (rtrs); rn; rn = route_next (rn))
1120 if ((or_list = rn->info) != NULL)
1121 for (ALL_LIST_ELEMENTS_RO (or_list, ln, or))
1122 {
1123 switch (or->path_type)
1124 {
1125 case OSPF_PATH_INTRA_AREA:
1126 if (IS_DEBUG_OSPF_EVENT)
1127 zlog_debug ("%s [%d] area: %s",
1128 inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
1129 or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
1130 buf2, BUFSIZ));
1131 break;
1132 case OSPF_PATH_INTER_AREA:
1133 if (IS_DEBUG_OSPF_EVENT)
1134 zlog_debug ("%s IA [%d] area: %s",
1135 inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
1136 or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
1137 buf2, BUFSIZ));
1138 break;
1139 default:
1140 break;
1141 }
1142
1143 for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path))
1144 {
1145 if (path->nexthop.s_addr == 0)
1146 {
1147 if (IS_DEBUG_OSPF_EVENT)
1148 zlog_debug (" directly attached to %s\r",
1149 ifindex2ifname (path->ifindex), VRF_DEFAULT);
1150 }
1151 else
1152 {
1153 if (IS_DEBUG_OSPF_EVENT)
1154 zlog_debug (" via %s, %s\r",
1155 inet_ntoa (path->nexthop),
1156 ifindex2ifname (path->ifindex), VRF_DEFAULT);
1157 }
1158 }
1159 }
1160
1161 zlog_debug ("ospf_rtrs_print() end");
1162 }
1163 #endif
1164
1165 /* Calculating the shortest-path tree for an area. */
1166 static void ospf_spf_calculate(struct ospf *ospf, struct ospf_area *area,
1167 struct route_table *new_table,
1168 struct route_table *new_rtrs)
1169 {
1170 struct vertex_pqueue_head candidate;
1171 struct vertex *v;
1172
1173 if (IS_DEBUG_OSPF_EVENT) {
1174 zlog_debug("ospf_spf_calculate: Start");
1175 zlog_debug("ospf_spf_calculate: running Dijkstra for area %s",
1176 inet_ntoa(area->area_id));
1177 }
1178
1179 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1180 return this area's calculation. */
1181 if (!area->router_lsa_self) {
1182 if (IS_DEBUG_OSPF_EVENT)
1183 zlog_debug(
1184 "ospf_spf_calculate: "
1185 "Skip area %s's calculation due to empty router_lsa_self",
1186 inet_ntoa(area->area_id));
1187 return;
1188 }
1189
1190 /* RFC2328 16.1. (1). */
1191 /* Initialize the algorithm's data structures. */
1192
1193 /* This function scans all the LSA database and set the stat field to
1194 * LSA_SPF_NOT_EXPLORED. */
1195 lsdb_clean_stat(area->lsdb);
1196 /* Create a new heap for the candidates. */
1197 vertex_pqueue_init(&candidate);
1198
1199 /* Initialize the shortest-path tree to only the root (which is the
1200 router doing the calculation). */
1201 ospf_spf_init(area);
1202 v = area->spf;
1203 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of
1204 * the
1205 * spanning tree. */
1206 v->lsa_p->stat = LSA_SPF_IN_SPFTREE;
1207
1208 /* Set Area A's TransitCapability to false. */
1209 area->transit = OSPF_TRANSIT_FALSE;
1210 area->shortcut_capability = 1;
1211
1212 for (;;) {
1213 /* RFC2328 16.1. (2). */
1214 ospf_spf_next(v, ospf, area, &candidate);
1215
1216 /* RFC2328 16.1. (3). */
1217 /* If at this step the candidate list is empty, the shortest-
1218 path tree (of transit vertices) has been completely built and
1219 this stage of the procedure terminates. */
1220 /* Otherwise, choose the vertex belonging to the candidate list
1221 that is closest to the root, and add it to the shortest-path
1222 tree (removing it from the candidate list in the
1223 process). */
1224 /* Extract from the candidates the node with the lower key. */
1225 v = vertex_pqueue_pop(&candidate);
1226 if (!v)
1227 break;
1228 /* Update stat field in vertex. */
1229 v->lsa_p->stat = LSA_SPF_IN_SPFTREE;
1230
1231 ospf_vertex_add_parent(v);
1232
1233 /* RFC2328 16.1. (4). */
1234 if (v->type == OSPF_VERTEX_ROUTER)
1235 ospf_intra_add_router(new_rtrs, v, area);
1236 else
1237 ospf_intra_add_transit(new_table, v, area);
1238
1239 /* RFC2328 16.1. (5). */
1240 /* Iterate the algorithm by returning to Step 2. */
1241
1242 } /* end loop until no more candidate vertices */
1243
1244 if (IS_DEBUG_OSPF_EVENT) {
1245 ospf_spf_dump(area->spf, 0);
1246 ospf_route_table_dump(new_table);
1247 }
1248
1249 /* Second stage of SPF calculation procedure's */
1250 ospf_spf_process_stubs(area, area->spf, new_table, 0);
1251
1252 /* Free candidate queue. */
1253 //vertex_pqueue_fini(&candidate);
1254
1255 ospf_vertex_dump(__func__, area->spf, 0, 1);
1256 /* Free nexthop information, canonical versions of which are attached
1257 * the first level of router vertices attached to the root vertex, see
1258 * ospf_nexthop_calculation.
1259 */
1260 ospf_canonical_nexthops_free(area->spf);
1261
1262 /* Increment SPF Calculation Counter. */
1263 area->spf_calculation++;
1264
1265 monotime(&area->ospf->ts_spf);
1266 area->ts_spf = area->ospf->ts_spf;
1267
1268 if (IS_DEBUG_OSPF_EVENT)
1269 zlog_debug("ospf_spf_calculate: Stop. %zd vertices",
1270 mtype_stats_alloc(MTYPE_OSPF_VERTEX));
1271
1272 /* Free SPF vertices, but not the list. List has ospf_vertex_free
1273 * as deconstructor.
1274 */
1275 list_delete_all_node(&vertex_list);
1276 }
1277
1278 /* Timer for SPF calculation. */
1279 static int ospf_spf_calculate_timer(struct thread *thread)
1280 {
1281 struct ospf *ospf = THREAD_ARG(thread);
1282 struct route_table *new_table, *new_rtrs;
1283 struct ospf_area *area;
1284 struct listnode *node, *nnode;
1285 struct timeval start_time, spf_start_time;
1286 int areas_processed = 0;
1287 unsigned long ia_time, prune_time, rt_time;
1288 unsigned long abr_time, total_spf_time, spf_time;
1289 char rbuf[32]; /* reason_buf */
1290
1291 if (IS_DEBUG_OSPF_EVENT)
1292 zlog_debug("SPF: Timer (SPF calculation expire)");
1293
1294 ospf->t_spf_calc = NULL;
1295
1296 monotime(&spf_start_time);
1297 /* Allocate new table tree. */
1298 new_table = route_table_init();
1299 new_rtrs = route_table_init();
1300
1301 ospf_vl_unapprove(ospf);
1302
1303 /* Calculate SPF for each area. */
1304 for (ALL_LIST_ELEMENTS(ospf->areas, node, nnode, area)) {
1305 /* Do backbone last, so as to first discover intra-area paths
1306 * for any back-bone virtual-links
1307 */
1308 if (ospf->backbone && ospf->backbone == area)
1309 continue;
1310
1311 ospf_spf_calculate(ospf, area, new_table, new_rtrs);
1312 areas_processed++;
1313 }
1314
1315 /* SPF for backbone, if required */
1316 if (ospf->backbone) {
1317 ospf_spf_calculate(ospf, ospf->backbone, new_table, new_rtrs);
1318 areas_processed++;
1319 }
1320
1321 spf_time = monotime_since(&spf_start_time, NULL);
1322
1323 ospf_vl_shut_unapproved(ospf);
1324
1325 monotime(&start_time);
1326 ospf_ia_routing(ospf, new_table, new_rtrs);
1327 ia_time = monotime_since(&start_time, NULL);
1328
1329 monotime(&start_time);
1330 ospf_prune_unreachable_networks(new_table);
1331 ospf_prune_unreachable_routers(new_rtrs);
1332 prune_time = monotime_since(&start_time, NULL);
1333
1334 /* AS-external-LSA calculation should not be performed here. */
1335
1336 /* If new Router Route is installed,
1337 then schedule re-calculate External routes. */
1338 if (1)
1339 ospf_ase_calculate_schedule(ospf);
1340
1341 ospf_ase_calculate_timer_add(ospf);
1342
1343 if (IS_DEBUG_OSPF_EVENT)
1344 zlog_debug(
1345 "%s: ospf install new route, vrf %s id %u new_table count %lu",
1346 __PRETTY_FUNCTION__, ospf_vrf_id_to_name(ospf->vrf_id),
1347 ospf->vrf_id, new_table->count);
1348 /* Update routing table. */
1349 monotime(&start_time);
1350 ospf_route_install(ospf, new_table);
1351 rt_time = monotime_since(&start_time, NULL);
1352
1353 /* Update ABR/ASBR routing table */
1354 if (ospf->old_rtrs) {
1355 /* old_rtrs's node holds linked list of ospf_route. --kunihiro.
1356 */
1357 /* ospf_route_delete (ospf->old_rtrs); */
1358 ospf_rtrs_free(ospf->old_rtrs);
1359 }
1360
1361 ospf->old_rtrs = ospf->new_rtrs;
1362 ospf->new_rtrs = new_rtrs;
1363
1364 monotime(&start_time);
1365 if (IS_OSPF_ABR(ospf))
1366 ospf_abr_task(ospf);
1367 abr_time = monotime_since(&start_time, NULL);
1368
1369 /* Schedule Segment Routing update */
1370 ospf_sr_update_timer_add(ospf);
1371
1372 total_spf_time =
1373 monotime_since(&spf_start_time, &ospf->ts_spf_duration);
1374
1375 rbuf[0] = '\0';
1376 if (spf_reason_flags) {
1377 if (spf_reason_flags & SPF_FLAG_ROUTER_LSA_INSTALL)
1378 strncat(rbuf, "R, ", sizeof(rbuf) - strlen(rbuf) - 1);
1379 if (spf_reason_flags & SPF_FLAG_NETWORK_LSA_INSTALL)
1380 strncat(rbuf, "N, ", sizeof(rbuf) - strlen(rbuf) - 1);
1381 if (spf_reason_flags & SPF_FLAG_SUMMARY_LSA_INSTALL)
1382 strncat(rbuf, "S, ", sizeof(rbuf) - strlen(rbuf) - 1);
1383 if (spf_reason_flags & SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL)
1384 strncat(rbuf, "AS, ", sizeof(rbuf) - strlen(rbuf) - 1);
1385 if (spf_reason_flags & SPF_FLAG_ABR_STATUS_CHANGE)
1386 strncat(rbuf, "ABR, ", sizeof(rbuf) - strlen(rbuf) - 1);
1387 if (spf_reason_flags & SPF_FLAG_ASBR_STATUS_CHANGE)
1388 strncat(rbuf, "ASBR, ",
1389 sizeof(rbuf) - strlen(rbuf) - 1);
1390 if (spf_reason_flags & SPF_FLAG_MAXAGE)
1391 strncat(rbuf, "M, ", sizeof(rbuf) - strlen(rbuf) - 1);
1392
1393 size_t rbuflen = strlen(rbuf);
1394 if (rbuflen >= 2)
1395 rbuf[rbuflen - 2] = '\0'; /* skip the last ", " */
1396 else
1397 rbuf[0] = '\0';
1398 }
1399
1400 if (IS_DEBUG_OSPF_EVENT) {
1401 zlog_info("SPF Processing Time(usecs): %ld", total_spf_time);
1402 zlog_info("\t SPF Time: %ld", spf_time);
1403 zlog_info("\t InterArea: %ld", ia_time);
1404 zlog_info("\t Prune: %ld", prune_time);
1405 zlog_info("\tRouteInstall: %ld", rt_time);
1406 if (IS_OSPF_ABR(ospf))
1407 zlog_info("\t ABR: %ld (%d areas)", abr_time,
1408 areas_processed);
1409 zlog_info("Reason(s) for SPF: %s", rbuf);
1410 }
1411
1412 ospf_clear_spf_reason_flags();
1413
1414 return 0;
1415 }
1416
1417 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1418 set timer for SPF calc. */
1419 void ospf_spf_calculate_schedule(struct ospf *ospf, ospf_spf_reason_t reason)
1420 {
1421 unsigned long delay, elapsed, ht;
1422
1423 if (IS_DEBUG_OSPF_EVENT)
1424 zlog_debug("SPF: calculation timer scheduled");
1425
1426 /* OSPF instance does not exist. */
1427 if (ospf == NULL)
1428 return;
1429
1430 ospf_spf_set_reason(reason);
1431
1432 /* SPF calculation timer is already scheduled. */
1433 if (ospf->t_spf_calc) {
1434 if (IS_DEBUG_OSPF_EVENT)
1435 zlog_debug(
1436 "SPF: calculation timer is already scheduled: %p",
1437 (void *)ospf->t_spf_calc);
1438 return;
1439 }
1440
1441 elapsed = monotime_since(&ospf->ts_spf, NULL) / 1000;
1442
1443 ht = ospf->spf_holdtime * ospf->spf_hold_multiplier;
1444
1445 if (ht > ospf->spf_max_holdtime)
1446 ht = ospf->spf_max_holdtime;
1447
1448 /* Get SPF calculation delay time. */
1449 if (elapsed < ht) {
1450 /* Got an event within the hold time of last SPF. We need to
1451 * increase the hold_multiplier, if it's not already at/past
1452 * maximum value, and wasn't already increased..
1453 */
1454 if (ht < ospf->spf_max_holdtime)
1455 ospf->spf_hold_multiplier++;
1456
1457 /* always honour the SPF initial delay */
1458 if ((ht - elapsed) < ospf->spf_delay)
1459 delay = ospf->spf_delay;
1460 else
1461 delay = ht - elapsed;
1462 } else {
1463 /* Event is past required hold-time of last SPF */
1464 delay = ospf->spf_delay;
1465 ospf->spf_hold_multiplier = 1;
1466 }
1467
1468 if (IS_DEBUG_OSPF_EVENT)
1469 zlog_debug("SPF: calculation timer delay = %ld msec", delay);
1470
1471 ospf->t_spf_calc = NULL;
1472 thread_add_timer_msec(master, ospf_spf_calculate_timer, ospf, delay,
1473 &ospf->t_spf_calc);
1474 }
FRRouting mirror