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