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