]> git.proxmox.com Git - mirror_frr.git/blame - ospf6d/ospf6_spf.c
projects / mirror_frr.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge branch 'stable/3.0' into tmp-3.0-master-merge
[mirror_frr.git] / ospf6d / ospf6_spf.c
CommitLineData
718e3744 1/*
508e53e2 2 * Copyright (C) 2003 Yasuhiro Ohara
718e3744 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 *
896014f4
DL		 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
718e3744 19 */
508e53e2 20
718e3744 21/* Shortest Path First calculation for OSPFv3 */
22
508e53e2 23#include <zebra.h>
718e3744 24
508e53e2 25#include "log.h"
26#include "memory.h"
27#include "command.h"
28#include "vty.h"
718e3744 29#include "prefix.h"
508e53e2 30#include "pqueue.h"
31#include "linklist.h"
32#include "thread.h"
718e3744 33
718e3744 34#include "ospf6_lsa.h"
35#include "ospf6_lsdb.h"
36#include "ospf6_route.h"
508e53e2 37#include "ospf6_area.h"
ca1f4309
DS		 38#include "ospf6_proto.h"
39#include "ospf6_abr.h"
718e3744 40#include "ospf6_spf.h"
508e53e2 41#include "ospf6_intra.h"
718e3744 42#include "ospf6_interface.h"
049207c3 43#include "ospf6d.h"
1f9a9fff 44#include "ospf6_abr.h"
718e3744 45
508e53e2 46unsigned char conf_debug_ospf6_spf = 0;
718e3744 47
d62a17ae 48static void ospf6_spf_copy_nexthops_to_route(struct ospf6_route *rt,
49 struct ospf6_vertex *v)
c3c0ac83 50{
d62a17ae 51 if (rt && v)
52 ospf6_copy_nexthops(rt->nh_list, v->nh_list);
c3c0ac83
DS		 53}
54
d62a17ae 55static void ospf6_spf_merge_nexthops_to_route(struct ospf6_route *rt,
56 struct ospf6_vertex *v)
c3c0ac83 57{
d62a17ae 58 if (rt && v)
59 ospf6_merge_nexthops(rt->nh_list, v->nh_list);
c3c0ac83
DS		 60}
61
d62a17ae 62static unsigned int ospf6_spf_get_ifindex_from_nh(struct ospf6_vertex *v)
c3c0ac83 63{
d62a17ae 64 struct ospf6_nexthop *nh;
65 struct listnode *node;
66
67 if (v) {
68 node = listhead(v->nh_list);
69 if (node) {
70 nh = listgetdata(node);
71 if (nh)
72 return (nh->ifindex);
73 }
c3c0ac83 74 }
d62a17ae 75 return 0;
c3c0ac83
DS		 76}
77
d62a17ae 78static int ospf6_vertex_cmp(void *a, void *b)
718e3744 79{
d62a17ae 80 struct ospf6_vertex *va = (struct ospf6_vertex *)a;
81 struct ospf6_vertex *vb = (struct ospf6_vertex *)b;
718e3744 82
d62a17ae 83 /* ascending order */
84 if (va->cost != vb->cost)
85 return (va->cost - vb->cost);
86 return (va->hops - vb->hops);
718e3744 87}
88
d62a17ae 89static int ospf6_vertex_id_cmp(void *a, void *b)
718e3744 90{
d62a17ae 91 struct ospf6_vertex *va = (struct ospf6_vertex *)a;
92 struct ospf6_vertex *vb = (struct ospf6_vertex *)b;
93 int ret = 0;
94
95 ret = ntohl(ospf6_linkstate_prefix_adv_router(&va->vertex_id))
96 - ntohl(ospf6_linkstate_prefix_adv_router(&vb->vertex_id));
97 if (ret)
98 return ret;
99
100 ret = ntohl(ospf6_linkstate_prefix_id(&va->vertex_id))
101 - ntohl(ospf6_linkstate_prefix_id(&vb->vertex_id));
102 return ret;
718e3744 103}
104
d62a17ae 105static struct ospf6_vertex *ospf6_vertex_create(struct ospf6_lsa *lsa)
718e3744 106{
d62a17ae 107 struct ospf6_vertex *v;
718e3744 108
d62a17ae 109 v = (struct ospf6_vertex *)XMALLOC(MTYPE_OSPF6_VERTEX,
110 sizeof(struct ospf6_vertex));
718e3744 111
d62a17ae 112 /* type */
113 if (ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER)
114 v->type = OSPF6_VERTEX_TYPE_ROUTER;
115 else if (ntohs(lsa->header->type) == OSPF6_LSTYPE_NETWORK)
116 v->type = OSPF6_VERTEX_TYPE_NETWORK;
117 else
118 assert(0);
718e3744 119
d62a17ae 120 /* vertex_id */
121 ospf6_linkstate_prefix(lsa->header->adv_router, lsa->header->id,
122 &v->vertex_id);
718e3744 123
d62a17ae 124 /* name */
125 ospf6_linkstate_prefix2str(&v->vertex_id, v->name, sizeof(v->name));
718e3744 126
d62a17ae 127 if (IS_OSPF6_DEBUG_SPF(PROCESS))
128 zlog_debug("%s: Creating vertex %s of type %s", __func__,
129 v->name,
130 ((ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER)
131 ? "Router"
132 : "N/W"));
c3c0ac83 133
d62a17ae 134 /* Associated LSA */
135 v->lsa = lsa;
718e3744 136
d62a17ae 137 /* capability bits + options */
138 v->capability = *(u_char *)(OSPF6_LSA_HEADER_END(lsa->header));
139 v->options[0] = *(u_char *)(OSPF6_LSA_HEADER_END(lsa->header) + 1);
140 v->options[1] = *(u_char *)(OSPF6_LSA_HEADER_END(lsa->header) + 2);
141 v->options[2] = *(u_char *)(OSPF6_LSA_HEADER_END(lsa->header) + 3);
718e3744 142
d62a17ae 143 v->nh_list = list_new();
d107621d 144 v->nh_list->del = (void (*) (void *))ospf6_nexthop_delete;
718e3744 145
d62a17ae 146 v->parent = NULL;
147 v->child_list = list_new();
148 v->child_list->cmp = ospf6_vertex_id_cmp;
718e3744 149
d62a17ae 150 return v;
718e3744 151}
152
d62a17ae 153static void ospf6_vertex_delete(struct ospf6_vertex *v)
718e3744 154{
d62a17ae 155 list_delete(v->nh_list);
156 list_delete(v->child_list);
157 XFREE(MTYPE_OSPF6_VERTEX, v);
718e3744 158}
159
d62a17ae 160static struct ospf6_lsa *ospf6_lsdesc_lsa(caddr_t lsdesc,
161 struct ospf6_vertex *v)
718e3744 162{
d62a17ae 163 struct ospf6_lsa *lsa;
164 u_int16_t type = 0;
165 u_int32_t id = 0, adv_router = 0;
166
167 if (VERTEX_IS_TYPE(NETWORK, v)) {
168 type = htons(OSPF6_LSTYPE_ROUTER);
169 id = htonl(0);
170 adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc);
171 } else {
172 if (ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, lsdesc)) {
173 type = htons(OSPF6_LSTYPE_ROUTER);
174 id = htonl(0);
175 adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc);
176 } else if (ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK, lsdesc)) {
177 type = htons(OSPF6_LSTYPE_NETWORK);
178 id = htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc));
179 adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc);
180 }
181 }
182
183 lsa = ospf6_lsdb_lookup(type, id, adv_router, v->area->lsdb);
184
185 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
186 char ibuf[16], abuf[16];
187 inet_ntop(AF_INET, &id, ibuf, sizeof(ibuf));
188 inet_ntop(AF_INET, &adv_router, abuf, sizeof(abuf));
189 if (lsa)
190 zlog_debug(" Link to: %s", lsa->name);
191 else
192 zlog_debug(" Link to: [%s Id:%s Adv:%s] No LSA",
193 ospf6_lstype_name(type), ibuf, abuf);
194 }
195
196 return lsa;
718e3744 197}
198
d62a17ae 199static char *ospf6_lsdesc_backlink(struct ospf6_lsa *lsa, caddr_t lsdesc,
200 struct ospf6_vertex *v)
718e3744 201{
d62a17ae 202 caddr_t backlink, found = NULL;
203 int size;
204
205 size = (OSPF6_LSA_IS_TYPE(ROUTER, lsa)
206 ? sizeof(struct ospf6_router_lsdesc)
207 : sizeof(struct ospf6_network_lsdesc));
208 for (backlink = OSPF6_LSA_HEADER_END(lsa->header) + 4;
209 backlink + size <= OSPF6_LSA_END(lsa->header); backlink += size) {
210 assert(!(OSPF6_LSA_IS_TYPE(NETWORK, lsa)
211 && VERTEX_IS_TYPE(NETWORK, v)));
212
213 if (OSPF6_LSA_IS_TYPE(NETWORK, lsa)
214 && NETWORK_LSDESC_GET_NBR_ROUTERID(backlink)
215 == v->lsa->header->adv_router)
216 found = backlink;
217 else if (VERTEX_IS_TYPE(NETWORK, v)
218 && ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK, backlink)
219 && ROUTER_LSDESC_GET_NBR_ROUTERID(backlink)
220 == v->lsa->header->adv_router
221 && ROUTER_LSDESC_GET_NBR_IFID(backlink)
222 == ntohl(v->lsa->header->id))
223 found = backlink;
224 else {
225 if (!ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, backlink)
226 || !ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, lsdesc))
227 continue;
228 if (ROUTER_LSDESC_GET_NBR_IFID(backlink)
229 != ROUTER_LSDESC_GET_IFID(lsdesc)
230 || ROUTER_LSDESC_GET_NBR_IFID(lsdesc)
231 != ROUTER_LSDESC_GET_IFID(backlink))
232 continue;
233 if (ROUTER_LSDESC_GET_NBR_ROUTERID(backlink)
234 != v->lsa->header->adv_router
235 || ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc)
236 != lsa->header->adv_router)
237 continue;
238 found = backlink;
239 }
240 }
241
242 if (IS_OSPF6_DEBUG_SPF(PROCESS))
243 zlog_debug(" Backlink %s", (found ? "OK" : "FAIL"));
244
245 return found;
718e3744 246}
247
d62a17ae 248static void ospf6_nexthop_calc(struct ospf6_vertex *w, struct ospf6_vertex *v,
249 caddr_t lsdesc)
718e3744 250{
d62a17ae 251 int i;
252 ifindex_t ifindex;
253 struct ospf6_interface *oi;
254 u_int16_t type;
255 u_int32_t adv_router;
256 struct ospf6_lsa *lsa;
257 struct ospf6_link_lsa *link_lsa;
258 char buf[64];
259
260 assert(VERTEX_IS_TYPE(ROUTER, w));
261 ifindex = (VERTEX_IS_TYPE(NETWORK, v) ? ospf6_spf_get_ifindex_from_nh(v)
262 : ROUTER_LSDESC_GET_IFID(lsdesc));
263 if (ifindex == 0) {
264 zlog_err("No nexthop ifindex at vertex %s", v->name);
265 return;
266 }
267
268 oi = ospf6_interface_lookup_by_ifindex(ifindex);
269 if (oi == NULL) {
270 if (IS_OSPF6_DEBUG_SPF(PROCESS))
271 zlog_debug("Can't find interface in SPF: ifindex %d",
272 ifindex);
273 return;
274 }
275
276 type = htons(OSPF6_LSTYPE_LINK);
277 adv_router = (VERTEX_IS_TYPE(NETWORK, v)
278 ? NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc)
279 : ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc));
280
281 i = 0;
282 for (ALL_LSDB_TYPED_ADVRTR(oi->lsdb, type, adv_router, lsa)) {
283 if (VERTEX_IS_TYPE(ROUTER, v)
284 && htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc))
285 != lsa->header->id)
286 continue;
287
288 link_lsa = (struct ospf6_link_lsa *)OSPF6_LSA_HEADER_END(
289 lsa->header);
290 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
291 inet_ntop(AF_INET6, &link_lsa->linklocal_addr, buf,
292 sizeof(buf));
293 zlog_debug(" nexthop %s from %s", buf, lsa->name);
294 }
295
296 ospf6_add_nexthop(w->nh_list, ifindex,
297 &link_lsa->linklocal_addr);
298 i++;
299 }
300
301 if (i == 0 && IS_OSPF6_DEBUG_SPF(PROCESS))
302 zlog_debug("No nexthop for %s found", w->name);
718e3744 303}
304
d62a17ae 305static int ospf6_spf_install(struct ospf6_vertex *v,
306 struct ospf6_route_table *result_table)
718e3744 307{
d62a17ae 308 struct ospf6_route *route, *parent_route;
309 struct ospf6_vertex *prev;
310
311 if (IS_OSPF6_DEBUG_SPF(PROCESS))
312 zlog_debug("SPF install %s hops %d cost %d", v->name, v->hops,
313 v->cost);
314
315 route = ospf6_route_lookup(&v->vertex_id, result_table);
316 if (route && route->path.cost < v->cost) {
317 if (IS_OSPF6_DEBUG_SPF(PROCESS))
318 zlog_debug(
319 " already installed with lower cost (%d), ignore",
320 route->path.cost);
321 ospf6_vertex_delete(v);
322 return -1;
323 } else if (route && route->path.cost == v->cost) {
324 if (IS_OSPF6_DEBUG_SPF(PROCESS))
325 zlog_debug(" another path found, merge");
326
327 ospf6_spf_merge_nexthops_to_route(route, v);
328
329 prev = (struct ospf6_vertex *)route->route_option;
330 assert(prev->hops <= v->hops);
331 ospf6_vertex_delete(v);
332
333 return -1;
c3c0ac83 334 }
508e53e2 335
d62a17ae 336 /* There should be no case where candidate being installed (variable
337 "v") is closer than the one in the SPF tree (variable "route").
338 In the case something has gone wrong with the behavior of
339 Priority-Queue. */
340
341 /* the case where the route exists already is handled and returned
342 up to here. */
343 assert(route == NULL);
344
345 route = ospf6_route_create();
346 memcpy(&route->prefix, &v->vertex_id, sizeof(struct prefix));
347 route->type = OSPF6_DEST_TYPE_LINKSTATE;
348 route->path.type = OSPF6_PATH_TYPE_INTRA;
349 route->path.origin.type = v->lsa->header->type;
350 route->path.origin.id = v->lsa->header->id;
351 route->path.origin.adv_router = v->lsa->header->adv_router;
352 route->path.metric_type = 1;
353 route->path.cost = v->cost;
354 route->path.u.cost_e2 = v->hops;
355 route->path.router_bits = v->capability;
356 route->path.options[0] = v->options[0];
357 route->path.options[1] = v->options[1];
358 route->path.options[2] = v->options[2];
359
360 ospf6_spf_copy_nexthops_to_route(route, v);
361
362 /*
363 * The SPF logic implementation does not transfer the multipathing
364 * properties
365 * of a parent to a child node. Thus if there was a 3-way multipath to a
366 * node's parent and a single hop from the parent to the child, the
367 * logic of
368 * creating new vertices and computing next hops prevents there from
369 * being 3
370 * paths to the child node. This is primarily because the resolution of
371 * multipath is done in this routine, not in the main spf loop.
372 *
373 * The following logic addresses that problem by merging the parent's
374 * nexthop
375 * information with the child's, if the parent is not the root of the
376 * tree.
377 * This is based on the assumption that before a node's route is
378 * installed,
379 * its parent's route's nexthops have already been installed.
380 */
381 if (v->parent && v->parent->hops) {
382 parent_route =
383 ospf6_route_lookup(&v->parent->vertex_id, result_table);
384 if (parent_route) {
385 ospf6_route_merge_nexthops(route, parent_route);
386 }
387 }
388
389 if (v->parent)
390 listnode_add_sort(v->parent->child_list, v);
391 route->route_option = v;
508e53e2 392
d62a17ae 393 ospf6_route_add(route, result_table);
394 return 0;
718e3744 395}
396
d62a17ae 397void ospf6_spf_table_finish(struct ospf6_route_table *result_table)
718e3744 398{
d62a17ae 399 struct ospf6_route *route, *nroute;
400 struct ospf6_vertex *v;
401 for (route = ospf6_route_head(result_table); route; route = nroute) {
402 nroute = ospf6_route_next(route);
403 v = (struct ospf6_vertex *)route->route_option;
404 ospf6_vertex_delete(v);
405 ospf6_route_remove(route, result_table);
406 }
718e3744 407}
408
d62a17ae 409static const char *ospf6_spf_reason_str[] = {
410 "R+", "R-", "N+", "N-", "L+", "L-", "R*", "N*",
411};
412
413void ospf6_spf_reason_string(unsigned int reason, char *buf, int size)
a0edf674 414{
d62a17ae 415 unsigned int bit;
416 int len = 0;
417
418 if (!buf)
419 return;
420
421 for (bit = 0; bit < array_size(ospf6_spf_reason_str); bit++) {
422 if ((reason & (1 << bit)) && (len < size)) {
423 len += snprintf((buf + len), (size - len), "%s%s",
424 (len > 0) ? ", " : "",
425 ospf6_spf_reason_str[bit]);
426 }
a0edf674 427 }
a0edf674
DD		 428}
429
6452df09 430/* RFC2328 16.1. Calculating the shortest-path tree for an area */
431/* RFC2740 3.8.1. Calculating the shortest path tree for an area */
d62a17ae 432void ospf6_spf_calculation(u_int32_t router_id,
433 struct ospf6_route_table *result_table,
434 struct ospf6_area *oa)
508e53e2 435{
d62a17ae 436 struct pqueue *candidate_list;
437 struct ospf6_vertex *root, *v, *w;
438 int size;
439 caddr_t lsdesc;
440 struct ospf6_lsa *lsa;
441 struct in6_addr address;
442
443 ospf6_spf_table_finish(result_table);
444
445 /* Install the calculating router itself as the root of the SPF tree */
446 /* construct root vertex */
447 lsa = ospf6_lsdb_lookup(htons(OSPF6_LSTYPE_ROUTER), htonl(0), router_id,
448 oa->lsdb_self);
449 if (lsa == NULL) {
450 if (IS_OSPF6_DEBUG_SPF(PROCESS))
451 zlog_debug("%s: No router LSA for area %s\n", __func__,
452 oa->name);
453 return;
454 }
455
456 /* initialize */
457 candidate_list = pqueue_create();
458 candidate_list->cmp = ospf6_vertex_cmp;
459
460 root = ospf6_vertex_create(lsa);
461 root->area = oa;
462 root->cost = 0;
463 root->hops = 0;
464 inet_pton(AF_INET6, "::1", &address);
465
466 /* Actually insert root to the candidate-list as the only candidate */
467 pqueue_enqueue(root, candidate_list);
468
469 /* Iterate until candidate-list becomes empty */
470 while (candidate_list->size) {
471 /* get closest candidate from priority queue */
472 v = pqueue_dequeue(candidate_list);
473
474 /* installing may result in merging or rejecting of the vertex
475 */
476 if (ospf6_spf_install(v, result_table) < 0)
477 continue;
478
479 /* Skip overloaded routers */
480 if ((OSPF6_LSA_IS_TYPE(ROUTER, v->lsa)
481 && ospf6_router_is_stub_router(v->lsa)))
482 continue;
483
484 /* For each LS description in the just-added vertex V's LSA */
485 size = (VERTEX_IS_TYPE(ROUTER, v)
486 ? sizeof(struct ospf6_router_lsdesc)
487 : sizeof(struct ospf6_network_lsdesc));
488 for (lsdesc = OSPF6_LSA_HEADER_END(v->lsa->header) + 4;
489 lsdesc + size <= OSPF6_LSA_END(v->lsa->header);
490 lsdesc += size) {
491 lsa = ospf6_lsdesc_lsa(lsdesc, v);
492 if (lsa == NULL)
493 continue;
494
495 if (OSPF6_LSA_IS_MAXAGE(lsa))
496 continue;
497
498 if (!ospf6_lsdesc_backlink(lsa, lsdesc, v))
499 continue;
500
501 w = ospf6_vertex_create(lsa);
502 w->area = oa;
503 w->parent = v;
504 if (VERTEX_IS_TYPE(ROUTER, v)) {
505 w->cost = v->cost
506 + ROUTER_LSDESC_GET_METRIC(lsdesc);
507 w->hops =
508 v->hops
509 + (VERTEX_IS_TYPE(NETWORK, w) ? 0 : 1);
510 } else /* NETWORK */
511 {
512 w->cost = v->cost;
513 w->hops = v->hops + 1;
514 }
515
516 /* nexthop calculation */
517 if (w->hops == 0)
518 ospf6_add_nexthop(
519 w->nh_list,
520 ROUTER_LSDESC_GET_IFID(lsdesc), NULL);
521 else if (w->hops == 1 && v->hops == 0)
522 ospf6_nexthop_calc(w, v, lsdesc);
523 else {
524 ospf6_copy_nexthops(w->nh_list, v->nh_list);
525 }
526
527 /* add new candidate to the candidate_list */
528 if (IS_OSPF6_DEBUG_SPF(PROCESS))
529 zlog_debug(
530 " New candidate: %s hops %d cost %d",
531 w->name, w->hops, w->cost);
532 pqueue_enqueue(w, candidate_list);
533 }
534 }
535
536 pqueue_delete(candidate_list);
537
538 oa->spf_calculation++;
718e3744 539}
540
d62a17ae 541static void ospf6_spf_log_database(struct ospf6_area *oa)
2680aa2b 542{
d62a17ae 543 char *p, *end, buffer[256];
544 struct listnode *node;
545 struct ospf6_interface *oi;
546
547 p = buffer;
548 end = buffer + sizeof(buffer);
549
550 snprintf(p, end - p, "SPF on DB (#LSAs):");
551 p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) : end);
552 snprintf(p, end - p, " Area %s: %d", oa->name, oa->lsdb->count);
553 p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) : end);
554
555 for (ALL_LIST_ELEMENTS_RO(oa->if_list, node, oi)) {
556 snprintf(p, end - p, " I/F %s: %d", oi->interface->name,
557 oi->lsdb->count);
558 p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer)
559 : end);
560 }
561
562 zlog_debug("%s", buffer);
2680aa2b 563}
564
d62a17ae 565static int ospf6_spf_calculation_thread(struct thread *t)
718e3744 566{
d62a17ae 567 struct ospf6_area *oa;
568 struct ospf6 *ospf6;
569 struct timeval start, end, runtime;
570 struct listnode *node;
571 int areas_processed = 0;
572 char rbuf[32];
573
574 ospf6 = (struct ospf6 *)THREAD_ARG(t);
575 ospf6->t_spf_calc = NULL;
576
577 /* execute SPF calculation */
578 monotime(&start);
579
580 if (ospf6_is_router_abr(ospf6))
581 ospf6_abr_range_reset_cost(ospf6);
582
583 for (ALL_LIST_ELEMENTS_RO(ospf6->area_list, node, oa)) {
584
585 if (oa == ospf6->backbone)
586 continue;
587
588 if (IS_OSPF6_DEBUG_SPF(PROCESS))
589 zlog_debug("SPF calculation for Area %s", oa->name);
590 if (IS_OSPF6_DEBUG_SPF(DATABASE))
591 ospf6_spf_log_database(oa);
592
593 ospf6_spf_calculation(ospf6->router_id, oa->spf_table, oa);
594 ospf6_intra_route_calculation(oa);
595 ospf6_intra_brouter_calculation(oa);
596
597 areas_processed++;
598 }
599
600 if (ospf6->backbone) {
601 if (IS_OSPF6_DEBUG_SPF(PROCESS))
602 zlog_debug("SPF calculation for Backbone area %s",
603 ospf6->backbone->name);
604 if (IS_OSPF6_DEBUG_SPF(DATABASE))
605 ospf6_spf_log_database(ospf6->backbone);
606
607 ospf6_spf_calculation(ospf6->router_id,
608 ospf6->backbone->spf_table,
609 ospf6->backbone);
610 ospf6_intra_route_calculation(ospf6->backbone);
611 ospf6_intra_brouter_calculation(ospf6->backbone);
612 areas_processed++;
613 }
614
615 if (ospf6_is_router_abr(ospf6))
616 ospf6_abr_defaults_to_stub(ospf6);
617
618 monotime(&end);
619 timersub(&end, &start, &runtime);
620
621 ospf6->ts_spf_duration = runtime;
622
623 ospf6_spf_reason_string(ospf6->spf_reason, rbuf, sizeof(rbuf));
624
625 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
626 zlog_debug("SPF runtime: %lld sec %lld usec",
627 (long long)runtime.tv_sec,
628 (long long)runtime.tv_usec);
629
630 zlog_info(
631 "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
632 "Reason: %s\n",
633 areas_processed, (long long)runtime.tv_sec,
634 (long long)runtime.tv_usec, rbuf);
635 ospf6->last_spf_reason = ospf6->spf_reason;
636 ospf6_reset_spf_reason(ospf6);
637 return 0;
718e3744 638}
639
3810e06e
DD		 640/* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
641 set timer for SPF calc. */
d62a17ae 642void ospf6_spf_schedule(struct ospf6 *ospf6, unsigned int reason)
718e3744 643{
d62a17ae 644 unsigned long delay, elapsed, ht;
645
646 ospf6_set_spf_reason(ospf6, reason);
647
648 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) {
649 char rbuf[32];
650 ospf6_spf_reason_string(reason, rbuf, sizeof(rbuf));
651 zlog_debug("SPF: calculation timer scheduled (reason %s)",
652 rbuf);
653 }
654
655 /* OSPF instance does not exist. */
656 if (ospf6 == NULL)
657 return;
658
659 /* SPF calculation timer is already scheduled. */
660 if (ospf6->t_spf_calc) {
661 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
662 zlog_debug(
663 "SPF: calculation timer is already scheduled: %p",
664 (void *)ospf6->t_spf_calc);
665 return;
666 }
667
668 elapsed = monotime_since(&ospf6->ts_spf, NULL) / 1000LL;
669 ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier;
670
671 if (ht > ospf6->spf_max_holdtime)
672 ht = ospf6->spf_max_holdtime;
673
674 /* Get SPF calculation delay time. */
675 if (elapsed < ht) {
676 /* Got an event within the hold time of last SPF. We need to
677 * increase the hold_multiplier, if it's not already at/past
678 * maximum value, and wasn't already increased..
679 */
680 if (ht < ospf6->spf_max_holdtime)
681 ospf6->spf_hold_multiplier++;
682
683 /* always honour the SPF initial delay */
684 if ((ht - elapsed) < ospf6->spf_delay)
685 delay = ospf6->spf_delay;
686 else
687 delay = ht - elapsed;
688 } else {
689 /* Event is past required hold-time of last SPF */
690 delay = ospf6->spf_delay;
691 ospf6->spf_hold_multiplier = 1;
692 }
693
694 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
695 zlog_debug("SPF: calculation timer delay = %ld", delay);
696
697 zlog_info("SPF: Scheduled in %ld msec", delay);
698
699 ospf6->t_spf_calc = NULL;
700 thread_add_timer_msec(master, ospf6_spf_calculation_thread, ospf6,
701 delay, &ospf6->t_spf_calc);
718e3744 702}
703
d62a17ae 704void ospf6_spf_display_subtree(struct vty *vty, const char *prefix, int rest,
705 struct ospf6_vertex *v)
718e3744 706{
d62a17ae 707 struct listnode *node, *nnode;
708 struct ospf6_vertex *c;
709 char *next_prefix;
710 int len;
711 int restnum;
712
713 /* "prefix" is the space prefix of the display line */
714 vty_out(vty, "%s+-%s [%d]\n", prefix, v->name, v->cost);
715
716 len = strlen(prefix) + 4;
717 next_prefix = (char *)malloc(len);
718 if (next_prefix == NULL) {
719 vty_out(vty, "malloc failed\n");
720 return;
721 }
722 snprintf(next_prefix, len, "%s%s", prefix, (rest ? "| " : " "));
723
724 restnum = listcount(v->child_list);
725 for (ALL_LIST_ELEMENTS(v->child_list, node, nnode, c)) {
726 restnum--;
727 ospf6_spf_display_subtree(vty, next_prefix, restnum, c);
728 }
729
730 free(next_prefix);
718e3744 731}
732
3b68735f 733DEFUN (debug_ospf6_spf_process,
734 debug_ospf6_spf_process_cmd,
735 "debug ospf6 spf process",
508e53e2 736 DEBUG_STR
737 OSPF6_STR
738 "Debug SPF Calculation\n"
3b68735f 739 "Debug Detailed SPF Process\n"
508e53e2 740 )
718e3744 741{
d62a17ae 742 unsigned char level = 0;
743 level = OSPF6_DEBUG_SPF_PROCESS;
744 OSPF6_DEBUG_SPF_ON(level);
745 return CMD_SUCCESS;
718e3744 746}
747
3b68735f 748DEFUN (debug_ospf6_spf_time,
749 debug_ospf6_spf_time_cmd,
750 "debug ospf6 spf time",
508e53e2 751 DEBUG_STR
718e3744 752 OSPF6_STR
508e53e2 753 "Debug SPF Calculation\n"
3b68735f 754 "Measure time taken by SPF Calculation\n"
508e53e2 755 )
718e3744 756{
d62a17ae 757 unsigned char level = 0;
758 level = OSPF6_DEBUG_SPF_TIME;
759 OSPF6_DEBUG_SPF_ON(level);
760 return CMD_SUCCESS;
718e3744 761}
762
2680aa2b 763DEFUN (debug_ospf6_spf_database,
764 debug_ospf6_spf_database_cmd,
765 "debug ospf6 spf database",
766 DEBUG_STR
767 OSPF6_STR
768 "Debug SPF Calculation\n"
769 "Log number of LSAs at SPF Calculation time\n"
770 )
771{
d62a17ae 772 unsigned char level = 0;
773 level = OSPF6_DEBUG_SPF_DATABASE;
774 OSPF6_DEBUG_SPF_ON(level);
775 return CMD_SUCCESS;
2680aa2b 776}
777
3b68735f 778DEFUN (no_debug_ospf6_spf_process,
779 no_debug_ospf6_spf_process_cmd,
780 "no debug ospf6 spf process",
508e53e2 781 NO_STR
782 DEBUG_STR
783 OSPF6_STR
784 "Quit Debugging SPF Calculation\n"
3b68735f 785 "Quit Debugging Detailed SPF Process\n"
508e53e2 786 )
718e3744 787{
d62a17ae 788 unsigned char level = 0;
789 level = OSPF6_DEBUG_SPF_PROCESS;
790 OSPF6_DEBUG_SPF_OFF(level);
791 return CMD_SUCCESS;
718e3744 792}
793
3b68735f 794DEFUN (no_debug_ospf6_spf_time,
795 no_debug_ospf6_spf_time_cmd,
796 "no debug ospf6 spf time",
508e53e2 797 NO_STR
798 DEBUG_STR
718e3744 799 OSPF6_STR
508e53e2 800 "Quit Debugging SPF Calculation\n"
3b68735f 801 "Quit Measuring time taken by SPF Calculation\n"
508e53e2 802 )
718e3744 803{
d62a17ae 804 unsigned char level = 0;
805 level = OSPF6_DEBUG_SPF_TIME;
806 OSPF6_DEBUG_SPF_OFF(level);
807 return CMD_SUCCESS;
718e3744 808}
809
2680aa2b 810DEFUN (no_debug_ospf6_spf_database,
811 no_debug_ospf6_spf_database_cmd,
812 "no debug ospf6 spf database",
813 NO_STR
814 DEBUG_STR
815 OSPF6_STR
816 "Debug SPF Calculation\n"
817 "Quit Logging number of LSAs at SPF Calculation time\n"
818 )
819{
d62a17ae 820 unsigned char level = 0;
821 level = OSPF6_DEBUG_SPF_DATABASE;
822 OSPF6_DEBUG_SPF_OFF(level);
823 return CMD_SUCCESS;
2680aa2b 824}
825
d62a17ae 826static int ospf6_timers_spf_set(struct vty *vty, unsigned int delay,
827 unsigned int hold, unsigned int max)
3810e06e 828{
d62a17ae 829 VTY_DECLVAR_CONTEXT(ospf6, ospf);
3810e06e 830
d62a17ae 831 ospf->spf_delay = delay;
832 ospf->spf_holdtime = hold;
833 ospf->spf_max_holdtime = max;
3810e06e 834
d62a17ae 835 return CMD_SUCCESS;
3810e06e
DD		 836}
837
838DEFUN (ospf6_timers_throttle_spf,
839 ospf6_timers_throttle_spf_cmd,
6147e2c6 840 "timers throttle spf (0-600000) (0-600000) (0-600000)",
3810e06e
DD		 841 "Adjust routing timers\n"
842 "Throttling adaptive timer\n"
843 "OSPF6 SPF timers\n"
844 "Delay (msec) from first change received till SPF calculation\n"
845 "Initial hold time (msec) between consecutive SPF calculations\n"
846 "Maximum hold time (msec)\n")
847{
d62a17ae 848 int idx_number = 3;
849 int idx_number_2 = 4;
850 int idx_number_3 = 5;
851 unsigned int delay, hold, max;
3810e06e 852
d62a17ae 853 delay = strtoul(argv[idx_number]->arg, NULL, 10);
854 hold = strtoul(argv[idx_number_2]->arg, NULL, 10);
855 max = strtoul(argv[idx_number_3]->arg, NULL, 10);
3810e06e 856
d62a17ae 857 return ospf6_timers_spf_set(vty, delay, hold, max);
3810e06e
DD		 858}
859
860DEFUN (no_ospf6_timers_throttle_spf,
861 no_ospf6_timers_throttle_spf_cmd,
1d68dbfe 862 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
3810e06e
DD		 863 NO_STR
864 "Adjust routing timers\n"
865 "Throttling adaptive timer\n"
1d68dbfe
DW		 866 "OSPF6 SPF timers\n"
867 "Delay (msec) from first change received till SPF calculation\n"
868 "Initial hold time (msec) between consecutive SPF calculations\n"
869 "Maximum hold time (msec)\n")
3810e06e 870{
d62a17ae 871 return ospf6_timers_spf_set(vty, OSPF_SPF_DELAY_DEFAULT,
872 OSPF_SPF_HOLDTIME_DEFAULT,
873 OSPF_SPF_MAX_HOLDTIME_DEFAULT);
3810e06e
DD		 874}
875
813d4307 876
d62a17ae 877int config_write_ospf6_debug_spf(struct vty *vty)
718e3744 878{
d62a17ae 879 if (IS_OSPF6_DEBUG_SPF(PROCESS))
880 vty_out(vty, "debug ospf6 spf process\n");
881 if (IS_OSPF6_DEBUG_SPF(TIME))
882 vty_out(vty, "debug ospf6 spf time\n");
883 if (IS_OSPF6_DEBUG_SPF(DATABASE))
884 vty_out(vty, "debug ospf6 spf database\n");
885 return 0;
718e3744 886}
887
d62a17ae 888void ospf6_spf_config_write(struct vty *vty)
3810e06e
DD		 889{
890
d62a17ae 891 if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT
892 || ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT
893 || ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT)
894 vty_out(vty, " timers throttle spf %d %d %d\n",
895 ospf6->spf_delay, ospf6->spf_holdtime,
896 ospf6->spf_max_holdtime);
3810e06e
DD		 897}
898
d62a17ae 899void install_element_ospf6_debug_spf(void)
508e53e2 900{
d62a17ae 901 install_element(ENABLE_NODE, &debug_ospf6_spf_process_cmd);
902 install_element(ENABLE_NODE, &debug_ospf6_spf_time_cmd);
903 install_element(ENABLE_NODE, &debug_ospf6_spf_database_cmd);
904 install_element(ENABLE_NODE, &no_debug_ospf6_spf_process_cmd);
905 install_element(ENABLE_NODE, &no_debug_ospf6_spf_time_cmd);
906 install_element(ENABLE_NODE, &no_debug_ospf6_spf_database_cmd);
907 install_element(CONFIG_NODE, &debug_ospf6_spf_process_cmd);
908 install_element(CONFIG_NODE, &debug_ospf6_spf_time_cmd);
909 install_element(CONFIG_NODE, &debug_ospf6_spf_database_cmd);
910 install_element(CONFIG_NODE, &no_debug_ospf6_spf_process_cmd);
911 install_element(CONFIG_NODE, &no_debug_ospf6_spf_time_cmd);
912 install_element(CONFIG_NODE, &no_debug_ospf6_spf_database_cmd);
508e53e2 913}
718e3744 914
d62a17ae 915void ospf6_spf_init(void)
718e3744 916{
d62a17ae 917 install_element(OSPF6_NODE, &ospf6_timers_throttle_spf_cmd);
918 install_element(OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd);
718e3744 919}
FRRouting mirror