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