]> 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
release: FRR 3.0-rc1
[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
17 * along with GNU Zebra; see the file COPYING. If not, write to the
18 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 * Boston, MA 02111-1307, USA.
20 */
21
22 /* Shortest Path First calculation for OSPFv3 */
23
24 #include <zebra.h>
25
26 #include "log.h"
27 #include "memory.h"
28 #include "command.h"
29 #include "vty.h"
30 #include "prefix.h"
31 #include "pqueue.h"
32 #include "linklist.h"
33 #include "thread.h"
34
35 #include "ospf6_lsa.h"
36 #include "ospf6_lsdb.h"
37 #include "ospf6_route.h"
38 #include "ospf6_area.h"
39 #include "ospf6_proto.h"
40 #include "ospf6_abr.h"
41 #include "ospf6_spf.h"
42 #include "ospf6_intra.h"
43 #include "ospf6_interface.h"
44 #include "ospf6d.h"
45 #include "ospf6_abr.h"
46
47 unsigned char conf_debug_ospf6_spf = 0;
48
49 static void ospf6_spf_copy_nexthops_to_route(struct ospf6_route *rt,
50 struct ospf6_vertex *v)
51 {
52 if (rt && v)
53 ospf6_copy_nexthops(rt->nh_list, v->nh_list);
54 }
55
56 static void ospf6_spf_merge_nexthops_to_route(struct ospf6_route *rt,
57 struct ospf6_vertex *v)
58 {
59 if (rt && v)
60 ospf6_merge_nexthops(rt->nh_list, v->nh_list);
61 }
62
63 static unsigned int ospf6_spf_get_ifindex_from_nh(struct ospf6_vertex *v)
64 {
65 struct ospf6_nexthop *nh;
66 struct listnode *node;
67
68 if (v) {
69 node = listhead(v->nh_list);
70 if (node) {
71 nh = listgetdata(node);
72 if (nh)
73 return (nh->ifindex);
74 }
75 }
76 return 0;
77 }
78
79 static int ospf6_vertex_cmp(void *a, void *b)
80 {
81 struct ospf6_vertex *va = (struct ospf6_vertex *)a;
82 struct ospf6_vertex *vb = (struct ospf6_vertex *)b;
83
84 /* ascending order */
85 if (va->cost != vb->cost)
86 return (va->cost - vb->cost);
87 return (va->hops - vb->hops);
88 }
89
90 static int ospf6_vertex_id_cmp(void *a, void *b)
91 {
92 struct ospf6_vertex *va = (struct ospf6_vertex *)a;
93 struct ospf6_vertex *vb = (struct ospf6_vertex *)b;
94 int ret = 0;
95
96 ret = ntohl(ospf6_linkstate_prefix_adv_router(&va->vertex_id))
97 - ntohl(ospf6_linkstate_prefix_adv_router(&vb->vertex_id));
98 if (ret)
99 return ret;
100
101 ret = ntohl(ospf6_linkstate_prefix_id(&va->vertex_id))
102 - ntohl(ospf6_linkstate_prefix_id(&vb->vertex_id));
103 return ret;
104 }
105
106 static struct ospf6_vertex *ospf6_vertex_create(struct ospf6_lsa *lsa)
107 {
108 struct ospf6_vertex *v;
109
110 v = (struct ospf6_vertex *)XMALLOC(MTYPE_OSPF6_VERTEX,
111 sizeof(struct ospf6_vertex));
112
113 /* type */
114 if (ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER)
115 v->type = OSPF6_VERTEX_TYPE_ROUTER;
116 else if (ntohs(lsa->header->type) == OSPF6_LSTYPE_NETWORK)
117 v->type = OSPF6_VERTEX_TYPE_NETWORK;
118 else
119 assert(0);
120
121 /* vertex_id */
122 ospf6_linkstate_prefix(lsa->header->adv_router, lsa->header->id,
123 &v->vertex_id);
124
125 /* name */
126 ospf6_linkstate_prefix2str(&v->vertex_id, v->name, sizeof(v->name));
127
128 if (IS_OSPF6_DEBUG_SPF(PROCESS))
129 zlog_debug("%s: Creating vertex %s of type %s", __func__,
130 v->name,
131 ((ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER)
132 ? "Router"
133 : "N/W"));
134
135 /* Associated LSA */
136 v->lsa = lsa;
137
138 /* capability bits + options */
139 v->capability = *(u_char *)(OSPF6_LSA_HEADER_END(lsa->header));
140 v->options[0] = *(u_char *)(OSPF6_LSA_HEADER_END(lsa->header) + 1);
141 v->options[1] = *(u_char *)(OSPF6_LSA_HEADER_END(lsa->header) + 2);
142 v->options[2] = *(u_char *)(OSPF6_LSA_HEADER_END(lsa->header) + 3);
143
144 v->nh_list = list_new();
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(v->nh_list);
156 list_delete(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 (lsa = ospf6_lsdb_type_router_head(type, adv_router, oi->lsdb); lsa;
283 lsa = ospf6_lsdb_type_router_next(type, adv_router, lsa)) {
284 if (VERTEX_IS_TYPE(ROUTER, v)
285 && htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc))
286 != lsa->header->id)
287 continue;
288
289 link_lsa = (struct ospf6_link_lsa *)OSPF6_LSA_HEADER_END(
290 lsa->header);
291 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
292 inet_ntop(AF_INET6, &link_lsa->linklocal_addr, buf,
293 sizeof(buf));
294 zlog_debug(" nexthop %s from %s", buf, lsa->name);
295 }
296
297 ospf6_add_nexthop(w->nh_list, ifindex,
298 &link_lsa->linklocal_addr);
299 i++;
300 }
301
302 if (i == 0 && IS_OSPF6_DEBUG_SPF(PROCESS))
303 zlog_debug("No nexthop for %s found", w->name);
304 }
305
306 static int ospf6_spf_install(struct ospf6_vertex *v,
307 struct ospf6_route_table *result_table)
308 {
309 struct ospf6_route *route, *parent_route;
310 struct ospf6_vertex *prev;
311
312 if (IS_OSPF6_DEBUG_SPF(PROCESS))
313 zlog_debug("SPF install %s hops %d cost %d", v->name, v->hops,
314 v->cost);
315
316 route = ospf6_route_lookup(&v->vertex_id, result_table);
317 if (route && route->path.cost < v->cost) {
318 if (IS_OSPF6_DEBUG_SPF(PROCESS))
319 zlog_debug(
320 " already installed with lower cost (%d), ignore",
321 route->path.cost);
322 ospf6_vertex_delete(v);
323 return -1;
324 } else if (route && route->path.cost == v->cost) {
325 if (IS_OSPF6_DEBUG_SPF(PROCESS))
326 zlog_debug(" another path found, merge");
327
328 ospf6_spf_merge_nexthops_to_route(route, v);
329
330 prev = (struct ospf6_vertex *)route->route_option;
331 assert(prev->hops <= v->hops);
332 ospf6_vertex_delete(v);
333
334 return -1;
335 }
336
337 /* There should be no case where candidate being installed (variable
338 "v") is closer than the one in the SPF tree (variable "route").
339 In the case something has gone wrong with the behavior of
340 Priority-Queue. */
341
342 /* the case where the route exists already is handled and returned
343 up to here. */
344 assert(route == NULL);
345
346 route = ospf6_route_create();
347 memcpy(&route->prefix, &v->vertex_id, sizeof(struct prefix));
348 route->type = OSPF6_DEST_TYPE_LINKSTATE;
349 route->path.type = OSPF6_PATH_TYPE_INTRA;
350 route->path.origin.type = v->lsa->header->type;
351 route->path.origin.id = v->lsa->header->id;
352 route->path.origin.adv_router = v->lsa->header->adv_router;
353 route->path.metric_type = 1;
354 route->path.cost = v->cost;
355 route->path.u.cost_e2 = v->hops;
356 route->path.router_bits = v->capability;
357 route->path.options[0] = v->options[0];
358 route->path.options[1] = v->options[1];
359 route->path.options[2] = v->options[2];
360
361 ospf6_spf_copy_nexthops_to_route(route, v);
362
363 /*
364 * The SPF logic implementation does not transfer the multipathing
365 * properties
366 * of a parent to a child node. Thus if there was a 3-way multipath to a
367 * node's parent and a single hop from the parent to the child, the
368 * logic of
369 * creating new vertices and computing next hops prevents there from
370 * being 3
371 * paths to the child node. This is primarily because the resolution of
372 * multipath is done in this routine, not in the main spf loop.
373 *
374 * The following logic addresses that problem by merging the parent's
375 * nexthop
376 * information with the child's, if the parent is not the root of the
377 * tree.
378 * This is based on the assumption that before a node's route is
379 * installed,
380 * its parent's route's nexthops have already been installed.
381 */
382 if (v->parent && v->parent->hops) {
383 parent_route =
384 ospf6_route_lookup(&v->parent->vertex_id, result_table);
385 if (parent_route) {
386 ospf6_route_merge_nexthops(route, parent_route);
387 }
388 }
389
390 if (v->parent)
391 listnode_add_sort(v->parent->child_list, v);
392 route->route_option = v;
393
394 ospf6_route_add(route, result_table);
395 return 0;
396 }
397
398 void ospf6_spf_table_finish(struct ospf6_route_table *result_table)
399 {
400 struct ospf6_route *route, *nroute;
401 struct ospf6_vertex *v;
402 for (route = ospf6_route_head(result_table); route; route = nroute) {
403 nroute = ospf6_route_next(route);
404 v = (struct ospf6_vertex *)route->route_option;
405 ospf6_vertex_delete(v);
406 ospf6_route_remove(route, result_table);
407 }
408 }
409
410 static const char *ospf6_spf_reason_str[] = {
411 "R+", "R-", "N+", "N-", "L+", "L-", "R*", "N*",
412 };
413
414 void ospf6_spf_reason_string(unsigned int reason, char *buf, int size)
415 {
416 unsigned int bit;
417 int len = 0;
418
419 if (!buf)
420 return;
421
422 for (bit = 0; bit < array_size(ospf6_spf_reason_str); bit++) {
423 if ((reason & (1 << bit)) && (len < size)) {
424 len += snprintf((buf + len), (size - len), "%s%s",
425 (len > 0) ? ", " : "",
426 ospf6_spf_reason_str[bit]);
427 }
428 }
429 }
430
431 /* RFC2328 16.1. Calculating the shortest-path tree for an area */
432 /* RFC2740 3.8.1. Calculating the shortest path tree for an area */
433 void ospf6_spf_calculation(u_int32_t router_id,
434 struct ospf6_route_table *result_table,
435 struct ospf6_area *oa)
436 {
437 struct pqueue *candidate_list;
438 struct ospf6_vertex *root, *v, *w;
439 int size;
440 caddr_t lsdesc;
441 struct ospf6_lsa *lsa;
442 struct in6_addr address;
443
444 ospf6_spf_table_finish(result_table);
445
446 /* Install the calculating router itself as the root of the SPF tree */
447 /* construct root vertex */
448 lsa = ospf6_lsdb_lookup(htons(OSPF6_LSTYPE_ROUTER), htonl(0), router_id,
449 oa->lsdb_self);
450 if (lsa == NULL) {
451 if (IS_OSPF6_DEBUG_SPF(PROCESS))
452 zlog_debug("%s: No router LSA for area %s\n", __func__,
453 oa->name);
454 return;
455 }
456
457 /* initialize */
458 candidate_list = pqueue_create();
459 candidate_list->cmp = ospf6_vertex_cmp;
460
461 root = ospf6_vertex_create(lsa);
462 root->area = oa;
463 root->cost = 0;
464 root->hops = 0;
465 inet_pton(AF_INET6, "::1", &address);
466
467 /* Actually insert root to the candidate-list as the only candidate */
468 pqueue_enqueue(root, candidate_list);
469
470 /* Iterate until candidate-list becomes empty */
471 while (candidate_list->size) {
472 /* get closest candidate from priority queue */
473 v = pqueue_dequeue(candidate_list);
474
475 /* installing may result in merging or rejecting of the vertex
476 */
477 if (ospf6_spf_install(v, result_table) < 0)
478 continue;
479
480 /* Skip overloaded routers */
481 if ((OSPF6_LSA_IS_TYPE(ROUTER, v->lsa)
482 && ospf6_router_is_stub_router(v->lsa)))
483 continue;
484
485 /* For each LS description in the just-added vertex V's LSA */
486 size = (VERTEX_IS_TYPE(ROUTER, v)
487 ? sizeof(struct ospf6_router_lsdesc)
488 : sizeof(struct ospf6_network_lsdesc));
489 for (lsdesc = OSPF6_LSA_HEADER_END(v->lsa->header) + 4;
490 lsdesc + size <= OSPF6_LSA_END(v->lsa->header);
491 lsdesc += size) {
492 lsa = ospf6_lsdesc_lsa(lsdesc, v);
493 if (lsa == NULL)
494 continue;
495
496 if (OSPF6_LSA_IS_MAXAGE(lsa))
497 continue;
498
499 if (!ospf6_lsdesc_backlink(lsa, lsdesc, v))
500 continue;
501
502 w = ospf6_vertex_create(lsa);
503 w->area = oa;
504 w->parent = v;
505 if (VERTEX_IS_TYPE(ROUTER, v)) {
506 w->cost = v->cost
507 + ROUTER_LSDESC_GET_METRIC(lsdesc);
508 w->hops =
509 v->hops
510 + (VERTEX_IS_TYPE(NETWORK, w) ? 0 : 1);
511 } else /* NETWORK */
512 {
513 w->cost = v->cost;
514 w->hops = v->hops + 1;
515 }
516
517 /* nexthop calculation */
518 if (w->hops == 0)
519 ospf6_add_nexthop(
520 w->nh_list,
521 ROUTER_LSDESC_GET_IFID(lsdesc), NULL);
522 else if (w->hops == 1 && v->hops == 0)
523 ospf6_nexthop_calc(w, v, lsdesc);
524 else {
525 ospf6_copy_nexthops(w->nh_list, v->nh_list);
526 }
527
528 /* add new candidate to the candidate_list */
529 if (IS_OSPF6_DEBUG_SPF(PROCESS))
530 zlog_debug(
531 " New candidate: %s hops %d cost %d",
532 w->name, w->hops, w->cost);
533 pqueue_enqueue(w, candidate_list);
534 }
535 }
536
537 pqueue_delete(candidate_list);
538
539 oa->spf_calculation++;
540 }
541
542 static void ospf6_spf_log_database(struct ospf6_area *oa)
543 {
544 char *p, *end, buffer[256];
545 struct listnode *node;
546 struct ospf6_interface *oi;
547
548 p = buffer;
549 end = buffer + sizeof(buffer);
550
551 snprintf(p, end - p, "SPF on DB (#LSAs):");
552 p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) : end);
553 snprintf(p, end - p, " Area %s: %d", oa->name, oa->lsdb->count);
554 p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) : end);
555
556 for (ALL_LIST_ELEMENTS_RO(oa->if_list, node, oi)) {
557 snprintf(p, end - p, " I/F %s: %d", oi->interface->name,
558 oi->lsdb->count);
559 p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer)
560 : end);
561 }
562
563 zlog_debug("%s", buffer);
564 }
565
566 static int ospf6_spf_calculation_thread(struct thread *t)
567 {
568 struct ospf6_area *oa;
569 struct ospf6 *ospf6;
570 struct timeval start, end, runtime;
571 struct listnode *node;
572 int areas_processed = 0;
573 char rbuf[32];
574
575 ospf6 = (struct ospf6 *)THREAD_ARG(t);
576 ospf6->t_spf_calc = NULL;
577
578 /* execute SPF calculation */
579 monotime(&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 if (IS_OSPF6_DEBUG_SPF(PROCESS))
590 zlog_debug("SPF calculation for Area %s", oa->name);
591 if (IS_OSPF6_DEBUG_SPF(DATABASE))
592 ospf6_spf_log_database(oa);
593
594 ospf6_spf_calculation(ospf6->router_id, oa->spf_table, oa);
595 ospf6_intra_route_calculation(oa);
596 ospf6_intra_brouter_calculation(oa);
597
598 areas_processed++;
599 }
600
601 if (ospf6->backbone) {
602 if (IS_OSPF6_DEBUG_SPF(PROCESS))
603 zlog_debug("SPF calculation for Backbone area %s",
604 ospf6->backbone->name);
605 if (IS_OSPF6_DEBUG_SPF(DATABASE))
606 ospf6_spf_log_database(ospf6->backbone);
607
608 ospf6_spf_calculation(ospf6->router_id,
609 ospf6->backbone->spf_table,
610 ospf6->backbone);
611 ospf6_intra_route_calculation(ospf6->backbone);
612 ospf6_intra_brouter_calculation(ospf6->backbone);
613 areas_processed++;
614 }
615
616 if (ospf6_is_router_abr(ospf6))
617 ospf6_abr_defaults_to_stub(ospf6);
618
619 monotime(&end);
620 timersub(&end, &start, &runtime);
621
622 ospf6->ts_spf_duration = runtime;
623
624 ospf6_spf_reason_string(ospf6->spf_reason, rbuf, sizeof(rbuf));
625
626 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
627 zlog_debug("SPF runtime: %lld sec %lld usec",
628 (long long)runtime.tv_sec,
629 (long long)runtime.tv_usec);
630
631 zlog_info(
632 "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
633 "Reason: %s\n",
634 areas_processed, (long long)runtime.tv_sec,
635 (long long)runtime.tv_usec, rbuf);
636 ospf6->last_spf_reason = ospf6->spf_reason;
637 ospf6_reset_spf_reason(ospf6);
638 return 0;
639 }
640
641 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
642 set timer for SPF calc. */
643 void ospf6_spf_schedule(struct ospf6 *ospf6, unsigned int reason)
644 {
645 unsigned long delay, elapsed, ht;
646
647 ospf6_set_spf_reason(ospf6, reason);
648
649 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) {
650 char rbuf[32];
651 ospf6_spf_reason_string(reason, rbuf, sizeof(rbuf));
652 zlog_debug("SPF: calculation timer scheduled (reason %s)",
653 rbuf);
654 }
655
656 /* OSPF instance does not exist. */
657 if (ospf6 == NULL)
658 return;
659
660 /* SPF calculation timer is already scheduled. */
661 if (ospf6->t_spf_calc) {
662 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
663 zlog_debug(
664 "SPF: calculation timer is already scheduled: %p",
665 (void *)ospf6->t_spf_calc);
666 return;
667 }
668
669 elapsed = monotime_since(&ospf6->ts_spf, NULL) / 1000LL;
670 ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier;
671
672 if (ht > ospf6->spf_max_holdtime)
673 ht = ospf6->spf_max_holdtime;
674
675 /* Get SPF calculation delay time. */
676 if (elapsed < ht) {
677 /* Got an event within the hold time of last SPF. We need to
678 * increase the hold_multiplier, if it's not already at/past
679 * maximum value, and wasn't already increased..
680 */
681 if (ht < ospf6->spf_max_holdtime)
682 ospf6->spf_hold_multiplier++;
683
684 /* always honour the SPF initial delay */
685 if ((ht - elapsed) < ospf6->spf_delay)
686 delay = ospf6->spf_delay;
687 else
688 delay = ht - elapsed;
689 } else {
690 /* Event is past required hold-time of last SPF */
691 delay = ospf6->spf_delay;
692 ospf6->spf_hold_multiplier = 1;
693 }
694
695 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
696 zlog_debug("SPF: calculation timer delay = %ld", delay);
697
698 zlog_info("SPF: Scheduled in %ld msec", delay);
699
700 ospf6->t_spf_calc = thread_add_timer_msec(
701 master, ospf6_spf_calculation_thread, ospf6, delay);
702 }
703
704 void ospf6_spf_display_subtree(struct vty *vty, const char *prefix, int rest,
705 struct ospf6_vertex *v)
706 {
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]%s", prefix, v->name, v->cost, VNL);
715
716 len = strlen(prefix) + 4;
717 next_prefix = (char *)malloc(len);
718 if (next_prefix == NULL) {
719 vty_out(vty, "malloc failed%s", VNL);
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);
731 }
732
733 DEFUN (debug_ospf6_spf_process,
734 debug_ospf6_spf_process_cmd,
735 "debug ospf6 spf process",
736 DEBUG_STR
737 OSPF6_STR
738 "Debug SPF Calculation\n"
739 "Debug Detailed SPF Process\n"
740 )
741 {
742 unsigned char level = 0;
743 level = OSPF6_DEBUG_SPF_PROCESS;
744 OSPF6_DEBUG_SPF_ON(level);
745 return CMD_SUCCESS;
746 }
747
748 DEFUN (debug_ospf6_spf_time,
749 debug_ospf6_spf_time_cmd,
750 "debug ospf6 spf time",
751 DEBUG_STR
752 OSPF6_STR
753 "Debug SPF Calculation\n"
754 "Measure time taken by SPF Calculation\n"
755 )
756 {
757 unsigned char level = 0;
758 level = OSPF6_DEBUG_SPF_TIME;
759 OSPF6_DEBUG_SPF_ON(level);
760 return CMD_SUCCESS;
761 }
762
763 DEFUN (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 {
772 unsigned char level = 0;
773 level = OSPF6_DEBUG_SPF_DATABASE;
774 OSPF6_DEBUG_SPF_ON(level);
775 return CMD_SUCCESS;
776 }
777
778 DEFUN (no_debug_ospf6_spf_process,
779 no_debug_ospf6_spf_process_cmd,
780 "no debug ospf6 spf process",
781 NO_STR
782 DEBUG_STR
783 OSPF6_STR
784 "Quit Debugging SPF Calculation\n"
785 "Quit Debugging Detailed SPF Process\n"
786 )
787 {
788 unsigned char level = 0;
789 level = OSPF6_DEBUG_SPF_PROCESS;
790 OSPF6_DEBUG_SPF_OFF(level);
791 return CMD_SUCCESS;
792 }
793
794 DEFUN (no_debug_ospf6_spf_time,
795 no_debug_ospf6_spf_time_cmd,
796 "no debug ospf6 spf time",
797 NO_STR
798 DEBUG_STR
799 OSPF6_STR
800 "Quit Debugging SPF Calculation\n"
801 "Quit Measuring time taken by SPF Calculation\n"
802 )
803 {
804 unsigned char level = 0;
805 level = OSPF6_DEBUG_SPF_TIME;
806 OSPF6_DEBUG_SPF_OFF(level);
807 return CMD_SUCCESS;
808 }
809
810 DEFUN (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 {
820 unsigned char level = 0;
821 level = OSPF6_DEBUG_SPF_DATABASE;
822 OSPF6_DEBUG_SPF_OFF(level);
823 return CMD_SUCCESS;
824 }
825
826 static int ospf6_timers_spf_set(struct vty *vty, unsigned int delay,
827 unsigned int hold, unsigned int max)
828 {
829 VTY_DECLVAR_CONTEXT(ospf6, ospf);
830
831 ospf->spf_delay = delay;
832 ospf->spf_holdtime = hold;
833 ospf->spf_max_holdtime = max;
834
835 return CMD_SUCCESS;
836 }
837
838 DEFUN (ospf6_timers_throttle_spf,
839 ospf6_timers_throttle_spf_cmd,
840 "timers throttle spf (0-600000) (0-600000) (0-600000)",
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 {
848 int idx_number = 3;
849 int idx_number_2 = 4;
850 int idx_number_3 = 5;
851 unsigned int delay, hold, max;
852
853 VTY_GET_INTEGER_RANGE("SPF delay timer", delay, argv[idx_number]->arg,
854 0, 600000);
855 VTY_GET_INTEGER_RANGE("SPF hold timer", hold, argv[idx_number_2]->arg,
856 0, 600000);
857 VTY_GET_INTEGER_RANGE("SPF max-hold timer", max,
858 argv[idx_number_3]->arg, 0, 600000);
859
860 return ospf6_timers_spf_set(vty, delay, hold, max);
861 }
862
863 DEFUN (no_ospf6_timers_throttle_spf,
864 no_ospf6_timers_throttle_spf_cmd,
865 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
866 NO_STR
867 "Adjust routing timers\n"
868 "Throttling adaptive timer\n"
869 "OSPF6 SPF timers\n"
870 "Delay (msec) from first change received till SPF calculation\n"
871 "Initial hold time (msec) between consecutive SPF calculations\n"
872 "Maximum hold time (msec)\n")
873 {
874 return ospf6_timers_spf_set(vty, OSPF_SPF_DELAY_DEFAULT,
875 OSPF_SPF_HOLDTIME_DEFAULT,
876 OSPF_SPF_MAX_HOLDTIME_DEFAULT);
877 }
878
879
880 int config_write_ospf6_debug_spf(struct vty *vty)
881 {
882 if (IS_OSPF6_DEBUG_SPF(PROCESS))
883 vty_out(vty, "debug ospf6 spf process%s", VNL);
884 if (IS_OSPF6_DEBUG_SPF(TIME))
885 vty_out(vty, "debug ospf6 spf time%s", VNL);
886 if (IS_OSPF6_DEBUG_SPF(DATABASE))
887 vty_out(vty, "debug ospf6 spf database%s", VNL);
888 return 0;
889 }
890
891 void ospf6_spf_config_write(struct vty *vty)
892 {
893
894 if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT
895 || ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT
896 || ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT)
897 vty_out(vty, " timers throttle spf %d %d %d%s",
898 ospf6->spf_delay, ospf6->spf_holdtime,
899 ospf6->spf_max_holdtime, VTY_NEWLINE);
900 }
901
902 void install_element_ospf6_debug_spf(void)
903 {
904 install_element(ENABLE_NODE, &debug_ospf6_spf_process_cmd);
905 install_element(ENABLE_NODE, &debug_ospf6_spf_time_cmd);
906 install_element(ENABLE_NODE, &debug_ospf6_spf_database_cmd);
907 install_element(ENABLE_NODE, &no_debug_ospf6_spf_process_cmd);
908 install_element(ENABLE_NODE, &no_debug_ospf6_spf_time_cmd);
909 install_element(ENABLE_NODE, &no_debug_ospf6_spf_database_cmd);
910 install_element(CONFIG_NODE, &debug_ospf6_spf_process_cmd);
911 install_element(CONFIG_NODE, &debug_ospf6_spf_time_cmd);
912 install_element(CONFIG_NODE, &debug_ospf6_spf_database_cmd);
913 install_element(CONFIG_NODE, &no_debug_ospf6_spf_process_cmd);
914 install_element(CONFIG_NODE, &no_debug_ospf6_spf_time_cmd);
915 install_element(CONFIG_NODE, &no_debug_ospf6_spf_database_cmd);
916 }
917
918 void ospf6_spf_init(void)
919 {
920 install_element(OSPF6_NODE, &ospf6_timers_throttle_spf_cmd);
921 install_element(OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd);
922 }
FRRouting mirror