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