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