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