]> git.proxmox.com Git - mirror_frr.git/blob - ospf6d/ospf6_spf.c
projects / mirror_frr.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
*: Convert list_delete(struct list *) to ** to allow nulling
[mirror_frr.git] / ospf6d / ospf6_spf.c
1 /*
2 * Copyright (C) 2003 Yasuhiro Ohara
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 */
20
21 /* Shortest Path First calculation for OSPFv3 */
22
23 #include <zebra.h>
24
25 #include "log.h"
26 #include "memory.h"
27 #include "command.h"
28 #include "vty.h"
29 #include "prefix.h"
30 #include "pqueue.h"
31 #include "linklist.h"
32 #include "thread.h"
33
34 #include "ospf6_lsa.h"
35 #include "ospf6_lsdb.h"
36 #include "ospf6_route.h"
37 #include "ospf6_area.h"
38 #include "ospf6_proto.h"
39 #include "ospf6_abr.h"
40 #include "ospf6_spf.h"
41 #include "ospf6_intra.h"
42 #include "ospf6_interface.h"
43 #include "ospf6d.h"
44 #include "ospf6_abr.h"
45
46 unsigned char conf_debug_ospf6_spf = 0;
47
48 static void ospf6_spf_copy_nexthops_to_route(struct ospf6_route *rt,
49 struct ospf6_vertex *v)
50 {
51 if (rt && v)
52 ospf6_copy_nexthops(rt->nh_list, v->nh_list);
53 }
54
55 static void ospf6_spf_merge_nexthops_to_route(struct ospf6_route *rt,
56 struct ospf6_vertex *v)
57 {
58 if (rt && v)
59 ospf6_merge_nexthops(rt->nh_list, v->nh_list);
60 }
61
62 static unsigned int ospf6_spf_get_ifindex_from_nh(struct ospf6_vertex *v)
63 {
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 }
74 }
75 return 0;
76 }
77
78 static int ospf6_vertex_cmp(void *a, void *b)
79 {
80 struct ospf6_vertex *va = (struct ospf6_vertex *)a;
81 struct ospf6_vertex *vb = (struct ospf6_vertex *)b;
82
83 /* ascending order */
84 if (va->cost != vb->cost)
85 return (va->cost - vb->cost);
86 return (va->hops - vb->hops);
87 }
88
89 static int ospf6_vertex_id_cmp(void *a, void *b)
90 {
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;
103 }
104
105 static struct ospf6_vertex *ospf6_vertex_create(struct ospf6_lsa *lsa)
106 {
107 struct ospf6_vertex *v;
108
109 v = (struct ospf6_vertex *)XMALLOC(MTYPE_OSPF6_VERTEX,
110 sizeof(struct ospf6_vertex));
111
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);
119
120 /* vertex_id */
121 ospf6_linkstate_prefix(lsa->header->adv_router, lsa->header->id,
122 &v->vertex_id);
123
124 /* name */
125 ospf6_linkstate_prefix2str(&v->vertex_id, v->name, sizeof(v->name));
126
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"));
133
134 /* Associated LSA */
135 v->lsa = lsa;
136
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);
142
143 v->nh_list = list_new();
144 v->nh_list->del = (void (*) (void *))ospf6_nexthop_delete;
145
146 v->parent = NULL;
147 v->child_list = list_new();
148 v->child_list->cmp = ospf6_vertex_id_cmp;
149
150 return v;
151 }
152
153 static void ospf6_vertex_delete(struct ospf6_vertex *v)
154 {
155 list_delete_and_null(&v->nh_list);
156 list_delete_and_null(&v->child_list);
157 XFREE(MTYPE_OSPF6_VERTEX, v);
158 }
159
160 static struct ospf6_lsa *ospf6_lsdesc_lsa(caddr_t lsdesc,
161 struct ospf6_vertex *v)
162 {
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;
197 }
198
199 static char *ospf6_lsdesc_backlink(struct ospf6_lsa *lsa, caddr_t lsdesc,
200 struct ospf6_vertex *v)
201 {
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;
246 }
247
248 static void ospf6_nexthop_calc(struct ospf6_vertex *w, struct ospf6_vertex *v,
249 caddr_t lsdesc)
250 {
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);
303 }
304
305 static int ospf6_spf_install(struct ospf6_vertex *v,
306 struct ospf6_route_table *result_table)
307 {
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;
334 }
335
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;
392
393 ospf6_route_add(route, result_table);
394 return 0;
395 }
396
397 void ospf6_spf_table_finish(struct ospf6_route_table *result_table)
398 {
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 }
407 }
408
409 static const char *ospf6_spf_reason_str[] = {
410 "R+", "R-", "N+", "N-", "L+", "L-", "R*", "N*",
411 };
412
413 void ospf6_spf_reason_string(unsigned int reason, char *buf, int size)
414 {
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 }
427 }
428 }
429
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 */
432 void ospf6_spf_calculation(u_int32_t router_id,
433 struct ospf6_route_table *result_table,
434 struct ospf6_area *oa)
435 {
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++;
539 }
540
541 static void ospf6_spf_log_database(struct ospf6_area *oa)
542 {
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);
563 }
564
565 static int ospf6_spf_calculation_thread(struct thread *t)
566 {
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 ospf6->ts_spf = start;
580
581 if (ospf6_is_router_abr(ospf6))
582 ospf6_abr_range_reset_cost(ospf6);
583
584 for (ALL_LIST_ELEMENTS_RO(ospf6->area_list, node, oa)) {
585
586 if (oa == ospf6->backbone)
587 continue;
588
589 monotime(&oa->ts_spf);
590 if (IS_OSPF6_DEBUG_SPF(PROCESS))
591 zlog_debug("SPF calculation for Area %s", oa->name);
592 if (IS_OSPF6_DEBUG_SPF(DATABASE))
593 ospf6_spf_log_database(oa);
594
595 ospf6_spf_calculation(ospf6->router_id, oa->spf_table, oa);
596 ospf6_intra_route_calculation(oa);
597 ospf6_intra_brouter_calculation(oa);
598
599 areas_processed++;
600 }
601
602 if (ospf6->backbone) {
603 monotime(&ospf6->backbone->ts_spf);
604 if (IS_OSPF6_DEBUG_SPF(PROCESS))
605 zlog_debug("SPF calculation for Backbone area %s",
606 ospf6->backbone->name);
607 if (IS_OSPF6_DEBUG_SPF(DATABASE))
608 ospf6_spf_log_database(ospf6->backbone);
609
610 ospf6_spf_calculation(ospf6->router_id,
611 ospf6->backbone->spf_table,
612 ospf6->backbone);
613 ospf6_intra_route_calculation(ospf6->backbone);
614 ospf6_intra_brouter_calculation(ospf6->backbone);
615 areas_processed++;
616 }
617
618 if (ospf6_is_router_abr(ospf6))
619 ospf6_abr_defaults_to_stub(ospf6);
620
621 monotime(&end);
622 timersub(&end, &start, &runtime);
623
624 ospf6->ts_spf_duration = runtime;
625
626 ospf6_spf_reason_string(ospf6->spf_reason, rbuf, sizeof(rbuf));
627
628 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
629 zlog_debug("SPF runtime: %lld sec %lld usec",
630 (long long)runtime.tv_sec,
631 (long long)runtime.tv_usec);
632
633 zlog_info(
634 "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
635 "Reason: %s\n",
636 areas_processed, (long long)runtime.tv_sec,
637 (long long)runtime.tv_usec, rbuf);
638
639 ospf6->last_spf_reason = ospf6->spf_reason;
640 ospf6_reset_spf_reason(ospf6);
641 return 0;
642 }
643
644 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
645 set timer for SPF calc. */
646 void ospf6_spf_schedule(struct ospf6 *ospf6, unsigned int reason)
647 {
648 unsigned long delay, elapsed, ht;
649
650 ospf6_set_spf_reason(ospf6, reason);
651
652 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) {
653 char rbuf[32];
654 ospf6_spf_reason_string(reason, rbuf, sizeof(rbuf));
655 zlog_debug("SPF: calculation timer scheduled (reason %s)",
656 rbuf);
657 }
658
659 /* OSPF instance does not exist. */
660 if (ospf6 == NULL)
661 return;
662
663 /* SPF calculation timer is already scheduled. */
664 if (ospf6->t_spf_calc) {
665 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
666 zlog_debug(
667 "SPF: calculation timer is already scheduled: %p",
668 (void *)ospf6->t_spf_calc);
669 return;
670 }
671
672 elapsed = monotime_since(&ospf6->ts_spf, NULL) / 1000LL;
673 ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier;
674
675 if (ht > ospf6->spf_max_holdtime)
676 ht = ospf6->spf_max_holdtime;
677
678 /* Get SPF calculation delay time. */
679 if (elapsed < ht) {
680 /* Got an event within the hold time of last SPF. We need to
681 * increase the hold_multiplier, if it's not already at/past
682 * maximum value, and wasn't already increased..
683 */
684 if (ht < ospf6->spf_max_holdtime)
685 ospf6->spf_hold_multiplier++;
686
687 /* always honour the SPF initial delay */
688 if ((ht - elapsed) < ospf6->spf_delay)
689 delay = ospf6->spf_delay;
690 else
691 delay = ht - elapsed;
692 } else {
693 /* Event is past required hold-time of last SPF */
694 delay = ospf6->spf_delay;
695 ospf6->spf_hold_multiplier = 1;
696 }
697
698 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
699 zlog_debug("SPF: calculation timer delay = %ld", delay);
700
701 zlog_info("SPF: Scheduled in %ld msec", delay);
702
703 ospf6->t_spf_calc = NULL;
704 thread_add_timer_msec(master, ospf6_spf_calculation_thread, ospf6,
705 delay, &ospf6->t_spf_calc);
706 }
707
708 void ospf6_spf_display_subtree(struct vty *vty, const char *prefix, int rest,
709 struct ospf6_vertex *v)
710 {
711 struct listnode *node, *nnode;
712 struct ospf6_vertex *c;
713 char *next_prefix;
714 int len;
715 int restnum;
716
717 /* "prefix" is the space prefix of the display line */
718 vty_out(vty, "%s+-%s [%d]\n", prefix, v->name, v->cost);
719
720 len = strlen(prefix) + 4;
721 next_prefix = (char *)malloc(len);
722 if (next_prefix == NULL) {
723 vty_out(vty, "malloc failed\n");
724 return;
725 }
726 snprintf(next_prefix, len, "%s%s", prefix, (rest ? "| " : " "));
727
728 restnum = listcount(v->child_list);
729 for (ALL_LIST_ELEMENTS(v->child_list, node, nnode, c)) {
730 restnum--;
731 ospf6_spf_display_subtree(vty, next_prefix, restnum, c);
732 }
733
734 free(next_prefix);
735 }
736
737 DEFUN (debug_ospf6_spf_process,
738 debug_ospf6_spf_process_cmd,
739 "debug ospf6 spf process",
740 DEBUG_STR
741 OSPF6_STR
742 "Debug SPF Calculation\n"
743 "Debug Detailed SPF Process\n"
744 )
745 {
746 unsigned char level = 0;
747 level = OSPF6_DEBUG_SPF_PROCESS;
748 OSPF6_DEBUG_SPF_ON(level);
749 return CMD_SUCCESS;
750 }
751
752 DEFUN (debug_ospf6_spf_time,
753 debug_ospf6_spf_time_cmd,
754 "debug ospf6 spf time",
755 DEBUG_STR
756 OSPF6_STR
757 "Debug SPF Calculation\n"
758 "Measure time taken by SPF Calculation\n"
759 )
760 {
761 unsigned char level = 0;
762 level = OSPF6_DEBUG_SPF_TIME;
763 OSPF6_DEBUG_SPF_ON(level);
764 return CMD_SUCCESS;
765 }
766
767 DEFUN (debug_ospf6_spf_database,
768 debug_ospf6_spf_database_cmd,
769 "debug ospf6 spf database",
770 DEBUG_STR
771 OSPF6_STR
772 "Debug SPF Calculation\n"
773 "Log number of LSAs at SPF Calculation time\n"
774 )
775 {
776 unsigned char level = 0;
777 level = OSPF6_DEBUG_SPF_DATABASE;
778 OSPF6_DEBUG_SPF_ON(level);
779 return CMD_SUCCESS;
780 }
781
782 DEFUN (no_debug_ospf6_spf_process,
783 no_debug_ospf6_spf_process_cmd,
784 "no debug ospf6 spf process",
785 NO_STR
786 DEBUG_STR
787 OSPF6_STR
788 "Quit Debugging SPF Calculation\n"
789 "Quit Debugging Detailed SPF Process\n"
790 )
791 {
792 unsigned char level = 0;
793 level = OSPF6_DEBUG_SPF_PROCESS;
794 OSPF6_DEBUG_SPF_OFF(level);
795 return CMD_SUCCESS;
796 }
797
798 DEFUN (no_debug_ospf6_spf_time,
799 no_debug_ospf6_spf_time_cmd,
800 "no debug ospf6 spf time",
801 NO_STR
802 DEBUG_STR
803 OSPF6_STR
804 "Quit Debugging SPF Calculation\n"
805 "Quit Measuring time taken by SPF Calculation\n"
806 )
807 {
808 unsigned char level = 0;
809 level = OSPF6_DEBUG_SPF_TIME;
810 OSPF6_DEBUG_SPF_OFF(level);
811 return CMD_SUCCESS;
812 }
813
814 DEFUN (no_debug_ospf6_spf_database,
815 no_debug_ospf6_spf_database_cmd,
816 "no debug ospf6 spf database",
817 NO_STR
818 DEBUG_STR
819 OSPF6_STR
820 "Debug SPF Calculation\n"
821 "Quit Logging number of LSAs at SPF Calculation time\n"
822 )
823 {
824 unsigned char level = 0;
825 level = OSPF6_DEBUG_SPF_DATABASE;
826 OSPF6_DEBUG_SPF_OFF(level);
827 return CMD_SUCCESS;
828 }
829
830 static int ospf6_timers_spf_set(struct vty *vty, unsigned int delay,
831 unsigned int hold, unsigned int max)
832 {
833 VTY_DECLVAR_CONTEXT(ospf6, ospf);
834
835 ospf->spf_delay = delay;
836 ospf->spf_holdtime = hold;
837 ospf->spf_max_holdtime = max;
838
839 return CMD_SUCCESS;
840 }
841
842 DEFUN (ospf6_timers_throttle_spf,
843 ospf6_timers_throttle_spf_cmd,
844 "timers throttle spf (0-600000) (0-600000) (0-600000)",
845 "Adjust routing timers\n"
846 "Throttling adaptive timer\n"
847 "OSPF6 SPF timers\n"
848 "Delay (msec) from first change received till SPF calculation\n"
849 "Initial hold time (msec) between consecutive SPF calculations\n"
850 "Maximum hold time (msec)\n")
851 {
852 int idx_number = 3;
853 int idx_number_2 = 4;
854 int idx_number_3 = 5;
855 unsigned int delay, hold, max;
856
857 delay = strtoul(argv[idx_number]->arg, NULL, 10);
858 hold = strtoul(argv[idx_number_2]->arg, NULL, 10);
859 max = strtoul(argv[idx_number_3]->arg, NULL, 10);
860
861 return ospf6_timers_spf_set(vty, delay, hold, max);
862 }
863
864 DEFUN (no_ospf6_timers_throttle_spf,
865 no_ospf6_timers_throttle_spf_cmd,
866 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
867 NO_STR
868 "Adjust routing timers\n"
869 "Throttling adaptive timer\n"
870 "OSPF6 SPF timers\n"
871 "Delay (msec) from first change received till SPF calculation\n"
872 "Initial hold time (msec) between consecutive SPF calculations\n"
873 "Maximum hold time (msec)\n")
874 {
875 return ospf6_timers_spf_set(vty, OSPF_SPF_DELAY_DEFAULT,
876 OSPF_SPF_HOLDTIME_DEFAULT,
877 OSPF_SPF_MAX_HOLDTIME_DEFAULT);
878 }
879
880
881 int config_write_ospf6_debug_spf(struct vty *vty)
882 {
883 if (IS_OSPF6_DEBUG_SPF(PROCESS))
884 vty_out(vty, "debug ospf6 spf process\n");
885 if (IS_OSPF6_DEBUG_SPF(TIME))
886 vty_out(vty, "debug ospf6 spf time\n");
887 if (IS_OSPF6_DEBUG_SPF(DATABASE))
888 vty_out(vty, "debug ospf6 spf database\n");
889 return 0;
890 }
891
892 void ospf6_spf_config_write(struct vty *vty)
893 {
894
895 if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT
896 || ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT
897 || ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT)
898 vty_out(vty, " timers throttle spf %d %d %d\n",
899 ospf6->spf_delay, ospf6->spf_holdtime,
900 ospf6->spf_max_holdtime);
901 }
902
903 void install_element_ospf6_debug_spf(void)
904 {
905 install_element(ENABLE_NODE, &debug_ospf6_spf_process_cmd);
906 install_element(ENABLE_NODE, &debug_ospf6_spf_time_cmd);
907 install_element(ENABLE_NODE, &debug_ospf6_spf_database_cmd);
908 install_element(ENABLE_NODE, &no_debug_ospf6_spf_process_cmd);
909 install_element(ENABLE_NODE, &no_debug_ospf6_spf_time_cmd);
910 install_element(ENABLE_NODE, &no_debug_ospf6_spf_database_cmd);
911 install_element(CONFIG_NODE, &debug_ospf6_spf_process_cmd);
912 install_element(CONFIG_NODE, &debug_ospf6_spf_time_cmd);
913 install_element(CONFIG_NODE, &debug_ospf6_spf_database_cmd);
914 install_element(CONFIG_NODE, &no_debug_ospf6_spf_process_cmd);
915 install_element(CONFIG_NODE, &no_debug_ospf6_spf_time_cmd);
916 install_element(CONFIG_NODE, &no_debug_ospf6_spf_database_cmd);
917 }
918
919 void ospf6_spf_init(void)
920 {
921 install_element(OSPF6_NODE, &ospf6_timers_throttle_spf_cmd);
922 install_element(OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd);
923 }
FRRouting mirror