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