]>
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" |
668e8a11 | 49 | #include "ospfd/ospf_errors.h" |
718e3744 | 50 | |
cf744958 DS |
51 | /* Variables to ensure a SPF scheduled log message is printed only once */ |
52 | ||
53 | static unsigned int spf_reason_flags = 0; | |
54 | ||
c971918a DL |
55 | /* dummy vertex to flag "in spftree" */ |
56 | static const struct vertex vertex_in_spftree = {}; | |
57 | #define LSA_SPF_IN_SPFTREE (struct vertex *)&vertex_in_spftree | |
58 | #define LSA_SPF_NOT_EXPLORED NULL | |
59 | ||
d62a17ae | 60 | static void ospf_clear_spf_reason_flags(void) |
cf744958 | 61 | { |
d62a17ae | 62 | spf_reason_flags = 0; |
cf744958 DS |
63 | } |
64 | ||
d62a17ae | 65 | static void ospf_spf_set_reason(ospf_spf_reason_t reason) |
cf744958 | 66 | { |
d62a17ae | 67 | spf_reason_flags |= 1 << reason; |
cf744958 DS |
68 | } |
69 | ||
d62a17ae | 70 | static void ospf_vertex_free(void *); |
5ec5929c G |
71 | /* |
72 | * List of allocated vertices, to simplify cleanup of SPF. | |
9c27ef9b PJ |
73 | * Not thread-safe obviously. If it ever needs to be, it'd have to be |
74 | * dynamically allocated at begin of ospf_spf_calculate | |
75 | */ | |
d62a17ae | 76 | static struct list vertex_list = {.del = ospf_vertex_free}; |
6b0655a2 | 77 | |
5ec5929c G |
78 | /* |
79 | * Heap related functions, for the managment of the candidates, to | |
80 | * be used with pqueue. | |
81 | */ | |
c971918a | 82 | static int vertex_cmp(const struct vertex *v1, const struct vertex *v2) |
462f20d5 | 83 | { |
c971918a DL |
84 | if (v1->distance != v2->distance) |
85 | return v1->distance - v2->distance; | |
86 | ||
87 | if (v1->type != v2->type) { | |
88 | switch (v1->type) { | |
89 | case OSPF_VERTEX_NETWORK: | |
90 | return -1; | |
91 | case OSPF_VERTEX_ROUTER: | |
92 | return 1; | |
93 | } | |
d62a17ae | 94 | } |
95 | return 0; | |
462f20d5 | 96 | } |
c971918a | 97 | DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue, struct vertex, pqi, vertex_cmp) |
462f20d5 | 98 | |
c971918a | 99 | static void lsdb_clean_stat(struct ospf_lsdb *lsdb) |
462f20d5 | 100 | { |
c971918a DL |
101 | struct route_table *table; |
102 | struct route_node *rn; | |
103 | struct ospf_lsa *lsa; | |
104 | int i; | |
105 | ||
106 | for (i = OSPF_MIN_LSA; i < OSPF_MAX_LSA; i++) { | |
107 | table = lsdb->type[i].db; | |
108 | for (rn = route_top(table); rn; rn = route_next(rn)) | |
109 | if ((lsa = (rn->info)) != NULL) | |
110 | lsa->stat = LSA_SPF_NOT_EXPLORED; | |
111 | } | |
462f20d5 | 112 | } |
6b0655a2 | 113 | |
d62a17ae | 114 | static struct vertex_nexthop *vertex_nexthop_new(void) |
718e3744 | 115 | { |
d62a17ae | 116 | return XCALLOC(MTYPE_OSPF_NEXTHOP, sizeof(struct vertex_nexthop)); |
718e3744 | 117 | } |
118 | ||
d62a17ae | 119 | static void vertex_nexthop_free(struct vertex_nexthop *nh) |
718e3744 | 120 | { |
d62a17ae | 121 | XFREE(MTYPE_OSPF_NEXTHOP, nh); |
718e3744 | 122 | } |
123 | ||
5ec5929c G |
124 | /* |
125 | * Free the canonical nexthop objects for an area, ie the nexthop objects | |
9c27ef9b PJ |
126 | * attached to the first-hop router vertices, and any intervening network |
127 | * vertices. | |
eb3da6df | 128 | */ |
d62a17ae | 129 | static void ospf_canonical_nexthops_free(struct vertex *root) |
718e3744 | 130 | { |
d62a17ae | 131 | struct listnode *node, *nnode; |
132 | struct vertex *child; | |
133 | ||
134 | for (ALL_LIST_ELEMENTS(root->children, node, nnode, child)) { | |
135 | struct listnode *n2, *nn2; | |
136 | struct vertex_parent *vp; | |
137 | ||
5ec5929c G |
138 | /* |
139 | * router vertices through an attached network each | |
d62a17ae | 140 | * have a distinct (canonical / not inherited) nexthop |
141 | * which must be freed. | |
142 | * | |
143 | * A network vertex can only have router vertices as its | |
144 | * children, so only one level of recursion is possible. | |
145 | */ | |
146 | if (child->type == OSPF_VERTEX_NETWORK) | |
147 | ospf_canonical_nexthops_free(child); | |
148 | ||
149 | /* Free child nexthops pointing back to this root vertex */ | |
150 | for (ALL_LIST_ELEMENTS(child->parents, n2, nn2, vp)) | |
cd4af525 | 151 | if (vp->parent == root && vp->nexthop) { |
d62a17ae | 152 | vertex_nexthop_free(vp->nexthop); |
cd4af525 CS |
153 | vp->nexthop = NULL; |
154 | } | |
d62a17ae | 155 | } |
156 | } | |
6b0655a2 | 157 | |
5ec5929c G |
158 | /* |
159 | * TODO: Parent list should be excised, in favour of maintaining only | |
9c27ef9b PJ |
160 | * vertex_nexthop, with refcounts. |
161 | */ | |
d62a17ae | 162 | static struct vertex_parent *vertex_parent_new(struct vertex *v, int backlink, |
163 | struct vertex_nexthop *hop) | |
eb3da6df | 164 | { |
d62a17ae | 165 | struct vertex_parent *new; |
166 | ||
167 | new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT, sizeof(struct vertex_parent)); | |
168 | ||
d62a17ae | 169 | new->parent = v; |
170 | new->backlink = backlink; | |
171 | new->nexthop = hop; | |
5ec5929c | 172 | |
d62a17ae | 173 | return new; |
718e3744 | 174 | } |
0c0f9cd5 | 175 | |
d62a17ae | 176 | static void vertex_parent_free(void *p) |
eb3da6df | 177 | { |
d62a17ae | 178 | XFREE(MTYPE_OSPF_VERTEX_PARENT, p); |
eb3da6df | 179 | } |
6b0655a2 | 180 | |
f32b6b9c DL |
181 | static int vertex_parent_cmp(void *aa, void *bb) |
182 | { | |
183 | struct vertex_parent *a = aa, *b = bb; | |
184 | return IPV4_ADDR_CMP(&a->nexthop->router, &b->nexthop->router); | |
185 | } | |
186 | ||
d62a17ae | 187 | static struct vertex *ospf_vertex_new(struct ospf_lsa *lsa) |
718e3744 | 188 | { |
d62a17ae | 189 | struct vertex *new; |
190 | ||
191 | new = XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex)); | |
192 | ||
193 | new->flags = 0; | |
d62a17ae | 194 | new->type = lsa->data->type; |
195 | new->id = lsa->data->id; | |
196 | new->lsa = lsa->data; | |
197 | new->children = list_new(); | |
198 | new->parents = list_new(); | |
199 | new->parents->del = vertex_parent_free; | |
f32b6b9c | 200 | new->parents->cmp = vertex_parent_cmp; |
c971918a DL |
201 | new->lsa_p = lsa; |
202 | ||
203 | lsa->stat = new; | |
d62a17ae | 204 | |
205 | listnode_add(&vertex_list, new); | |
206 | ||
207 | if (IS_DEBUG_OSPF_EVENT) | |
208 | zlog_debug("%s: Created %s vertex %s", __func__, | |
209 | new->type == OSPF_VERTEX_ROUTER ? "Router" | |
210 | : "Network", | |
211 | inet_ntoa(new->lsa->id)); | |
5ec5929c | 212 | |
d62a17ae | 213 | return new; |
718e3744 | 214 | } |
215 | ||
d62a17ae | 216 | static void ospf_vertex_free(void *data) |
718e3744 | 217 | { |
d62a17ae | 218 | struct vertex *v = data; |
219 | ||
220 | if (IS_DEBUG_OSPF_EVENT) | |
221 | zlog_debug("%s: Free %s vertex %s", __func__, | |
222 | v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network", | |
223 | inet_ntoa(v->lsa->id)); | |
224 | ||
d62a17ae | 225 | if (v->children) |
6a154c88 | 226 | list_delete(&v->children); |
d62a17ae | 227 | |
228 | if (v->parents) | |
6a154c88 | 229 | list_delete(&v->parents); |
d62a17ae | 230 | |
231 | v->lsa = NULL; | |
232 | ||
233 | XFREE(MTYPE_OSPF_VERTEX, v); | |
718e3744 | 234 | } |
235 | ||
d62a17ae | 236 | static void ospf_vertex_dump(const char *msg, struct vertex *v, |
237 | int print_parents, int print_children) | |
630e4807 | 238 | { |
d62a17ae | 239 | if (!IS_DEBUG_OSPF_EVENT) |
240 | return; | |
241 | ||
242 | zlog_debug("%s %s vertex %s distance %u flags %u", msg, | |
243 | v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network", | |
244 | inet_ntoa(v->lsa->id), v->distance, (unsigned int)v->flags); | |
245 | ||
246 | if (print_parents) { | |
247 | struct listnode *node; | |
248 | struct vertex_parent *vp; | |
249 | ||
250 | for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) { | |
251 | char buf1[BUFSIZ]; | |
252 | ||
253 | if (vp) { | |
254 | zlog_debug( | |
255 | "parent %s backlink %d nexthop %s interface %s", | |
256 | inet_ntoa(vp->parent->lsa->id), | |
257 | vp->backlink, | |
258 | inet_ntop(AF_INET, &vp->nexthop->router, | |
259 | buf1, BUFSIZ), | |
260 | vp->nexthop->oi | |
261 | ? IF_NAME(vp->nexthop->oi) | |
262 | : "NULL"); | |
263 | } | |
264 | } | |
265 | } | |
266 | ||
267 | if (print_children) { | |
268 | struct listnode *cnode; | |
269 | struct vertex *cv; | |
270 | ||
271 | for (ALL_LIST_ELEMENTS_RO(v->children, cnode, cv)) | |
272 | ospf_vertex_dump(" child:", cv, 0, 0); | |
630e4807 | 273 | } |
630e4807 | 274 | } |
275 | ||
276 | ||
277 | /* Add a vertex to the list of children in each of its parents. */ | |
d62a17ae | 278 | static void ospf_vertex_add_parent(struct vertex *v) |
718e3744 | 279 | { |
d62a17ae | 280 | struct vertex_parent *vp; |
281 | struct listnode *node; | |
282 | ||
283 | assert(v && v->parents); | |
284 | ||
285 | for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) { | |
286 | assert(vp->parent && vp->parent->children); | |
287 | ||
288 | /* No need to add two links from the same parent. */ | |
289 | if (listnode_lookup(vp->parent->children, v) == NULL) | |
290 | listnode_add(vp->parent->children, v); | |
291 | } | |
718e3744 | 292 | } |
6b0655a2 | 293 | |
5ec5929c | 294 | static void ospf_spf_init(struct ospf_area *area, struct ospf_lsa *root_lsa) |
718e3744 | 295 | { |
d62a17ae | 296 | struct vertex *v; |
297 | ||
298 | /* Create root node. */ | |
5ec5929c | 299 | v = ospf_vertex_new(root_lsa); |
d62a17ae | 300 | |
301 | area->spf = v; | |
302 | ||
303 | /* Reset ABR and ASBR router counts. */ | |
304 | area->abr_count = 0; | |
305 | area->asbr_count = 0; | |
718e3744 | 306 | } |
307 | ||
d355bfa7 | 308 | /* return index of link back to V from W, or -1 if no link found */ |
d62a17ae | 309 | static int ospf_lsa_has_link(struct lsa_header *w, struct lsa_header *v) |
718e3744 | 310 | { |
d62a17ae | 311 | unsigned int i, length; |
312 | struct router_lsa *rl; | |
313 | struct network_lsa *nl; | |
314 | ||
315 | /* In case of W is Network LSA. */ | |
316 | if (w->type == OSPF_NETWORK_LSA) { | |
317 | if (v->type == OSPF_NETWORK_LSA) | |
318 | return -1; | |
319 | ||
320 | nl = (struct network_lsa *)w; | |
321 | length = (ntohs(w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4; | |
322 | ||
323 | for (i = 0; i < length; i++) | |
324 | if (IPV4_ADDR_SAME(&nl->routers[i], &v->id)) | |
325 | return i; | |
326 | return -1; | |
327 | } | |
328 | ||
329 | /* In case of W is Router LSA. */ | |
330 | if (w->type == OSPF_ROUTER_LSA) { | |
331 | rl = (struct router_lsa *)w; | |
332 | ||
333 | length = ntohs(w->length); | |
334 | ||
335 | for (i = 0; i < ntohs(rl->links) | |
336 | && length >= sizeof(struct router_lsa); | |
337 | i++, length -= 12) { | |
338 | switch (rl->link[i].type) { | |
339 | case LSA_LINK_TYPE_POINTOPOINT: | |
340 | case LSA_LINK_TYPE_VIRTUALLINK: | |
341 | /* Router LSA ID. */ | |
342 | if (v->type == OSPF_ROUTER_LSA | |
343 | && IPV4_ADDR_SAME(&rl->link[i].link_id, | |
344 | &v->id)) { | |
345 | return i; | |
346 | } | |
347 | break; | |
348 | case LSA_LINK_TYPE_TRANSIT: | |
349 | /* Network LSA ID. */ | |
350 | if (v->type == OSPF_NETWORK_LSA | |
351 | && IPV4_ADDR_SAME(&rl->link[i].link_id, | |
352 | &v->id)) { | |
353 | return i; | |
354 | } | |
355 | break; | |
356 | case LSA_LINK_TYPE_STUB: | |
357 | /* Stub can't lead anywhere, carry on */ | |
358 | continue; | |
359 | default: | |
360 | break; | |
361 | } | |
362 | } | |
363 | } | |
364 | return -1; | |
718e3744 | 365 | } |
366 | ||
5ec5929c G |
367 | /* |
368 | * Find the next link after prev_link from v to w. If prev_link is | |
630e4807 | 369 | * NULL, return the first link from v to w. Ignore stub and virtual links; |
370 | * these link types will never be returned. | |
371 | */ | |
4dadc291 | 372 | static struct router_lsa_link * |
d62a17ae | 373 | ospf_get_next_link(struct vertex *v, struct vertex *w, |
374 | struct router_lsa_link *prev_link) | |
718e3744 | 375 | { |
d7c0a89a QY |
376 | uint8_t *p; |
377 | uint8_t *lim; | |
378 | uint8_t lsa_type = LSA_LINK_TYPE_TRANSIT; | |
d62a17ae | 379 | struct router_lsa_link *l; |
380 | ||
381 | if (w->type == OSPF_VERTEX_ROUTER) | |
382 | lsa_type = LSA_LINK_TYPE_POINTOPOINT; | |
383 | ||
384 | if (prev_link == NULL) | |
d7c0a89a | 385 | p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4; |
d62a17ae | 386 | else { |
d7c0a89a | 387 | p = (uint8_t *)prev_link; |
d62a17ae | 388 | p += (OSPF_ROUTER_LSA_LINK_SIZE |
389 | + (prev_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE)); | |
390 | } | |
0c0f9cd5 | 391 | |
d7c0a89a | 392 | lim = ((uint8_t *)v->lsa) + ntohs(v->lsa->length); |
718e3744 | 393 | |
d62a17ae | 394 | while (p < lim) { |
395 | l = (struct router_lsa_link *)p; | |
718e3744 | 396 | |
d62a17ae | 397 | p += (OSPF_ROUTER_LSA_LINK_SIZE |
398 | + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE)); | |
718e3744 | 399 | |
d62a17ae | 400 | if (l->m[0].type != lsa_type) |
401 | continue; | |
718e3744 | 402 | |
d62a17ae | 403 | if (IPV4_ADDR_SAME(&l->link_id, &w->id)) |
404 | return l; | |
405 | } | |
718e3744 | 406 | |
d62a17ae | 407 | return NULL; |
718e3744 | 408 | } |
409 | ||
d62a17ae | 410 | static void ospf_spf_flush_parents(struct vertex *w) |
bc20c1a4 | 411 | { |
d62a17ae | 412 | struct vertex_parent *vp; |
413 | struct listnode *ln, *nn; | |
414 | ||
415 | /* delete the existing nexthops */ | |
416 | for (ALL_LIST_ELEMENTS(w->parents, ln, nn, vp)) { | |
417 | list_delete_node(w->parents, ln); | |
418 | vertex_parent_free(vp); | |
419 | } | |
bc20c1a4 PJ |
420 | } |
421 | ||
d62a17ae | 422 | /* |
75ee0b8e | 423 | * Consider supplied next-hop for inclusion to the supplied list of |
d62a17ae | 424 | * equal-cost next-hops, adjust list as neccessary. |
bf9392c6 | 425 | */ |
d62a17ae | 426 | static void ospf_spf_add_parent(struct vertex *v, struct vertex *w, |
427 | struct vertex_nexthop *newhop, | |
428 | unsigned int distance) | |
bf9392c6 | 429 | { |
d62a17ae | 430 | struct vertex_parent *vp, *wp; |
431 | struct listnode *node; | |
432 | ||
433 | /* we must have a newhop, and a distance */ | |
434 | assert(v && w && newhop); | |
435 | assert(distance); | |
436 | ||
5ec5929c G |
437 | /* |
438 | * IFF w has already been assigned a distance, then we shouldn't get | |
439 | * here unless callers have determined V(l)->W is shortest / | |
440 | * equal-shortest path (0 is a special case distance (no distance yet | |
441 | * assigned)). | |
d62a17ae | 442 | */ |
443 | if (w->distance) | |
444 | assert(distance <= w->distance); | |
445 | else | |
446 | w->distance = distance; | |
447 | ||
448 | if (IS_DEBUG_OSPF_EVENT) { | |
449 | char buf[2][INET_ADDRSTRLEN]; | |
450 | zlog_debug( | |
451 | "%s: Adding %s as parent of %s", __func__, | |
452 | inet_ntop(AF_INET, &v->lsa->id, buf[0], sizeof(buf[0])), | |
453 | inet_ntop(AF_INET, &w->lsa->id, buf[1], | |
454 | sizeof(buf[1]))); | |
455 | } | |
456 | ||
5ec5929c G |
457 | /* |
458 | * Adding parent for a new, better path: flush existing parents from W. | |
d62a17ae | 459 | */ |
460 | if (distance < w->distance) { | |
461 | if (IS_DEBUG_OSPF_EVENT) | |
462 | zlog_debug( | |
463 | "%s: distance %d better than %d, flushing existing parents", | |
464 | __func__, distance, w->distance); | |
465 | ospf_spf_flush_parents(w); | |
466 | w->distance = distance; | |
467 | } | |
468 | ||
5ec5929c G |
469 | /* |
470 | * new parent is <= existing parents, add it to parent list (if nexthop | |
d62a17ae | 471 | * not on parent list) |
472 | */ | |
473 | for (ALL_LIST_ELEMENTS_RO(w->parents, node, wp)) { | |
474 | if (memcmp(newhop, wp->nexthop, sizeof(*newhop)) == 0) { | |
475 | if (IS_DEBUG_OSPF_EVENT) | |
476 | zlog_debug( | |
477 | "%s: ... nexthop already on parent list, skipping add", | |
478 | __func__); | |
479 | return; | |
480 | } | |
481 | } | |
7b92589c | 482 | |
d62a17ae | 483 | vp = vertex_parent_new(v, ospf_lsa_has_link(w->lsa, v->lsa), newhop); |
f32b6b9c | 484 | listnode_add_sort(w->parents, vp); |
0c0f9cd5 | 485 | |
d62a17ae | 486 | return; |
eb3da6df | 487 | } |
488 | ||
5ec5929c G |
489 | /* |
490 | * 16.1.1. Calculate nexthop from root through V (parent) to | |
bd34fb34 | 491 | * vertex W (destination), with given distance from root->W. |
eb3da6df | 492 | * |
493 | * The link must be supplied if V is the root vertex. In all other cases | |
494 | * it may be NULL. | |
bd34fb34 PJ |
495 | * |
496 | * Note that this function may fail, hence the state of the destination | |
497 | * vertex, W, should /not/ be modified in a dependent manner until | |
498 | * this function returns. This function will update the W vertex with the | |
499 | * provided distance as appropriate. | |
630e4807 | 500 | */ |
d62a17ae | 501 | static unsigned int ospf_nexthop_calculation(struct ospf_area *area, |
502 | struct vertex *v, struct vertex *w, | |
503 | struct router_lsa_link *l, | |
504 | unsigned int distance, int lsa_pos) | |
718e3744 | 505 | { |
d62a17ae | 506 | struct listnode *node, *nnode; |
507 | struct vertex_nexthop *nh; | |
508 | struct vertex_parent *vp; | |
509 | struct ospf_interface *oi = NULL; | |
510 | unsigned int added = 0; | |
511 | char buf1[BUFSIZ]; | |
512 | char buf2[BUFSIZ]; | |
513 | ||
514 | if (IS_DEBUG_OSPF_EVENT) { | |
515 | zlog_debug("ospf_nexthop_calculation(): Start"); | |
516 | ospf_vertex_dump("V (parent):", v, 1, 1); | |
517 | ospf_vertex_dump("W (dest) :", w, 1, 1); | |
518 | zlog_debug("V->W distance: %d", distance); | |
c81ee5c9 JT |
519 | } |
520 | ||
d62a17ae | 521 | if (v == area->spf) { |
5ec5929c G |
522 | /* |
523 | * 16.1.1 para 4. In the first case, the parent vertex (V) is | |
524 | * the root (the calculating router itself). This means that | |
525 | * the destination is either a directly connected network or | |
526 | * directly connected router. The outgoing interface in this | |
527 | * case is simply the OSPF interface connecting to the | |
528 | * destination network/router. | |
529 | */ | |
d62a17ae | 530 | |
531 | /* we *must* be supplied with the link data */ | |
532 | assert(l != NULL); | |
533 | oi = ospf_if_lookup_by_lsa_pos(area, lsa_pos); | |
534 | if (!oi) { | |
535 | zlog_debug( | |
536 | "%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s", | |
537 | __func__, lsa_pos, | |
538 | inet_ntop(AF_INET, &l->link_id, buf1, BUFSIZ), | |
539 | inet_ntop(AF_INET, &l->link_data, buf2, | |
540 | BUFSIZ)); | |
541 | return 0; | |
c81ee5c9 | 542 | } |
c81ee5c9 | 543 | |
d62a17ae | 544 | if (IS_DEBUG_OSPF_EVENT) { |
545 | zlog_debug( | |
3efd0893 | 546 | "%s: considering link:%s type:%d link_id:%s link_data:%s", |
d62a17ae | 547 | __func__, oi->ifp->name, l->m[0].type, |
548 | inet_ntop(AF_INET, &l->link_id, buf1, BUFSIZ), | |
549 | inet_ntop(AF_INET, &l->link_data, buf2, | |
550 | BUFSIZ)); | |
551 | } | |
c81ee5c9 | 552 | |
d62a17ae | 553 | if (w->type == OSPF_VERTEX_ROUTER) { |
5ec5929c G |
554 | /* |
555 | * l is a link from v to w l2 will be link from w to v | |
d62a17ae | 556 | */ |
557 | struct router_lsa_link *l2 = NULL; | |
558 | ||
559 | if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) { | |
560 | struct in_addr nexthop = {.s_addr = 0}; | |
561 | ||
5ec5929c G |
562 | /* |
563 | * If the destination is a router which connects | |
564 | * to the calculating router via a | |
565 | * Point-to-MultiPoint network, the | |
566 | * destination's next hop IP address(es) can be | |
567 | * determined by examining the destination's | |
568 | * router-LSA: each link pointing back to the | |
569 | * calculating router and having a Link Data | |
570 | * field belonging to the Point-to-MultiPoint | |
571 | * network provides an IP address of the next | |
572 | * hop router. | |
573 | * | |
574 | * At this point l is a link from V to W, and V | |
575 | * is the root ("us"). If it is a point-to- | |
576 | * multipoint interface, then look through the | |
577 | * links in the opposite direction (W to V). | |
578 | * If any of them have an address that lands | |
579 | * within the subnet declared by the PtMP link, | |
580 | * then that link is a constituent of the PtMP | |
581 | * link, and its address is a nexthop address | |
582 | * for V. | |
583 | */ | |
d62a17ae | 584 | if (oi->type == OSPF_IFTYPE_POINTOPOINT) { |
5ec5929c G |
585 | /* |
586 | * Having nexthop = 0 (as proposed in | |
587 | * the RFC) is tempting, but NOT | |
588 | * acceptable. It breaks AS-External | |
589 | * routes with a forwarding address, | |
590 | * since | |
591 | * ospf_ase_complete_direct_routes() | |
592 | * will mistakenly assume we've reached | |
593 | * the last hop and should place the | |
594 | * forwarding address as nexthop. Also, | |
595 | * users may configure multi-access | |
596 | * links in p2p mode, so we need the IP | |
597 | * to ARP the nexthop. | |
598 | */ | |
d62a17ae | 599 | struct ospf_neighbor *nbr_w; |
600 | ||
601 | nbr_w = ospf_nbr_lookup_by_routerid( | |
602 | oi->nbrs, &l->link_id); | |
603 | if (nbr_w != NULL) { | |
604 | added = 1; | |
605 | nexthop = nbr_w->src; | |
606 | } | |
607 | } else if (oi->type | |
608 | == OSPF_IFTYPE_POINTOMULTIPOINT) { | |
609 | struct prefix_ipv4 la; | |
610 | ||
611 | la.family = AF_INET; | |
612 | la.prefixlen = oi->address->prefixlen; | |
613 | ||
5ec5929c G |
614 | /* |
615 | * V links to W on PtMP interface; | |
616 | * find the interface address on W | |
617 | */ | |
d62a17ae | 618 | while ((l2 = ospf_get_next_link(w, v, |
619 | l2))) { | |
620 | la.prefix = l2->link_data; | |
621 | ||
622 | if (prefix_cmp((struct prefix | |
623 | *)&la, | |
624 | oi->address) | |
625 | != 0) | |
626 | continue; | |
5ec5929c G |
627 | |
628 | /* | |
629 | * link_data is on our PtMP | |
630 | * network | |
631 | */ | |
d62a17ae | 632 | added = 1; |
633 | nexthop = l2->link_data; | |
634 | break; | |
635 | } | |
636 | } | |
637 | ||
638 | if (added) { | |
5ec5929c G |
639 | /* |
640 | * found all necessary info to build | |
641 | * nexthop | |
642 | */ | |
d62a17ae | 643 | nh = vertex_nexthop_new(); |
644 | nh->oi = oi; | |
645 | nh->router = nexthop; | |
646 | ospf_spf_add_parent(v, w, nh, distance); | |
647 | return 1; | |
648 | } else | |
649 | zlog_info( | |
650 | "%s: could not determine nexthop for link %s", | |
651 | __func__, oi->ifp->name); | |
652 | } /* end point-to-point link from V to W */ | |
653 | else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK) { | |
654 | struct ospf_vl_data *vl_data; | |
655 | ||
5ec5929c G |
656 | /* |
657 | * VLink implementation limitations: | |
658 | * a) vl_data can only reference one nexthop, | |
659 | * so no ECMP to backbone through VLinks. | |
660 | * Though transit-area summaries may be | |
661 | * considered, and those can be ECMP. | |
d62a17ae | 662 | * b) We can only use /one/ VLink, even if |
5ec5929c G |
663 | * multiple ones exist this router through |
664 | * multiple transit-areas. | |
d62a17ae | 665 | */ |
666 | vl_data = ospf_vl_lookup(area->ospf, NULL, | |
667 | l->link_id); | |
668 | ||
669 | if (vl_data | |
670 | && CHECK_FLAG(vl_data->flags, | |
671 | OSPF_VL_FLAG_APPROVED)) { | |
672 | nh = vertex_nexthop_new(); | |
673 | nh->oi = vl_data->nexthop.oi; | |
674 | nh->router = vl_data->nexthop.router; | |
675 | ospf_spf_add_parent(v, w, nh, distance); | |
676 | return 1; | |
677 | } else | |
678 | zlog_info( | |
3efd0893 | 679 | "ospf_nexthop_calculation(): vl_data for VL link not found"); |
d62a17ae | 680 | } /* end virtual-link from V to W */ |
681 | return 0; | |
682 | } /* end W is a Router vertex */ | |
683 | else { | |
684 | assert(w->type == OSPF_VERTEX_NETWORK); | |
685 | ||
686 | nh = vertex_nexthop_new(); | |
687 | nh->oi = oi; | |
688 | nh->router.s_addr = 0; /* Nexthop not required */ | |
689 | ospf_spf_add_parent(v, w, nh, distance); | |
690 | return 1; | |
691 | } | |
692 | } /* end V is the root */ | |
693 | /* Check if W's parent is a network connected to root. */ | |
694 | else if (v->type == OSPF_VERTEX_NETWORK) { | |
695 | /* See if any of V's parents are the root. */ | |
696 | for (ALL_LIST_ELEMENTS(v->parents, node, nnode, vp)) { | |
5ec5929c G |
697 | if (vp->parent == area->spf) { |
698 | /* | |
699 | * 16.1.1 para 5. ...the parent vertex is a | |
700 | * network that directly connects the | |
701 | * calculating router to the destination | |
702 | * router. The list of next hops is then | |
703 | * determined by examining the destination's | |
704 | * router-LSA ... | |
d62a17ae | 705 | */ |
706 | ||
707 | assert(w->type == OSPF_VERTEX_ROUTER); | |
708 | while ((l = ospf_get_next_link(w, v, l))) { | |
5ec5929c G |
709 | /* |
710 | * ... For each link in the router-LSA | |
711 | * that points back to the parent | |
712 | * network, the link's Link Data field | |
713 | * provides the IP address of a next hop | |
714 | * router. The outgoing interface to use | |
715 | * can then be derived from the next | |
716 | * hop IP address (or it can be | |
717 | * inherited from the parent network). | |
d62a17ae | 718 | */ |
719 | nh = vertex_nexthop_new(); | |
720 | nh->oi = vp->nexthop->oi; | |
721 | nh->router = l->link_data; | |
722 | added = 1; | |
723 | ospf_spf_add_parent(v, w, nh, distance); | |
724 | } | |
5ec5929c G |
725 | /* |
726 | * Note lack of return is deliberate. See next | |
727 | * comment. | |
728 | */ | |
d62a17ae | 729 | } |
c81ee5c9 | 730 | } |
5ec5929c G |
731 | /* |
732 | * NB: This code is non-trivial. | |
d62a17ae | 733 | * |
734 | * E.g. it is not enough to know that V connects to the root. It | |
5ec5929c G |
735 | * is also important that the while above, looping through all |
736 | * links from W->V found at least one link, so that we know | |
737 | * there is bi-directional connectivity between V and W (which | |
738 | * need not be the case, e.g. when OSPF has not yet converged | |
739 | * fully). Otherwise, if we /always/ return here, without having | |
740 | * checked that root->V->-W actually resulted in a valid nexthop | |
741 | * being created, then we we will prevent SPF from finding/using | |
742 | * higher cost paths. | |
d62a17ae | 743 | * |
744 | * It is important, if root->V->W has not been added, that we | |
5ec5929c G |
745 | * continue through to the intervening-router nexthop code |
746 | * below. So as to ensure other paths to V may be used. This | |
747 | * avoids unnecessary blackholes while OSPF is converging. | |
d62a17ae | 748 | * |
749 | * I.e. we may have arrived at this function, examining V -> W, | |
5ec5929c G |
750 | * via workable paths other than root -> V, and it's important |
751 | * to avoid getting "confused" by non-working root->V->W path | |
752 | * - it's important to *not* lose the working non-root paths, | |
753 | * just because of a non-viable root->V->W. | |
d62a17ae | 754 | */ |
755 | if (added) | |
756 | return added; | |
757 | } | |
c81ee5c9 | 758 | |
5ec5929c G |
759 | /* |
760 | * 16.1.1 para 4. If there is at least one intervening router in the | |
d62a17ae | 761 | * current shortest path between the destination and the root, the |
762 | * destination simply inherits the set of next hops from the | |
763 | * parent. | |
764 | */ | |
765 | if (IS_DEBUG_OSPF_EVENT) | |
766 | zlog_debug("%s: Intervening routers, adding parent(s)", | |
767 | __func__); | |
768 | ||
769 | for (ALL_LIST_ELEMENTS(v->parents, node, nnode, vp)) { | |
770 | added = 1; | |
771 | ospf_spf_add_parent(v, w, vp->nexthop, distance); | |
772 | } | |
c81ee5c9 | 773 | |
d62a17ae | 774 | return added; |
718e3744 | 775 | } |
776 | ||
5ec5929c G |
777 | /* |
778 | * RFC2328 16.1 (2). | |
779 | * v is on the SPF tree. Examine the links in v's LSA. Update the list of | |
780 | * candidates with any vertices not already on the list. If a lower-cost path | |
781 | * is found to a vertex already on the candidate list, store the new cost. | |
630e4807 | 782 | */ |
5ec5929c | 783 | static void ospf_spf_next(struct vertex *v, struct ospf_area *area, |
c971918a | 784 | struct vertex_pqueue_head *candidate) |
718e3744 | 785 | { |
d62a17ae | 786 | struct ospf_lsa *w_lsa = NULL; |
d7c0a89a QY |
787 | uint8_t *p; |
788 | uint8_t *lim; | |
d62a17ae | 789 | struct router_lsa_link *l = NULL; |
790 | struct in_addr *r; | |
791 | int type = 0, lsa_pos = -1, lsa_pos_next = 0; | |
792 | ||
5ec5929c G |
793 | /* |
794 | * If this is a router-LSA, and bit V of the router-LSA (see Section | |
795 | * A.4.2:RFC2328) is set, set Area A's TransitCapability to true. | |
796 | */ | |
d62a17ae | 797 | if (v->type == OSPF_VERTEX_ROUTER) { |
798 | if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa *)v->lsa)) | |
799 | area->transit = OSPF_TRANSIT_TRUE; | |
800 | } | |
718e3744 | 801 | |
d62a17ae | 802 | if (IS_DEBUG_OSPF_EVENT) |
803 | zlog_debug("%s: Next vertex of %s vertex %s", __func__, | |
804 | v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network", | |
805 | inet_ntoa(v->lsa->id)); | |
806 | ||
d7c0a89a QY |
807 | p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4; |
808 | lim = ((uint8_t *)v->lsa) + ntohs(v->lsa->length); | |
d62a17ae | 809 | |
810 | while (p < lim) { | |
811 | struct vertex *w; | |
812 | unsigned int distance; | |
813 | ||
814 | /* In case of V is Router-LSA. */ | |
815 | if (v->lsa->type == OSPF_ROUTER_LSA) { | |
816 | l = (struct router_lsa_link *)p; | |
817 | ||
818 | lsa_pos = lsa_pos_next; /* LSA link position */ | |
819 | lsa_pos_next++; | |
820 | p += (OSPF_ROUTER_LSA_LINK_SIZE | |
821 | + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE)); | |
822 | ||
5ec5929c G |
823 | /* |
824 | * (a) If this is a link to a stub network, examine the | |
825 | * next link in V's LSA. Links to stub networks will | |
826 | * be considered in the second stage of the shortest | |
827 | * path calculation. | |
828 | */ | |
d62a17ae | 829 | if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB) |
830 | continue; | |
831 | ||
5ec5929c G |
832 | /* |
833 | * (b) Otherwise, W is a transit vertex (router or | |
834 | * transit network). Look up the vertex W's LSA | |
835 | * (router-LSA or network-LSA) in Area A's link state | |
836 | * database. | |
837 | */ | |
d62a17ae | 838 | switch (type) { |
839 | case LSA_LINK_TYPE_POINTOPOINT: | |
840 | case LSA_LINK_TYPE_VIRTUALLINK: | |
5ec5929c G |
841 | if (type == LSA_LINK_TYPE_VIRTUALLINK |
842 | && IS_DEBUG_OSPF_EVENT) | |
843 | zlog_debug( | |
844 | "looking up LSA through VL: %s", | |
845 | inet_ntoa(l->link_id)); | |
846 | w_lsa = ospf_lsa_lookup(area->ospf, area, | |
b5a8894d | 847 | OSPF_ROUTER_LSA, |
d62a17ae | 848 | l->link_id, l->link_id); |
5ec5929c G |
849 | if (w_lsa && IS_DEBUG_OSPF_EVENT) |
850 | zlog_debug("found Router LSA %s", | |
851 | inet_ntoa(l->link_id)); | |
d62a17ae | 852 | break; |
853 | case LSA_LINK_TYPE_TRANSIT: | |
854 | if (IS_DEBUG_OSPF_EVENT) | |
855 | zlog_debug( | |
856 | "Looking up Network LSA, ID: %s", | |
857 | inet_ntoa(l->link_id)); | |
858 | w_lsa = ospf_lsa_lookup_by_id( | |
859 | area, OSPF_NETWORK_LSA, l->link_id); | |
5ec5929c G |
860 | if (w_lsa && IS_DEBUG_OSPF_EVENT) |
861 | zlog_debug("found the LSA"); | |
d62a17ae | 862 | break; |
863 | default: | |
cf444bcf | 864 | flog_warn(EC_OSPF_LSA, |
668e8a11 | 865 | "Invalid LSA link type %d", type); |
d62a17ae | 866 | continue; |
867 | } | |
3239e3ca DL |
868 | |
869 | /* step (d) below */ | |
870 | distance = v->distance + ntohs(l->m[0].metric); | |
d62a17ae | 871 | } else { |
872 | /* In case of V is Network-LSA. */ | |
873 | r = (struct in_addr *)p; | |
874 | p += sizeof(struct in_addr); | |
875 | ||
876 | /* Lookup the vertex W's LSA. */ | |
877 | w_lsa = ospf_lsa_lookup_by_id(area, OSPF_ROUTER_LSA, | |
878 | *r); | |
5ec5929c G |
879 | if (w_lsa && IS_DEBUG_OSPF_EVENT) |
880 | zlog_debug("found Router LSA %s", | |
881 | inet_ntoa(w_lsa->data->id)); | |
3239e3ca DL |
882 | |
883 | /* step (d) below */ | |
884 | distance = v->distance; | |
d62a17ae | 885 | } |
718e3744 | 886 | |
5ec5929c G |
887 | /* |
888 | * (b cont.) If the LSA does not exist, or its LS age is equal | |
889 | * to MaxAge, or it does not have a link back to vertex V, | |
890 | * examine the next link in V's LSA.[23] | |
891 | */ | |
d62a17ae | 892 | if (w_lsa == NULL) { |
893 | if (IS_DEBUG_OSPF_EVENT) | |
894 | zlog_debug("No LSA found"); | |
895 | continue; | |
896 | } | |
718e3744 | 897 | |
d62a17ae | 898 | if (IS_LSA_MAXAGE(w_lsa)) { |
899 | if (IS_DEBUG_OSPF_EVENT) | |
900 | zlog_debug("LSA is MaxAge"); | |
901 | continue; | |
902 | } | |
718e3744 | 903 | |
d62a17ae | 904 | if (ospf_lsa_has_link(w_lsa->data, v->lsa) < 0) { |
905 | if (IS_DEBUG_OSPF_EVENT) | |
906 | zlog_debug("The LSA doesn't have a link back"); | |
907 | continue; | |
908 | } | |
718e3744 | 909 | |
5ec5929c G |
910 | /* |
911 | * (c) If vertex W is already on the shortest-path tree, examine | |
912 | * the next link in the LSA. | |
913 | */ | |
d62a17ae | 914 | if (w_lsa->stat == LSA_SPF_IN_SPFTREE) { |
915 | if (IS_DEBUG_OSPF_EVENT) | |
916 | zlog_debug("The LSA is already in SPF"); | |
917 | continue; | |
918 | } | |
718e3744 | 919 | |
5ec5929c G |
920 | /* |
921 | * (d) Calculate the link state cost D of the resulting path | |
922 | * from the root to vertex W. D is equal to the sum of the link | |
923 | * state cost of the (already calculated) shortest path to | |
924 | * vertex V and the advertised cost of the link between vertices | |
925 | * V and W. If D is: | |
926 | */ | |
d62a17ae | 927 | |
3239e3ca | 928 | /* calculate link cost D -- moved above */ |
d62a17ae | 929 | |
930 | /* Is there already vertex W in candidate list? */ | |
931 | if (w_lsa->stat == LSA_SPF_NOT_EXPLORED) { | |
932 | /* prepare vertex W. */ | |
933 | w = ospf_vertex_new(w_lsa); | |
934 | ||
935 | /* Calculate nexthop to W. */ | |
936 | if (ospf_nexthop_calculation(area, v, w, l, distance, | |
937 | lsa_pos)) | |
c971918a | 938 | vertex_pqueue_add(candidate, w); |
d62a17ae | 939 | else if (IS_DEBUG_OSPF_EVENT) |
940 | zlog_debug("Nexthop Calc failed"); | |
c971918a DL |
941 | } else if (w_lsa->stat != LSA_SPF_IN_SPFTREE) { |
942 | w = w_lsa->stat; | |
d62a17ae | 943 | if (w->distance < distance) { |
944 | continue; | |
945 | } | |
d62a17ae | 946 | else if (w->distance == distance) { |
5ec5929c G |
947 | /* |
948 | * Found an equal-cost path to W. | |
949 | * Calculate nexthop of to W from V. | |
950 | */ | |
d62a17ae | 951 | ospf_nexthop_calculation(area, v, w, l, |
952 | distance, lsa_pos); | |
953 | } | |
d62a17ae | 954 | else { |
5ec5929c G |
955 | /* |
956 | * Found a lower-cost path to W. | |
d62a17ae | 957 | * nexthop_calculation is conditional, if it |
5ec5929c G |
958 | * finds valid nexthop it will call |
959 | * spf_add_parents, which will flush the old | |
960 | * parents. | |
d62a17ae | 961 | */ |
c971918a DL |
962 | vertex_pqueue_del(candidate, w); |
963 | ospf_nexthop_calculation(area, v, w, l, | |
964 | distance, lsa_pos); | |
965 | vertex_pqueue_add(candidate, w); | |
d62a17ae | 966 | } |
967 | } /* end W is already on the candidate list */ | |
968 | } /* end loop over the links in V's LSA */ | |
969 | } | |
718e3744 | 970 | |
d62a17ae | 971 | static void ospf_spf_dump(struct vertex *v, int i) |
972 | { | |
973 | struct listnode *cnode; | |
974 | struct listnode *nnode; | |
975 | struct vertex_parent *parent; | |
976 | ||
977 | if (v->type == OSPF_VERTEX_ROUTER) { | |
978 | if (IS_DEBUG_OSPF_EVENT) | |
979 | zlog_debug("SPF Result: %d [R] %s", i, | |
980 | inet_ntoa(v->lsa->id)); | |
981 | } else { | |
982 | struct network_lsa *lsa = (struct network_lsa *)v->lsa; | |
983 | if (IS_DEBUG_OSPF_EVENT) | |
984 | zlog_debug("SPF Result: %d [N] %s/%d", i, | |
985 | inet_ntoa(v->lsa->id), | |
986 | ip_masklen(lsa->mask)); | |
462f20d5 | 987 | } |
718e3744 | 988 | |
d62a17ae | 989 | if (IS_DEBUG_OSPF_EVENT) |
990 | for (ALL_LIST_ELEMENTS_RO(v->parents, nnode, parent)) { | |
991 | zlog_debug(" nexthop %p %s %s", (void *)parent->nexthop, | |
992 | inet_ntoa(parent->nexthop->router), | |
993 | parent->nexthop->oi | |
994 | ? IF_NAME(parent->nexthop->oi) | |
995 | : "NULL"); | |
996 | } | |
718e3744 | 997 | |
d62a17ae | 998 | i++; |
718e3744 | 999 | |
d62a17ae | 1000 | for (ALL_LIST_ELEMENTS_RO(v->children, cnode, v)) |
1001 | ospf_spf_dump(v, i); | |
718e3744 | 1002 | } |
1003 | ||
1004 | /* Second stage of SPF calculation. */ | |
d62a17ae | 1005 | static void ospf_spf_process_stubs(struct ospf_area *area, struct vertex *v, |
1006 | struct route_table *rt, int parent_is_root) | |
718e3744 | 1007 | { |
d62a17ae | 1008 | struct listnode *cnode, *cnnode; |
1009 | struct vertex *child; | |
1010 | ||
1011 | if (IS_DEBUG_OSPF_EVENT) | |
1012 | zlog_debug("ospf_process_stub():processing stubs for area %s", | |
1013 | inet_ntoa(area->area_id)); | |
5ec5929c | 1014 | |
d62a17ae | 1015 | if (v->type == OSPF_VERTEX_ROUTER) { |
d7c0a89a QY |
1016 | uint8_t *p; |
1017 | uint8_t *lim; | |
d62a17ae | 1018 | struct router_lsa_link *l; |
5ec5929c | 1019 | struct router_lsa *router_lsa; |
d62a17ae | 1020 | int lsa_pos = 0; |
1021 | ||
1022 | if (IS_DEBUG_OSPF_EVENT) | |
1023 | zlog_debug( | |
1024 | "ospf_process_stubs():processing router LSA, id: %s", | |
1025 | inet_ntoa(v->lsa->id)); | |
d62a17ae | 1026 | |
5ec5929c | 1027 | router_lsa = (struct router_lsa *)v->lsa; |
d62a17ae | 1028 | |
1029 | if (IS_DEBUG_OSPF_EVENT) | |
1030 | zlog_debug( | |
1031 | "ospf_process_stubs(): we have %d links to process", | |
5ec5929c G |
1032 | ntohs(router_lsa->links)); |
1033 | ||
d7c0a89a QY |
1034 | p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4; |
1035 | lim = ((uint8_t *)v->lsa) + ntohs(v->lsa->length); | |
d62a17ae | 1036 | |
1037 | while (p < lim) { | |
1038 | l = (struct router_lsa_link *)p; | |
1039 | ||
1040 | p += (OSPF_ROUTER_LSA_LINK_SIZE | |
1041 | + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE)); | |
1042 | ||
1043 | if (l->m[0].type == LSA_LINK_TYPE_STUB) | |
1044 | ospf_intra_add_stub(rt, l, v, area, | |
1045 | parent_is_root, lsa_pos); | |
1046 | lsa_pos++; | |
1047 | } | |
1048 | } | |
718e3744 | 1049 | |
d62a17ae | 1050 | ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1, |
1051 | 1); | |
718e3744 | 1052 | |
d62a17ae | 1053 | for (ALL_LIST_ELEMENTS(v->children, cnode, cnnode, child)) { |
1054 | if (CHECK_FLAG(child->flags, OSPF_VERTEX_PROCESSED)) | |
1055 | continue; | |
718e3744 | 1056 | |
5ec5929c G |
1057 | /* |
1058 | * The first level of routers connected to the root | |
d62a17ae | 1059 | * should have 'parent_is_root' set, including those |
1060 | * connected via a network vertex. | |
1061 | */ | |
1062 | if (area->spf == v) | |
1063 | parent_is_root = 1; | |
1064 | else if (v->type == OSPF_VERTEX_ROUTER) | |
1065 | parent_is_root = 0; | |
1066 | ||
1067 | ospf_spf_process_stubs(area, child, rt, parent_is_root); | |
1068 | ||
1069 | SET_FLAG(child->flags, OSPF_VERTEX_PROCESSED); | |
1070 | } | |
718e3744 | 1071 | } |
1072 | ||
d62a17ae | 1073 | void ospf_rtrs_free(struct route_table *rtrs) |
718e3744 | 1074 | { |
d62a17ae | 1075 | struct route_node *rn; |
1076 | struct list *or_list; | |
1077 | struct ospf_route * or ; | |
1078 | struct listnode *node, *nnode; | |
718e3744 | 1079 | |
d62a17ae | 1080 | if (IS_DEBUG_OSPF_EVENT) |
1081 | zlog_debug("Route: Router Routing Table free"); | |
718e3744 | 1082 | |
d62a17ae | 1083 | for (rn = route_top(rtrs); rn; rn = route_next(rn)) |
1084 | if ((or_list = rn->info) != NULL) { | |
1085 | for (ALL_LIST_ELEMENTS(or_list, node, nnode, or)) | |
1086 | ospf_route_free(or); | |
718e3744 | 1087 | |
6a154c88 | 1088 | list_delete(&or_list); |
718e3744 | 1089 | |
d62a17ae | 1090 | /* Unlock the node. */ |
1091 | rn->info = NULL; | |
1092 | route_unlock_node(rn); | |
1093 | } | |
5ec5929c | 1094 | |
d62a17ae | 1095 | route_table_finish(rtrs); |
718e3744 | 1096 | } |
1097 | ||
075e12f5 | 1098 | #if 0 |
4dadc291 | 1099 | static void |
718e3744 | 1100 | ospf_rtrs_print (struct route_table *rtrs) |
1101 | { | |
1102 | struct route_node *rn; | |
52dc7ee6 | 1103 | struct list *or_list; |
1104 | struct listnode *ln; | |
1105 | struct listnode *pnode; | |
718e3744 | 1106 | struct ospf_route *or; |
1107 | struct ospf_path *path; | |
1108 | char buf1[BUFSIZ]; | |
1109 | char buf2[BUFSIZ]; | |
1110 | ||
1111 | if (IS_DEBUG_OSPF_EVENT) | |
2a42e285 | 1112 | zlog_debug ("ospf_rtrs_print() start"); |
718e3744 | 1113 | |
1114 | for (rn = route_top (rtrs); rn; rn = route_next (rn)) | |
1115 | if ((or_list = rn->info) != NULL) | |
1eb8ef25 | 1116 | for (ALL_LIST_ELEMENTS_RO (or_list, ln, or)) |
718e3744 | 1117 | { |
718e3744 | 1118 | switch (or->path_type) |
1119 | { | |
1120 | case OSPF_PATH_INTRA_AREA: | |
0c0f9cd5 | 1121 | if (IS_DEBUG_OSPF_EVENT) |
2a42e285 | 1122 | zlog_debug ("%s [%d] area: %s", |
0c0f9cd5 | 1123 | inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), |
1124 | or->cost, inet_ntop (AF_INET, &or->u.std.area_id, | |
1125 | buf2, BUFSIZ)); | |
718e3744 | 1126 | break; |
1127 | case OSPF_PATH_INTER_AREA: | |
0c0f9cd5 | 1128 | if (IS_DEBUG_OSPF_EVENT) |
2a42e285 | 1129 | zlog_debug ("%s IA [%d] area: %s", |
0c0f9cd5 | 1130 | inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), |
1131 | or->cost, inet_ntop (AF_INET, &or->u.std.area_id, | |
1132 | buf2, BUFSIZ)); | |
718e3744 | 1133 | break; |
1134 | default: | |
1135 | break; | |
1136 | } | |
1137 | ||
1eb8ef25 | 1138 | for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path)) |
718e3744 | 1139 | { |
718e3744 | 1140 | if (path->nexthop.s_addr == 0) |
0c0f9cd5 | 1141 | { |
1142 | if (IS_DEBUG_OSPF_EVENT) | |
9165c5f5 | 1143 | zlog_debug (" directly attached to %s\r", |
baaea325 | 1144 | ifindex2ifname (path->ifindex), VRF_DEFAULT); |
0c0f9cd5 | 1145 | } |
1146 | else | |
1147 | { | |
1148 | if (IS_DEBUG_OSPF_EVENT) | |
9165c5f5 | 1149 | zlog_debug (" via %s, %s\r", |
a8ba847f | 1150 | inet_ntoa (path->nexthop), |
baaea325 | 1151 | ifindex2ifname (path->ifindex), VRF_DEFAULT); |
0c0f9cd5 | 1152 | } |
718e3744 | 1153 | } |
1154 | } | |
1155 | ||
2a42e285 | 1156 | zlog_debug ("ospf_rtrs_print() end"); |
718e3744 | 1157 | } |
075e12f5 | 1158 | #endif |
718e3744 | 1159 | |
5ec5929c G |
1160 | /* Calculating the shortest-path tree for an area, see RFC2328 16.1. */ |
1161 | static void ospf_spf_calculate(struct ospf_area *area, | |
1162 | struct ospf_lsa *root_lsa, | |
d62a17ae | 1163 | struct route_table *new_table, |
1164 | struct route_table *new_rtrs) | |
718e3744 | 1165 | { |
c971918a | 1166 | struct vertex_pqueue_head candidate; |
d62a17ae | 1167 | struct vertex *v; |
718e3744 | 1168 | |
d62a17ae | 1169 | if (IS_DEBUG_OSPF_EVENT) { |
1170 | zlog_debug("ospf_spf_calculate: Start"); | |
1171 | zlog_debug("ospf_spf_calculate: running Dijkstra for area %s", | |
1172 | inet_ntoa(area->area_id)); | |
1173 | } | |
718e3744 | 1174 | |
5ec5929c G |
1175 | /* |
1176 | * If the router LSA of the root is not yet allocated, return this | |
1177 | * area's calculation. In the 'usual' case the root_lsa is the | |
1178 | * self-originated router LSA of the node itself. | |
1179 | */ | |
1180 | if (!root_lsa) { | |
d62a17ae | 1181 | if (IS_DEBUG_OSPF_EVENT) |
1182 | zlog_debug( | |
5ec5929c | 1183 | "ospf_spf_calculate: Skip area %s's calculation due to empty root LSA", |
d62a17ae | 1184 | inet_ntoa(area->area_id)); |
1185 | return; | |
1186 | } | |
718e3744 | 1187 | |
5ec5929c | 1188 | /* Initialize the algorithm's data structures, see RFC2328 16.1. (1). */ |
d62a17ae | 1189 | |
5ec5929c G |
1190 | /* |
1191 | * This function scans all the LSA database and set the stat field to | |
1192 | * LSA_SPF_NOT_EXPLORED. | |
1193 | */ | |
c971918a | 1194 | lsdb_clean_stat(area->lsdb); |
5ec5929c | 1195 | |
d62a17ae | 1196 | /* Create a new heap for the candidates. */ |
c971918a | 1197 | vertex_pqueue_init(&candidate); |
d62a17ae | 1198 | |
5ec5929c G |
1199 | /* |
1200 | * Initialize the shortest-path tree to only the root (which is usually | |
1201 | * the router doing the calculation). | |
1202 | */ | |
1203 | ospf_spf_init(area, root_lsa); | |
d62a17ae | 1204 | |
2951a7a4 | 1205 | /* Set Area A's TransitCapability to false. */ |
d62a17ae | 1206 | area->transit = OSPF_TRANSIT_FALSE; |
1207 | area->shortcut_capability = 1; | |
1208 | ||
5ec5929c G |
1209 | /* |
1210 | * Use the root vertex for the start of the SPF algorithm and make it | |
1211 | * part of the tree. | |
1212 | */ | |
1213 | v = area->spf; | |
1214 | v->lsa_p->stat = LSA_SPF_IN_SPFTREE; | |
1215 | ||
d62a17ae | 1216 | for (;;) { |
1217 | /* RFC2328 16.1. (2). */ | |
5ec5929c | 1218 | ospf_spf_next(v, area, &candidate); |
d62a17ae | 1219 | |
1220 | /* RFC2328 16.1. (3). */ | |
c971918a DL |
1221 | v = vertex_pqueue_pop(&candidate); |
1222 | if (!v) | |
5ec5929c | 1223 | /* No more vertices left. */ |
c971918a | 1224 | break; |
5ec5929c | 1225 | |
c971918a | 1226 | v->lsa_p->stat = LSA_SPF_IN_SPFTREE; |
d62a17ae | 1227 | |
1228 | ospf_vertex_add_parent(v); | |
1229 | ||
1230 | /* RFC2328 16.1. (4). */ | |
1231 | if (v->type == OSPF_VERTEX_ROUTER) | |
1232 | ospf_intra_add_router(new_rtrs, v, area); | |
1233 | else | |
1234 | ospf_intra_add_transit(new_table, v, area); | |
1235 | ||
5ec5929c G |
1236 | /* Iterate back to (2), see RFC2328 16.1. (5). */ |
1237 | } | |
d62a17ae | 1238 | |
1239 | if (IS_DEBUG_OSPF_EVENT) { | |
1240 | ospf_spf_dump(area->spf, 0); | |
1241 | ospf_route_table_dump(new_table); | |
1242 | } | |
cf744958 | 1243 | |
5ec5929c G |
1244 | /* |
1245 | * Second stage of SPF calculation procedure's, add leaves to the tree | |
1246 | * for stub networks. | |
1247 | */ | |
d62a17ae | 1248 | ospf_spf_process_stubs(area, area->spf, new_table, 0); |
cf744958 | 1249 | |
d62a17ae | 1250 | ospf_vertex_dump(__func__, area->spf, 0, 1); |
5ec5929c G |
1251 | /* |
1252 | * Free nexthop information, canonical versions of which are attached | |
d62a17ae | 1253 | * the first level of router vertices attached to the root vertex, see |
1254 | * ospf_nexthop_calculation. | |
1255 | */ | |
1256 | ospf_canonical_nexthops_free(area->spf); | |
718e3744 | 1257 | |
d62a17ae | 1258 | /* Increment SPF Calculation Counter. */ |
1259 | area->spf_calculation++; | |
1260 | ||
1261 | monotime(&area->ospf->ts_spf); | |
1262 | area->ts_spf = area->ospf->ts_spf; | |
cf744958 | 1263 | |
d62a17ae | 1264 | if (IS_DEBUG_OSPF_EVENT) |
1265 | zlog_debug("ospf_spf_calculate: Stop. %zd vertices", | |
1266 | mtype_stats_alloc(MTYPE_OSPF_VERTEX)); | |
1267 | ||
5ec5929c G |
1268 | /* |
1269 | * Free SPF vertices, but not the list. List has ospf_vertex_free | |
d62a17ae | 1270 | * as deconstructor. |
1271 | */ | |
1272 | list_delete_all_node(&vertex_list); | |
718e3744 | 1273 | } |
6b0655a2 | 1274 | |
5ec5929c G |
1275 | static int ospf_spf_calculate_areas(struct ospf *ospf, |
1276 | struct route_table *new_table, | |
1277 | struct route_table *new_rtrs) | |
718e3744 | 1278 | { |
d62a17ae | 1279 | struct ospf_area *area; |
1280 | struct listnode *node, *nnode; | |
d62a17ae | 1281 | int areas_processed = 0; |
d62a17ae | 1282 | |
1283 | /* Calculate SPF for each area. */ | |
1284 | for (ALL_LIST_ELEMENTS(ospf->areas, node, nnode, area)) { | |
1285 | /* Do backbone last, so as to first discover intra-area paths | |
5ec5929c | 1286 | * for any back-bone virtual-links */ |
d62a17ae | 1287 | if (ospf->backbone && ospf->backbone == area) |
1288 | continue; | |
cf744958 | 1289 | |
5ec5929c G |
1290 | ospf_spf_calculate(area, area->router_lsa_self, new_table, |
1291 | new_rtrs); | |
d62a17ae | 1292 | areas_processed++; |
1293 | } | |
1294 | ||
1295 | /* SPF for backbone, if required */ | |
1296 | if (ospf->backbone) { | |
5ec5929c G |
1297 | area = ospf->backbone; |
1298 | ospf_spf_calculate(area, area->router_lsa_self, new_table, | |
1299 | new_rtrs); | |
d62a17ae | 1300 | areas_processed++; |
1301 | } | |
1302 | ||
5ec5929c G |
1303 | return areas_processed; |
1304 | } | |
1305 | ||
1306 | /* Worker for SPF calculation scheduler. */ | |
1307 | static int ospf_spf_calculate_schedule_worker(struct thread *thread) | |
1308 | { | |
1309 | struct ospf *ospf = THREAD_ARG(thread); | |
1310 | struct route_table *new_table, *new_rtrs; | |
1311 | struct timeval start_time, spf_start_time; | |
1312 | int areas_processed; | |
1313 | unsigned long ia_time, prune_time, rt_time; | |
1314 | unsigned long abr_time, total_spf_time, spf_time; | |
1315 | char rbuf[32]; /* reason_buf */ | |
1316 | ||
1317 | if (IS_DEBUG_OSPF_EVENT) | |
1318 | zlog_debug("SPF: Timer (SPF calculation expire)"); | |
1319 | ||
1320 | ospf->t_spf_calc = NULL; | |
1321 | ||
1322 | ospf_vl_unapprove(ospf); | |
1323 | ||
1324 | /* Execute SPF for each area including backbone, see RFC 2328 16.1. */ | |
1325 | monotime(&spf_start_time); | |
1326 | new_table = route_table_init(); /* routing table */ | |
1327 | new_rtrs = route_table_init(); /* ABR/ASBR routing table */ | |
1328 | areas_processed = ospf_spf_calculate_areas(ospf, new_table, new_rtrs); | |
d62a17ae | 1329 | spf_time = monotime_since(&spf_start_time, NULL); |
1330 | ||
1331 | ospf_vl_shut_unapproved(ospf); | |
1332 | ||
5ec5929c | 1333 | /* Calculate inter-area routes, see RFC 2328 16.2. */ |
d62a17ae | 1334 | monotime(&start_time); |
1335 | ospf_ia_routing(ospf, new_table, new_rtrs); | |
1336 | ia_time = monotime_since(&start_time, NULL); | |
1337 | ||
5ec5929c | 1338 | /* Get rid of transit networks and routers we cannot reach anyway. */ |
d62a17ae | 1339 | monotime(&start_time); |
1340 | ospf_prune_unreachable_networks(new_table); | |
1341 | ospf_prune_unreachable_routers(new_rtrs); | |
1342 | prune_time = monotime_since(&start_time, NULL); | |
1343 | ||
5ec5929c | 1344 | /* Note: RFC 2328 16.3. is apparently missing. */ |
d62a17ae | 1345 | |
5ec5929c G |
1346 | /* |
1347 | * Calculate AS external routes, see RFC 2328 16.4. | |
1348 | * There is a dedicated routing table for external routes which is not | |
1349 | * handled here directly | |
1350 | */ | |
1351 | ospf_ase_calculate_schedule(ospf); | |
d62a17ae | 1352 | ospf_ase_calculate_timer_add(ospf); |
1353 | ||
b5a8894d | 1354 | if (IS_DEBUG_OSPF_EVENT) |
996c9314 LB |
1355 | zlog_debug( |
1356 | "%s: ospf install new route, vrf %s id %u new_table count %lu", | |
5e81f5dd | 1357 | __func__, ospf_vrf_id_to_name(ospf->vrf_id), |
996c9314 | 1358 | ospf->vrf_id, new_table->count); |
5ec5929c | 1359 | |
d62a17ae | 1360 | /* Update routing table. */ |
1361 | monotime(&start_time); | |
1362 | ospf_route_install(ospf, new_table); | |
1363 | rt_time = monotime_since(&start_time, NULL); | |
1364 | ||
5ec5929c G |
1365 | /* Free old ABR/ASBR routing table */ |
1366 | if (ospf->old_rtrs) | |
d62a17ae | 1367 | /* ospf_route_delete (ospf->old_rtrs); */ |
1368 | ospf_rtrs_free(ospf->old_rtrs); | |
d62a17ae | 1369 | |
5ec5929c | 1370 | /* Update ABR/ASBR routing table */ |
d62a17ae | 1371 | ospf->old_rtrs = ospf->new_rtrs; |
1372 | ospf->new_rtrs = new_rtrs; | |
1373 | ||
5ec5929c | 1374 | /* ABRs may require additional changes, see RFC 2328 16.7. */ |
d62a17ae | 1375 | monotime(&start_time); |
1376 | if (IS_OSPF_ABR(ospf)) | |
1377 | ospf_abr_task(ospf); | |
1378 | abr_time = monotime_since(&start_time, NULL); | |
1379 | ||
cf9b9f77 | 1380 | /* Schedule Segment Routing update */ |
b37eb79c | 1381 | ospf_sr_update_task(ospf); |
cf9b9f77 | 1382 | |
d62a17ae | 1383 | total_spf_time = |
1384 | monotime_since(&spf_start_time, &ospf->ts_spf_duration); | |
1385 | ||
1386 | rbuf[0] = '\0'; | |
1387 | if (spf_reason_flags) { | |
1388 | if (spf_reason_flags & SPF_FLAG_ROUTER_LSA_INSTALL) | |
1389 | strncat(rbuf, "R, ", sizeof(rbuf) - strlen(rbuf) - 1); | |
1390 | if (spf_reason_flags & SPF_FLAG_NETWORK_LSA_INSTALL) | |
1391 | strncat(rbuf, "N, ", sizeof(rbuf) - strlen(rbuf) - 1); | |
1392 | if (spf_reason_flags & SPF_FLAG_SUMMARY_LSA_INSTALL) | |
1393 | strncat(rbuf, "S, ", sizeof(rbuf) - strlen(rbuf) - 1); | |
1394 | if (spf_reason_flags & SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL) | |
1395 | strncat(rbuf, "AS, ", sizeof(rbuf) - strlen(rbuf) - 1); | |
1396 | if (spf_reason_flags & SPF_FLAG_ABR_STATUS_CHANGE) | |
1397 | strncat(rbuf, "ABR, ", sizeof(rbuf) - strlen(rbuf) - 1); | |
1398 | if (spf_reason_flags & SPF_FLAG_ASBR_STATUS_CHANGE) | |
1399 | strncat(rbuf, "ASBR, ", | |
1400 | sizeof(rbuf) - strlen(rbuf) - 1); | |
1401 | if (spf_reason_flags & SPF_FLAG_MAXAGE) | |
1402 | strncat(rbuf, "M, ", sizeof(rbuf) - strlen(rbuf) - 1); | |
1403 | ||
1404 | size_t rbuflen = strlen(rbuf); | |
1405 | if (rbuflen >= 2) | |
1406 | rbuf[rbuflen - 2] = '\0'; /* skip the last ", " */ | |
1407 | else | |
1408 | rbuf[0] = '\0'; | |
1409 | } | |
1410 | ||
1411 | if (IS_DEBUG_OSPF_EVENT) { | |
1412 | zlog_info("SPF Processing Time(usecs): %ld", total_spf_time); | |
d6951e5e DL |
1413 | zlog_info(" SPF Time: %ld", spf_time); |
1414 | zlog_info(" InterArea: %ld", ia_time); | |
1415 | zlog_info(" Prune: %ld", prune_time); | |
1416 | zlog_info(" RouteInstall: %ld", rt_time); | |
d62a17ae | 1417 | if (IS_OSPF_ABR(ospf)) |
d6951e5e DL |
1418 | zlog_info(" ABR: %ld (%d areas)", |
1419 | abr_time, areas_processed); | |
d62a17ae | 1420 | zlog_info("Reason(s) for SPF: %s", rbuf); |
1421 | } | |
1422 | ||
1423 | ospf_clear_spf_reason_flags(); | |
1424 | ||
1425 | return 0; | |
718e3744 | 1426 | } |
1427 | ||
5ec5929c G |
1428 | /* |
1429 | * Add schedule for SPF calculation. To avoid frequenst SPF calc, we set timer | |
1430 | * for SPF calc. | |
1431 | */ | |
d62a17ae | 1432 | void ospf_spf_calculate_schedule(struct ospf *ospf, ospf_spf_reason_t reason) |
718e3744 | 1433 | { |
d62a17ae | 1434 | unsigned long delay, elapsed, ht; |
718e3744 | 1435 | |
d62a17ae | 1436 | if (IS_DEBUG_OSPF_EVENT) |
1437 | zlog_debug("SPF: calculation timer scheduled"); | |
1438 | ||
1439 | /* OSPF instance does not exist. */ | |
1440 | if (ospf == NULL) | |
1441 | return; | |
1442 | ||
1443 | ospf_spf_set_reason(reason); | |
1444 | ||
1445 | /* SPF calculation timer is already scheduled. */ | |
1446 | if (ospf->t_spf_calc) { | |
1447 | if (IS_DEBUG_OSPF_EVENT) | |
1448 | zlog_debug( | |
1449 | "SPF: calculation timer is already scheduled: %p", | |
1450 | (void *)ospf->t_spf_calc); | |
1451 | return; | |
1452 | } | |
1453 | ||
1454 | elapsed = monotime_since(&ospf->ts_spf, NULL) / 1000; | |
1455 | ||
1456 | ht = ospf->spf_holdtime * ospf->spf_hold_multiplier; | |
1457 | ||
1458 | if (ht > ospf->spf_max_holdtime) | |
1459 | ht = ospf->spf_max_holdtime; | |
1460 | ||
1461 | /* Get SPF calculation delay time. */ | |
1462 | if (elapsed < ht) { | |
5ec5929c G |
1463 | /* |
1464 | * Got an event within the hold time of last SPF. We need to | |
d62a17ae | 1465 | * increase the hold_multiplier, if it's not already at/past |
5ec5929c | 1466 | * maximum value, and wasn't already increased. |
d62a17ae | 1467 | */ |
1468 | if (ht < ospf->spf_max_holdtime) | |
1469 | ospf->spf_hold_multiplier++; | |
1470 | ||
1471 | /* always honour the SPF initial delay */ | |
1472 | if ((ht - elapsed) < ospf->spf_delay) | |
1473 | delay = ospf->spf_delay; | |
1474 | else | |
1475 | delay = ht - elapsed; | |
1476 | } else { | |
1477 | /* Event is past required hold-time of last SPF */ | |
1478 | delay = ospf->spf_delay; | |
1479 | ospf->spf_hold_multiplier = 1; | |
1480 | } | |
1481 | ||
1482 | if (IS_DEBUG_OSPF_EVENT) | |
05ba78e4 | 1483 | zlog_debug("SPF: calculation timer delay = %ld msec", delay); |
cf744958 | 1484 | |
d62a17ae | 1485 | ospf->t_spf_calc = NULL; |
5ec5929c G |
1486 | thread_add_timer_msec(master, ospf_spf_calculate_schedule_worker, ospf, |
1487 | delay, &ospf->t_spf_calc); | |
718e3744 | 1488 | } |