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