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