]> 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
ospf6d: missing ECMP NHs in certain topologies
[mirror_frr.git] / ospf6d / ospf6_spf.c
CommitLineData
acddc0ed 1// SPDX-License-Identifier: GPL-2.0-or-later
718e3744 2/*
508e53e2 3 * Copyright (C) 2003 Yasuhiro Ohara
718e3744 4 */
508e53e2 5
718e3744 6/* Shortest Path First calculation for OSPFv3 */
7
508e53e2 8#include <zebra.h>
718e3744 9
508e53e2 10#include "log.h"
11#include "memory.h"
12#include "command.h"
13#include "vty.h"
718e3744 14#include "prefix.h"
508e53e2 15#include "linklist.h"
24a58196 16#include "frrevent.h"
4ba03be5 17#include "lib_errors.h"
718e3744 18
718e3744 19#include "ospf6_lsa.h"
20#include "ospf6_lsdb.h"
21#include "ospf6_route.h"
508e53e2 22#include "ospf6_area.h"
ca1f4309
DS		 23#include "ospf6_proto.h"
24#include "ospf6_abr.h"
ad500b22 25#include "ospf6_asbr.h"
718e3744 26#include "ospf6_spf.h"
508e53e2 27#include "ospf6_intra.h"
718e3744 28#include "ospf6_interface.h"
049207c3 29#include "ospf6d.h"
1f9a9fff 30#include "ospf6_abr.h"
ad500b22 31#include "ospf6_nssa.h"
71165098 32#include "ospf6_zebra.h"
718e3744 33
30043e4c
DL		 34DEFINE_MTYPE_STATIC(OSPF6D, OSPF6_VERTEX, "OSPF6 vertex");
35
508e53e2 36unsigned char conf_debug_ospf6_spf = 0;
718e3744 37
d62a17ae 38static void ospf6_spf_copy_nexthops_to_route(struct ospf6_route *rt,
39 struct ospf6_vertex *v)
c3c0ac83 40{
d62a17ae 41 if (rt && v)
42 ospf6_copy_nexthops(rt->nh_list, v->nh_list);
c3c0ac83
DS		 43}
44
d62a17ae 45static void ospf6_spf_merge_nexthops_to_route(struct ospf6_route *rt,
46 struct ospf6_vertex *v)
c3c0ac83 47{
d62a17ae 48 if (rt && v)
49 ospf6_merge_nexthops(rt->nh_list, v->nh_list);
c3c0ac83
DS		 50}
51
d62a17ae 52static unsigned int ospf6_spf_get_ifindex_from_nh(struct ospf6_vertex *v)
c3c0ac83 53{
d62a17ae 54 struct ospf6_nexthop *nh;
55 struct listnode *node;
56
57 if (v) {
58 node = listhead(v->nh_list);
59 if (node) {
60 nh = listgetdata(node);
61 if (nh)
62 return (nh->ifindex);
63 }
c3c0ac83 64 }
d62a17ae 65 return 0;
c3c0ac83
DS		 66}
67
4ab0496e
DL		 68static int ospf6_vertex_cmp(const struct ospf6_vertex *va,
69 const struct ospf6_vertex *vb)
718e3744 70{
d62a17ae 71 /* ascending order */
72 if (va->cost != vb->cost)
73 return (va->cost - vb->cost);
4ab0496e
DL		 74 if (va->hops != vb->hops)
75 return (va->hops - vb->hops);
76 return 0;
718e3744 77}
4ab0496e 78DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue, struct ospf6_vertex, pqi,
960b9a53 79 ospf6_vertex_cmp);
718e3744 80
d62a17ae 81static int ospf6_vertex_id_cmp(void *a, void *b)
718e3744 82{
d62a17ae 83 struct ospf6_vertex *va = (struct ospf6_vertex *)a;
84 struct ospf6_vertex *vb = (struct ospf6_vertex *)b;
85 int ret = 0;
86
87 ret = ntohl(ospf6_linkstate_prefix_adv_router(&va->vertex_id))
88 - ntohl(ospf6_linkstate_prefix_adv_router(&vb->vertex_id));
89 if (ret)
90 return ret;
91
92 ret = ntohl(ospf6_linkstate_prefix_id(&va->vertex_id))
93 - ntohl(ospf6_linkstate_prefix_id(&vb->vertex_id));
94 return ret;
718e3744 95}
96
d62a17ae 97static struct ospf6_vertex *ospf6_vertex_create(struct ospf6_lsa *lsa)
718e3744 98{
d62a17ae 99 struct ospf6_vertex *v;
718e3744 100
9f5dc319 101 v = XMALLOC(MTYPE_OSPF6_VERTEX, sizeof(struct ospf6_vertex));
718e3744 102
d62a17ae 103 /* type */
26e14616 104 if (ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER) {
d62a17ae 105 v->type = OSPF6_VERTEX_TYPE_ROUTER;
26e14616
CS		 106 /* Router LSA use Link ID 0 as base in vertex_id */
107 ospf6_linkstate_prefix(lsa->header->adv_router, htonl(0),
996c9314 108 &v->vertex_id);
26e14616 109 } else if (ntohs(lsa->header->type) == OSPF6_LSTYPE_NETWORK) {
d62a17ae 110 v->type = OSPF6_VERTEX_TYPE_NETWORK;
26e14616
CS		 111 /* vertex_id */
112 ospf6_linkstate_prefix(lsa->header->adv_router, lsa->header->id,
996c9314 113 &v->vertex_id);
26e14616
CS		 114 } else
115 assert(0);
718e3744 116
d62a17ae 117 /* name */
118 ospf6_linkstate_prefix2str(&v->vertex_id, v->name, sizeof(v->name));
718e3744 119
d62a17ae 120 if (IS_OSPF6_DEBUG_SPF(PROCESS))
26e14616
CS		 121 zlog_debug("%s: Creating vertex %s of type %s (0x%04hx) lsa %s",
122 __func__, v->name,
d62a17ae 123 ((ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER)
124 ? "Router"
996c9314
LB		 125 : "N/W"),
126 ntohs(lsa->header->type), lsa->name);
26e14616 127
c3c0ac83 128
d62a17ae 129 /* Associated LSA */
130 v->lsa = lsa;
718e3744 131
d62a17ae 132 /* capability bits + options */
d7c0a89a
QY		 133 v->capability = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa->header));
134 v->options[0] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa->header) + 1);
135 v->options[1] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa->header) + 2);
136 v->options[2] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa->header) + 3);
718e3744 137
d62a17ae 138 v->nh_list = list_new();
064d4355 139 v->nh_list->cmp = (int (*)(void *, void *))ospf6_nexthop_cmp;
996c9314 140 v->nh_list->del = (void (*)(void *))ospf6_nexthop_delete;
718e3744 141
d62a17ae 142 v->parent = NULL;
143 v->child_list = list_new();
144 v->child_list->cmp = ospf6_vertex_id_cmp;
718e3744 145
d62a17ae 146 return v;
718e3744 147}
148
d62a17ae 149static void ospf6_vertex_delete(struct ospf6_vertex *v)
718e3744 150{
6a154c88
DL		 151 list_delete(&v->nh_list);
152 list_delete(&v->child_list);
d62a17ae 153 XFREE(MTYPE_OSPF6_VERTEX, v);
718e3744 154}
155
d62a17ae 156static struct ospf6_lsa *ospf6_lsdesc_lsa(caddr_t lsdesc,
da086a3b 157 struct ospf6_vertex *v)
718e3744 158{
da086a3b 159 struct ospf6_lsa *lsa = NULL;
d7c0a89a
QY		 160 uint16_t type = 0;
161 uint32_t id = 0, adv_router = 0;
d62a17ae 162
163 if (VERTEX_IS_TYPE(NETWORK, v)) {
164 type = htons(OSPF6_LSTYPE_ROUTER);
da086a3b 165 id = htonl(0);
d62a17ae 166 adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc);
167 } else {
168 if (ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, lsdesc)) {
169 type = htons(OSPF6_LSTYPE_ROUTER);
da086a3b 170 id = htonl(0);
d62a17ae 171 adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc);
172 } else if (ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK, lsdesc)) {
173 type = htons(OSPF6_LSTYPE_NETWORK);
174 id = htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc));
175 adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc);
176 }
177 }
178
da086a3b
CS		 179 if (type == htons(OSPF6_LSTYPE_NETWORK))
180 lsa = ospf6_lsdb_lookup(type, id, adv_router, v->area->lsdb);
181 else
182 lsa = ospf6_create_single_router_lsa(v->area, v->area->lsdb,
183 adv_router);
d62a17ae 184 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
185 char ibuf[16], abuf[16];
186 inet_ntop(AF_INET, &id, ibuf, sizeof(ibuf));
187 inet_ntop(AF_INET, &adv_router, abuf, sizeof(abuf));
188 if (lsa)
da086a3b
CS		 189 zlog_debug(" Link to: %s len %u, V %s", lsa->name,
190 ntohs(lsa->header->length), v->name);
d62a17ae 191 else
da086a3b 192 zlog_debug(" Link to: [%s Id:%s Adv:%s] No LSA , V %s",
26e14616 193 ospf6_lstype_name(type), ibuf, abuf,
da086a3b 194 v->name);
d62a17ae 195 }
196
197 return lsa;
718e3744 198}
199
d62a17ae 200static char *ospf6_lsdesc_backlink(struct ospf6_lsa *lsa, caddr_t lsdesc,
201 struct ospf6_vertex *v)
718e3744 202{
d62a17ae 203 caddr_t backlink, found = NULL;
204 int size;
205
206 size = (OSPF6_LSA_IS_TYPE(ROUTER, lsa)
207 ? sizeof(struct ospf6_router_lsdesc)
208 : sizeof(struct ospf6_network_lsdesc));
209 for (backlink = OSPF6_LSA_HEADER_END(lsa->header) + 4;
210 backlink + size <= OSPF6_LSA_END(lsa->header); backlink += size) {
211 assert(!(OSPF6_LSA_IS_TYPE(NETWORK, lsa)
212 && VERTEX_IS_TYPE(NETWORK, v)));
213
ff2052ee
CH		 214 if (OSPF6_LSA_IS_TYPE(NETWORK, lsa)) {
215 if (NETWORK_LSDESC_GET_NBR_ROUTERID(backlink)
216 == v->lsa->header->adv_router)
217 found = backlink;
218 } else if (VERTEX_IS_TYPE(NETWORK, v)) {
219 if (ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK, backlink)
220 && ROUTER_LSDESC_GET_NBR_ROUTERID(backlink)
221 == v->lsa->header->adv_router
222 && ROUTER_LSDESC_GET_NBR_IFID(backlink)
223 == ntohl(v->lsa->header->id))
224 found = backlink;
225 } else {
226 assert(OSPF6_LSA_IS_TYPE(ROUTER, lsa)
227 && VERTEX_IS_TYPE(ROUTER, v));
228
d62a17ae 229 if (!ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, backlink)
230 || !ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, lsdesc))
231 continue;
ff2052ee 232
d62a17ae 233 if (ROUTER_LSDESC_GET_NBR_IFID(backlink)
234 != ROUTER_LSDESC_GET_IFID(lsdesc)
235 || ROUTER_LSDESC_GET_NBR_IFID(lsdesc)
236 != ROUTER_LSDESC_GET_IFID(backlink))
237 continue;
238 if (ROUTER_LSDESC_GET_NBR_ROUTERID(backlink)
239 != v->lsa->header->adv_router
240 || ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc)
241 != lsa->header->adv_router)
242 continue;
243 found = backlink;
244 }
245 }
246
247 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1ba43456
CS		 248 zlog_debug("Vertex %s Lsa %s Backlink %s", v->name, lsa->name,
249 (found ? "OK" : "FAIL"));
d62a17ae 250
251 return found;
718e3744 252}
253
d62a17ae 254static void ospf6_nexthop_calc(struct ospf6_vertex *w, struct ospf6_vertex *v,
beadc736 255 caddr_t lsdesc, struct ospf6 *ospf6)
718e3744 256{
d62a17ae 257 int i;
258 ifindex_t ifindex;
259 struct ospf6_interface *oi;
d7c0a89a
QY		 260 uint16_t type;
261 uint32_t adv_router;
d62a17ae 262 struct ospf6_lsa *lsa;
263 struct ospf6_link_lsa *link_lsa;
264 char buf[64];
265
266 assert(VERTEX_IS_TYPE(ROUTER, w));
267 ifindex = (VERTEX_IS_TYPE(NETWORK, v) ? ospf6_spf_get_ifindex_from_nh(v)
268 : ROUTER_LSDESC_GET_IFID(lsdesc));
269 if (ifindex == 0) {
1c50c1c0
QY		 270 flog_err(EC_LIB_DEVELOPMENT, "No nexthop ifindex at vertex %s",
271 v->name);
d62a17ae 272 return;
273 }
274
c5d28568 275 oi = ospf6_interface_lookup_by_ifindex(ifindex, ospf6->vrf_id);
d62a17ae 276 if (oi == NULL) {
1b1f7b4f 277 zlog_warn("Can't find interface in SPF: ifindex %d", ifindex);
d62a17ae 278 return;
279 }
280
281 type = htons(OSPF6_LSTYPE_LINK);
282 adv_router = (VERTEX_IS_TYPE(NETWORK, v)
283 ? NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc)
284 : ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc));
285
286 i = 0;
287 for (ALL_LSDB_TYPED_ADVRTR(oi->lsdb, type, adv_router, lsa)) {
288 if (VERTEX_IS_TYPE(ROUTER, v)
289 && htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc))
290 != lsa->header->id)
291 continue;
292
293 link_lsa = (struct ospf6_link_lsa *)OSPF6_LSA_HEADER_END(
294 lsa->header);
295 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
296 inet_ntop(AF_INET6, &link_lsa->linklocal_addr, buf,
297 sizeof(buf));
298 zlog_debug(" nexthop %s from %s", buf, lsa->name);
299 }
300
301 ospf6_add_nexthop(w->nh_list, ifindex,
302 &link_lsa->linklocal_addr);
303 i++;
304 }
305
306 if (i == 0 && IS_OSPF6_DEBUG_SPF(PROCESS))
307 zlog_debug("No nexthop for %s found", w->name);
718e3744 308}
309
d62a17ae 310static int ospf6_spf_install(struct ospf6_vertex *v,
e285b70d 311 struct ospf6_route_table *result_table)
718e3744 312{
637e6f29 313 struct ospf6_route *route;
d62a17ae 314 struct ospf6_vertex *prev;
315
316 if (IS_OSPF6_DEBUG_SPF(PROCESS))
26e14616
CS		 317 zlog_debug("SPF install %s (lsa %s) hops %d cost %d", v->name,
318 v->lsa->name, v->hops, v->cost);
d62a17ae 319
320 route = ospf6_route_lookup(&v->vertex_id, result_table);
321 if (route && route->path.cost < v->cost) {
322 if (IS_OSPF6_DEBUG_SPF(PROCESS))
323 zlog_debug(
324 " already installed with lower cost (%d), ignore",
325 route->path.cost);
326 ospf6_vertex_delete(v);
327 return -1;
328 } else if (route && route->path.cost == v->cost) {
2dbe669b 329 if (IS_OSPF6_DEBUG_SPF(PROCESS))
996c9314 330 zlog_debug(
2dbe669b
DA		 331 " another path found to route %pFX lsa %s, merge",
332 &route->prefix, v->lsa->name);
637e6f29 333
334 /* merging the parent's nexthop information to the child's
335 * if the parent is not the root of the tree.
336 */
337 if (!ospf6_merge_parents_nh_to_child(v, route, result_table))
338 ospf6_spf_merge_nexthops_to_route(route, v);
d62a17ae 339
340 prev = (struct ospf6_vertex *)route->route_option;
341 assert(prev->hops <= v->hops);
d62a17ae 342
996c9314
LB		 343 if ((VERTEX_IS_TYPE(ROUTER, v)
344 && route->path.origin.id != v->lsa->header->id)) {
26e14616 345 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
996c9314
LB		 346 zlog_debug(
347 "%s: V lsa %s id %u, route id %u are different",
15569c58 348 __func__, v->lsa->name,
996c9314
LB		 349 ntohl(v->lsa->header->id),
350 ntohl(route->path.origin.id));
26e14616
CS		 351 }
352 return 0;
353 }
354
355 ospf6_vertex_delete(v);
d62a17ae 356 return -1;
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
22813fdb 368 route = ospf6_route_create(v->area->ospf6);
d62a17ae 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 */
637e6f29 404 ospf6_merge_parents_nh_to_child(v, route, result_table);
d62a17ae 405
406 if (v->parent)
407 listnode_add_sort(v->parent->child_list, v);
408 route->route_option = v;
508e53e2 409
e285b70d 410 ospf6_route_add(route, result_table);
d62a17ae 411 return 0;
718e3744 412}
413
e285b70d 414void ospf6_spf_table_finish(struct ospf6_route_table *result_table)
718e3744 415{
d62a17ae 416 struct ospf6_route *route, *nroute;
417 struct ospf6_vertex *v;
418 for (route = ospf6_route_head(result_table); route; route = nroute) {
419 nroute = ospf6_route_next(route);
420 v = (struct ospf6_vertex *)route->route_option;
421 ospf6_vertex_delete(v);
e285b70d 422 ospf6_route_remove(route, result_table);
d62a17ae 423 }
718e3744 424}
425
71165098 426static const char *const ospf6_spf_reason_str[] = {
d0606e0a
DS		 427 "R+", /* OSPF6_SPF_FLAGS_ROUTER_LSA_ADDED */
428 "R-", /* OSPF6_SPF_FLAGS_ROUTER_LSA_REMOVED */
429 "N+", /* OSPF6_SPF_FLAGS_NETWORK_LSA_ADDED */
430 "N-", /* OSPF6_SPF_FLAGS_NETWORK_LSA_REMOVED */
431 "L+", /* OSPF6_SPF_FLAGS_NETWORK_LINK_LSA_ADDED */
432 "L-", /* OSPF6_SPF_FLAGS_NETWORK_LINK_LSA_REMOVED */
433 "R*", /* OSPF6_SPF_FLAGS_ROUTER_LSA_ORIGINATED */
434 "N*", /* OSPF6_SPF_FLAGS_NETWORK_LSA_ORIGINATED */
435 "C", /* OSPF6_SPF_FLAGS_CONFIG_CHANGE */
436 "A", /* OSPF6_SPF_FLAGS_ASBR_STATUS_CHANGE */
437 "GR", /* OSPF6_SPF_FLAGS_GR_FINISH */
438};
439
440void ospf6_spf_reason_string(uint32_t reason, char *buf, int size)
a0edf674 441{
d0606e0a 442 uint32_t bit;
d62a17ae 443 int len = 0;
444
445 if (!buf)
446 return;
447
f13d33cc
PG		 448 if (!reason) {
449 buf[0] = '\0';
450 return;
451 }
d62a17ae 452 for (bit = 0; bit < array_size(ospf6_spf_reason_str); bit++) {
453 if ((reason & (1 << bit)) && (len < size)) {
454 len += snprintf((buf + len), (size - len), "%s%s",
455 (len > 0) ? ", " : "",
456 ospf6_spf_reason_str[bit]);
457 }
a0edf674 458 }
a0edf674
DD		 459}
460
6452df09 461/* RFC2328 16.1. Calculating the shortest-path tree for an area */
462/* RFC2740 3.8.1. Calculating the shortest path tree for an area */
d7c0a89a 463void ospf6_spf_calculation(uint32_t router_id,
d62a17ae 464 struct ospf6_route_table *result_table,
465 struct ospf6_area *oa)
508e53e2 466{
4ab0496e 467 struct vertex_pqueue_head candidate_list;
d62a17ae 468 struct ospf6_vertex *root, *v, *w;
469 int size;
470 caddr_t lsdesc;
da086a3b 471 struct ospf6_lsa *lsa;
d62a17ae 472 struct in6_addr address;
473
e285b70d 474 ospf6_spf_table_finish(result_table);
d62a17ae 475
476 /* Install the calculating router itself as the root of the SPF tree */
477 /* construct root vertex */
da086a3b 478 lsa = ospf6_create_single_router_lsa(oa, oa->lsdb_self, router_id);
d62a17ae 479 if (lsa == NULL) {
1b1f7b4f 480 zlog_warn("%s: No router LSA for area %s", __func__, oa->name);
d62a17ae 481 return;
482 }
483
484 /* initialize */
4ab0496e 485 vertex_pqueue_init(&candidate_list);
d62a17ae 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 */
4ab0496e 495 vertex_pqueue_add(&candidate_list, root);
d62a17ae 496
497 /* Iterate until candidate-list becomes empty */
4ab0496e 498 while ((v = vertex_pqueue_pop(&candidate_list))) {
d62a17ae 499 /* installing may result in merging or rejecting of the vertex
500 */
e285b70d 501 if (ospf6_spf_install(v, result_table) < 0)
d62a17ae 502 continue;
503
504 /* Skip overloaded routers */
505 if ((OSPF6_LSA_IS_TYPE(ROUTER, v->lsa)
506 && ospf6_router_is_stub_router(v->lsa)))
507 continue;
508
da086a3b
CS		 509 /* For each LS description in the just-added vertex V's LSA */
510 size = (VERTEX_IS_TYPE(ROUTER, v)
511 ? sizeof(struct ospf6_router_lsdesc)
512 : sizeof(struct ospf6_network_lsdesc));
513 for (lsdesc = OSPF6_LSA_HEADER_END(v->lsa->header) + 4;
514 lsdesc + size <= OSPF6_LSA_END(v->lsa->header);
515 lsdesc += size) {
516 lsa = ospf6_lsdesc_lsa(lsdesc, v);
517 if (lsa == NULL)
518 continue;
519
520 if (OSPF6_LSA_IS_MAXAGE(lsa))
521 continue;
522
523 if (!ospf6_lsdesc_backlink(lsa, lsdesc, v))
524 continue;
525
526 w = ospf6_vertex_create(lsa);
527 w->area = oa;
528 w->parent = v;
529 if (VERTEX_IS_TYPE(ROUTER, v)) {
530 w->cost = v->cost
26e14616 531 + ROUTER_LSDESC_GET_METRIC(lsdesc);
da086a3b
CS		 532 w->hops =
533 v->hops
534 + (VERTEX_IS_TYPE(NETWORK, w) ? 0 : 1);
535 } else {
536 /* NETWORK */
537 w->cost = v->cost;
538 w->hops = v->hops + 1;
539 }
540
541 /* nexthop calculation */
542 if (w->hops == 0)
543 ospf6_add_nexthop(
544 w->nh_list,
d62a17ae 545 ROUTER_LSDESC_GET_IFID(lsdesc), NULL);
da086a3b 546 else if (w->hops == 1 && v->hops == 0)
beadc736 547 ospf6_nexthop_calc(w, v, lsdesc, oa->ospf6);
da086a3b
CS		 548 else
549 ospf6_copy_nexthops(w->nh_list, v->nh_list);
550
551
552 /* add new candidate to the candidate_list */
553 if (IS_OSPF6_DEBUG_SPF(PROCESS))
554 zlog_debug(
d62a17ae 555 " New candidate: %s hops %d cost %d",
996c9314 556 w->name, w->hops, w->cost);
4ab0496e 557 vertex_pqueue_add(&candidate_list, w);
d62a17ae 558 }
559 }
560
4ab0496e 561 //vertex_pqueue_fini(&candidate_list);
d62a17ae 562
da086a3b
CS		 563 ospf6_remove_temp_router_lsa(oa);
564
d62a17ae 565 oa->spf_calculation++;
718e3744 566}
567
d62a17ae 568static void ospf6_spf_log_database(struct ospf6_area *oa)
2680aa2b 569{
d62a17ae 570 char *p, *end, buffer[256];
571 struct listnode *node;
572 struct ospf6_interface *oi;
573
574 p = buffer;
575 end = buffer + sizeof(buffer);
576
577 snprintf(p, end - p, "SPF on DB (#LSAs):");
578 p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) : end);
579 snprintf(p, end - p, " Area %s: %d", oa->name, oa->lsdb->count);
580 p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) : end);
581
582 for (ALL_LIST_ELEMENTS_RO(oa->if_list, node, oi)) {
583 snprintf(p, end - p, " I/F %s: %d", oi->interface->name,
584 oi->lsdb->count);
585 p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer)
586 : end);
587 }
588
589 zlog_debug("%s", buffer);
2680aa2b 590}
591
e6685141 592static void ospf6_spf_calculation_thread(struct event *t)
718e3744 593{
d62a17ae 594 struct ospf6_area *oa;
595 struct ospf6 *ospf6;
596 struct timeval start, end, runtime;
597 struct listnode *node;
598 int areas_processed = 0;
599 char rbuf[32];
600
e16d030c 601 ospf6 = (struct ospf6 *)EVENT_ARG(t);
d62a17ae 602
603 /* execute SPF calculation */
604 monotime(&start);
ab0f1135 605 ospf6->ts_spf = start;
d62a17ae 606
95b3f03d 607 if (ospf6_check_and_set_router_abr(ospf6))
d62a17ae 608 ospf6_abr_range_reset_cost(ospf6);
609
610 for (ALL_LIST_ELEMENTS_RO(ospf6->area_list, node, oa)) {
611
612 if (oa == ospf6->backbone)
613 continue;
614
ab0f1135 615 monotime(&oa->ts_spf);
d62a17ae 616 if (IS_OSPF6_DEBUG_SPF(PROCESS))
617 zlog_debug("SPF calculation for Area %s", oa->name);
618 if (IS_OSPF6_DEBUG_SPF(DATABASE))
619 ospf6_spf_log_database(oa);
620
621 ospf6_spf_calculation(ospf6->router_id, oa->spf_table, oa);
622 ospf6_intra_route_calculation(oa);
623 ospf6_intra_brouter_calculation(oa);
624
625 areas_processed++;
626 }
627
628 if (ospf6->backbone) {
ab0f1135 629 monotime(&ospf6->backbone->ts_spf);
d62a17ae 630 if (IS_OSPF6_DEBUG_SPF(PROCESS))
631 zlog_debug("SPF calculation for Backbone area %s",
632 ospf6->backbone->name);
633 if (IS_OSPF6_DEBUG_SPF(DATABASE))
634 ospf6_spf_log_database(ospf6->backbone);
635
636 ospf6_spf_calculation(ospf6->router_id,
637 ospf6->backbone->spf_table,
638 ospf6->backbone);
639 ospf6_intra_route_calculation(ospf6->backbone);
640 ospf6_intra_brouter_calculation(ospf6->backbone);
641 areas_processed++;
642 }
643
ad500b22
K		 644 /* External LSA calculation */
645 ospf6_ase_calculate_timer_add(ospf6);
646
6735622c 647 if (ospf6_check_and_set_router_abr(ospf6)) {
d62a17ae 648 ospf6_abr_defaults_to_stub(ospf6);
6735622c
RW		 649 ospf6_abr_nssa_type_7_defaults(ospf6);
650 }
d62a17ae 651
652 monotime(&end);
653 timersub(&end, &start, &runtime);
654
655 ospf6->ts_spf_duration = runtime;
656
657 ospf6_spf_reason_string(ospf6->spf_reason, rbuf, sizeof(rbuf));
658
659 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
1bc19a9e
DS		 660 zlog_debug(
661 "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, Reason: %s",
662 areas_processed, (long long)runtime.tv_sec,
663 (long long)runtime.tv_usec, rbuf);
ab0f1135 664
d62a17ae 665 ospf6->last_spf_reason = ospf6->spf_reason;
666 ospf6_reset_spf_reason(ospf6);
718e3744 667}
668
3810e06e
DD		 669/* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
670 set timer for SPF calc. */
d62a17ae 671void ospf6_spf_schedule(struct ospf6 *ospf6, unsigned int reason)
718e3744 672{
d62a17ae 673 unsigned long delay, elapsed, ht;
674
cac84a16 675 /* OSPF instance does not exist. */
676 if (ospf6 == NULL)
677 return;
678
d62a17ae 679 ospf6_set_spf_reason(ospf6, reason);
680
681 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) {
682 char rbuf[32];
683 ospf6_spf_reason_string(reason, rbuf, sizeof(rbuf));
684 zlog_debug("SPF: calculation timer scheduled (reason %s)",
685 rbuf);
686 }
687
d62a17ae 688 /* SPF calculation timer is already scheduled. */
5f6eaa9b 689 if (event_is_scheduled(ospf6->t_spf_calc)) {
d62a17ae 690 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
691 zlog_debug(
692 "SPF: calculation timer is already scheduled: %p",
693 (void *)ospf6->t_spf_calc);
694 return;
695 }
696
697 elapsed = monotime_since(&ospf6->ts_spf, NULL) / 1000LL;
698 ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier;
699
700 if (ht > ospf6->spf_max_holdtime)
701 ht = ospf6->spf_max_holdtime;
702
703 /* Get SPF calculation delay time. */
704 if (elapsed < ht) {
705 /* Got an event within the hold time of last SPF. We need to
706 * increase the hold_multiplier, if it's not already at/past
707 * maximum value, and wasn't already increased..
708 */
709 if (ht < ospf6->spf_max_holdtime)
710 ospf6->spf_hold_multiplier++;
711
712 /* always honour the SPF initial delay */
713 if ((ht - elapsed) < ospf6->spf_delay)
714 delay = ospf6->spf_delay;
715 else
716 delay = ht - elapsed;
717 } else {
718 /* Event is past required hold-time of last SPF */
719 delay = ospf6->spf_delay;
720 ospf6->spf_hold_multiplier = 1;
721 }
722
723 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
1bc19a9e 724 zlog_debug("SPF: Rescheduling in %ld msec", delay);
d62a17ae 725
e16d030c 726 EVENT_OFF(ospf6->t_spf_calc);
907a2395
DS		 727 event_add_timer_msec(master, ospf6_spf_calculation_thread, ospf6, delay,
728 &ospf6->t_spf_calc);
718e3744 729}
730
d62a17ae 731void ospf6_spf_display_subtree(struct vty *vty, const char *prefix, int rest,
305b639b
YR		 732 struct ospf6_vertex *v, json_object *json_obj,
733 bool use_json)
718e3744 734{
d62a17ae 735 struct listnode *node, *nnode;
736 struct ospf6_vertex *c;
737 char *next_prefix;
738 int len;
739 int restnum;
305b639b
YR		 740 json_object *json_childs = NULL;
741 json_object *json_child = NULL;
d62a17ae 742
305b639b
YR		 743 if (use_json) {
744 json_childs = json_object_new_object();
745 json_object_int_add(json_obj, "cost", v->cost);
746 } else {
747 /* "prefix" is the space prefix of the display line */
748 vty_out(vty, "%s+-%s [%d]\n", prefix, v->name, v->cost);
749 }
d62a17ae 750
751 len = strlen(prefix) + 4;
752 next_prefix = (char *)malloc(len);
753 if (next_prefix == NULL) {
754 vty_out(vty, "malloc failed\n");
755 return;
756 }
757 snprintf(next_prefix, len, "%s%s", prefix, (rest ? "| " : " "));
758
759 restnum = listcount(v->child_list);
760 for (ALL_LIST_ELEMENTS(v->child_list, node, nnode, c)) {
305b639b
YR		 761 if (use_json)
762 json_child = json_object_new_object();
763 else
764 restnum--;
d62a17ae 765
305b639b
YR		 766 ospf6_spf_display_subtree(vty, next_prefix, restnum, c,
767 json_child, use_json);
768
769 if (use_json)
770 json_object_object_add(json_childs, c->name,
771 json_child);
772 }
773 if (use_json) {
774 json_object_boolean_add(json_obj, "isLeafNode",
775 !listcount(v->child_list));
776 if (listcount(v->child_list))
777 json_object_object_add(json_obj, "children",
778 json_childs);
779 else
780 json_object_free(json_childs);
781 }
d62a17ae 782 free(next_prefix);
718e3744 783}
784
3b68735f 785DEFUN (debug_ospf6_spf_process,
786 debug_ospf6_spf_process_cmd,
787 "debug ospf6 spf process",
508e53e2 788 DEBUG_STR
789 OSPF6_STR
790 "Debug SPF Calculation\n"
3b68735f 791 "Debug Detailed SPF Process\n"
508e53e2 792 )
718e3744 793{
d62a17ae 794 unsigned char level = 0;
795 level = OSPF6_DEBUG_SPF_PROCESS;
796 OSPF6_DEBUG_SPF_ON(level);
797 return CMD_SUCCESS;
718e3744 798}
799
3b68735f 800DEFUN (debug_ospf6_spf_time,
801 debug_ospf6_spf_time_cmd,
802 "debug ospf6 spf time",
508e53e2 803 DEBUG_STR
718e3744 804 OSPF6_STR
508e53e2 805 "Debug SPF Calculation\n"
3b68735f 806 "Measure time taken by SPF Calculation\n"
508e53e2 807 )
718e3744 808{
d62a17ae 809 unsigned char level = 0;
810 level = OSPF6_DEBUG_SPF_TIME;
811 OSPF6_DEBUG_SPF_ON(level);
812 return CMD_SUCCESS;
718e3744 813}
814
2680aa2b 815DEFUN (debug_ospf6_spf_database,
816 debug_ospf6_spf_database_cmd,
817 "debug ospf6 spf database",
818 DEBUG_STR
819 OSPF6_STR
820 "Debug SPF Calculation\n"
821 "Log number of LSAs at SPF Calculation time\n"
822 )
823{
d62a17ae 824 unsigned char level = 0;
825 level = OSPF6_DEBUG_SPF_DATABASE;
826 OSPF6_DEBUG_SPF_ON(level);
827 return CMD_SUCCESS;
2680aa2b 828}
829
3b68735f 830DEFUN (no_debug_ospf6_spf_process,
831 no_debug_ospf6_spf_process_cmd,
832 "no debug ospf6 spf process",
508e53e2 833 NO_STR
834 DEBUG_STR
835 OSPF6_STR
836 "Quit Debugging SPF Calculation\n"
3b68735f 837 "Quit Debugging Detailed SPF Process\n"
508e53e2 838 )
718e3744 839{
d62a17ae 840 unsigned char level = 0;
841 level = OSPF6_DEBUG_SPF_PROCESS;
842 OSPF6_DEBUG_SPF_OFF(level);
843 return CMD_SUCCESS;
718e3744 844}
845
3b68735f 846DEFUN (no_debug_ospf6_spf_time,
847 no_debug_ospf6_spf_time_cmd,
848 "no debug ospf6 spf time",
508e53e2 849 NO_STR
850 DEBUG_STR
718e3744 851 OSPF6_STR
508e53e2 852 "Quit Debugging SPF Calculation\n"
3b68735f 853 "Quit Measuring time taken by SPF Calculation\n"
508e53e2 854 )
718e3744 855{
d62a17ae 856 unsigned char level = 0;
857 level = OSPF6_DEBUG_SPF_TIME;
858 OSPF6_DEBUG_SPF_OFF(level);
859 return CMD_SUCCESS;
718e3744 860}
861
2680aa2b 862DEFUN (no_debug_ospf6_spf_database,
863 no_debug_ospf6_spf_database_cmd,
864 "no debug ospf6 spf database",
865 NO_STR
866 DEBUG_STR
867 OSPF6_STR
868 "Debug SPF Calculation\n"
869 "Quit Logging number of LSAs at SPF Calculation time\n"
870 )
871{
d62a17ae 872 unsigned char level = 0;
873 level = OSPF6_DEBUG_SPF_DATABASE;
874 OSPF6_DEBUG_SPF_OFF(level);
875 return CMD_SUCCESS;
2680aa2b 876}
877
d62a17ae 878static int ospf6_timers_spf_set(struct vty *vty, unsigned int delay,
879 unsigned int hold, unsigned int max)
3810e06e 880{
d62a17ae 881 VTY_DECLVAR_CONTEXT(ospf6, ospf);
3810e06e 882
d62a17ae 883 ospf->spf_delay = delay;
884 ospf->spf_holdtime = hold;
885 ospf->spf_max_holdtime = max;
3810e06e 886
d62a17ae 887 return CMD_SUCCESS;
3810e06e
DD		 888}
889
890DEFUN (ospf6_timers_throttle_spf,
891 ospf6_timers_throttle_spf_cmd,
6147e2c6 892 "timers throttle spf (0-600000) (0-600000) (0-600000)",
3810e06e
DD		 893 "Adjust routing timers\n"
894 "Throttling adaptive timer\n"
895 "OSPF6 SPF timers\n"
896 "Delay (msec) from first change received till SPF calculation\n"
897 "Initial hold time (msec) between consecutive SPF calculations\n"
898 "Maximum hold time (msec)\n")
899{
d62a17ae 900 int idx_number = 3;
901 int idx_number_2 = 4;
902 int idx_number_3 = 5;
903 unsigned int delay, hold, max;
3810e06e 904
d62a17ae 905 delay = strtoul(argv[idx_number]->arg, NULL, 10);
906 hold = strtoul(argv[idx_number_2]->arg, NULL, 10);
907 max = strtoul(argv[idx_number_3]->arg, NULL, 10);
3810e06e 908
d62a17ae 909 return ospf6_timers_spf_set(vty, delay, hold, max);
3810e06e
DD		 910}
911
912DEFUN (no_ospf6_timers_throttle_spf,
913 no_ospf6_timers_throttle_spf_cmd,
1d68dbfe 914 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
3810e06e
DD		 915 NO_STR
916 "Adjust routing timers\n"
917 "Throttling adaptive timer\n"
1d68dbfe
DW		 918 "OSPF6 SPF timers\n"
919 "Delay (msec) from first change received till SPF calculation\n"
920 "Initial hold time (msec) between consecutive SPF calculations\n"
921 "Maximum hold time (msec)\n")
3810e06e 922{
d62a17ae 923 return ospf6_timers_spf_set(vty, OSPF_SPF_DELAY_DEFAULT,
924 OSPF_SPF_HOLDTIME_DEFAULT,
925 OSPF_SPF_MAX_HOLDTIME_DEFAULT);
3810e06e
DD		 926}
927
813d4307 928
d62a17ae 929int config_write_ospf6_debug_spf(struct vty *vty)
718e3744 930{
d62a17ae 931 if (IS_OSPF6_DEBUG_SPF(PROCESS))
932 vty_out(vty, "debug ospf6 spf process\n");
933 if (IS_OSPF6_DEBUG_SPF(TIME))
934 vty_out(vty, "debug ospf6 spf time\n");
935 if (IS_OSPF6_DEBUG_SPF(DATABASE))
936 vty_out(vty, "debug ospf6 spf database\n");
937 return 0;
718e3744 938}
939
beadc736 940void ospf6_spf_config_write(struct vty *vty, struct ospf6 *ospf6)
3810e06e
DD		 941{
942
d62a17ae 943 if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT
944 || ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT
945 || ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT)
946 vty_out(vty, " timers throttle spf %d %d %d\n",
947 ospf6->spf_delay, ospf6->spf_holdtime,
948 ospf6->spf_max_holdtime);
3810e06e
DD		 949}
950
d62a17ae 951void install_element_ospf6_debug_spf(void)
508e53e2 952{
d62a17ae 953 install_element(ENABLE_NODE, &debug_ospf6_spf_process_cmd);
954 install_element(ENABLE_NODE, &debug_ospf6_spf_time_cmd);
955 install_element(ENABLE_NODE, &debug_ospf6_spf_database_cmd);
956 install_element(ENABLE_NODE, &no_debug_ospf6_spf_process_cmd);
957 install_element(ENABLE_NODE, &no_debug_ospf6_spf_time_cmd);
958 install_element(ENABLE_NODE, &no_debug_ospf6_spf_database_cmd);
959 install_element(CONFIG_NODE, &debug_ospf6_spf_process_cmd);
960 install_element(CONFIG_NODE, &debug_ospf6_spf_time_cmd);
961 install_element(CONFIG_NODE, &debug_ospf6_spf_database_cmd);
962 install_element(CONFIG_NODE, &no_debug_ospf6_spf_process_cmd);
963 install_element(CONFIG_NODE, &no_debug_ospf6_spf_time_cmd);
964 install_element(CONFIG_NODE, &no_debug_ospf6_spf_database_cmd);
508e53e2 965}
718e3744 966
d62a17ae 967void ospf6_spf_init(void)
718e3744 968{
d62a17ae 969 install_element(OSPF6_NODE, &ospf6_timers_throttle_spf_cmd);
970 install_element(OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd);
718e3744 971}
da086a3b
CS		 972
973/* Create Aggregated Large Router-LSA from multiple Link-State IDs
974 * RFC 5340 A 4.3:
975 * When more than one router-LSA is received from a single router,
976 * the links are processed as if concatenated into a single LSA.*/
977struct ospf6_lsa *ospf6_create_single_router_lsa(struct ospf6_area *area,
978 struct ospf6_lsdb *lsdb,
979 uint32_t adv_router)
980{
981 struct ospf6_lsa *lsa = NULL;
982 struct ospf6_lsa *rtr_lsa = NULL;
983 struct ospf6_lsa_header *lsa_header = NULL;
984 uint8_t *new_header = NULL;
985 const struct route_node *end = NULL;
986 uint16_t lsa_length, total_lsa_length = 0, num_lsa = 0;
d7c0a89a 987 uint16_t type = 0;
da086a3b
CS		 988 char ifbuf[16];
989 uint32_t interface_id;
990 caddr_t lsd;
991
996c9314
LB		 992 lsa_length = sizeof(struct ospf6_lsa_header)
993 + sizeof(struct ospf6_router_lsa);
da086a3b
CS		 994 total_lsa_length = lsa_length;
995 type = htons(OSPF6_LSTYPE_ROUTER);
996
997 /* First check Aggregated LSA formed earlier in Cache */
998 lsa = ospf6_lsdb_lookup(type, htonl(0), adv_router,
999 area->temp_router_lsa_lsdb);
1000 if (lsa)
1001 return lsa;
1002
1003 inet_ntop(AF_INET, &adv_router, ifbuf, sizeof(ifbuf));
1004
1005 /* Determine total LSA length from all link state ids */
1006 end = ospf6_lsdb_head(lsdb, 2, type, adv_router, &rtr_lsa);
1007 while (rtr_lsa) {
1008 lsa = rtr_lsa;
1009 if (OSPF6_LSA_IS_MAXAGE(rtr_lsa)) {
1010 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1011 continue;
1012 }
c4efd0f4 1013 lsa_header = rtr_lsa->header;
996c9314 1014 total_lsa_length += (ntohs(lsa_header->length) - lsa_length);
da086a3b
CS		 1015 num_lsa++;
1016 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1017 }
1018 if (IS_OSPF6_DEBUG_SPF(PROCESS))
15569c58
DA		 1019 zlog_debug("%s: adv_router %s num_lsa %u to convert.", __func__,
1020 ifbuf, num_lsa);
da086a3b
CS		 1021 if (num_lsa == 1)
1022 return lsa;
1023
1024 if (num_lsa == 0) {
1025 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1026 zlog_debug("%s: adv_router %s not found in LSDB.",
15569c58 1027 __func__, ifbuf);
da086a3b
CS		 1028 return NULL;
1029 }
1030
771e1fbe
DL		 1031 lsa = ospf6_lsa_alloc(total_lsa_length);
1032 new_header = (uint8_t *)lsa->header;
da086a3b
CS		 1033
1034 lsa->lsdb = area->temp_router_lsa_lsdb;
1035
1036 /* Fill Larger LSA Payload */
1037 end = ospf6_lsdb_head(lsdb, 2, type, adv_router, &rtr_lsa);
cf29dab3
DS		 1038
1039 /*
1040 * We assume at this point in time that rtr_lsa is
1041 * a valid pointer.
1042 */
1043 assert(rtr_lsa);
1044 if (!OSPF6_LSA_IS_MAXAGE(rtr_lsa)) {
1045 /* Append first Link State ID LSA */
c4efd0f4 1046 lsa_header = rtr_lsa->header;
cf29dab3
DS		 1047 memcpy(new_header, lsa_header, ntohs(lsa_header->length));
1048 /* Assign new lsa length as aggregated length. */
1049 ((struct ospf6_lsa_header *)new_header)->length =
1050 htons(total_lsa_length);
1051 new_header += ntohs(lsa_header->length);
1052 num_lsa--;
da086a3b
CS		 1053 }
1054
1055 /* Print LSA Name */
1056 ospf6_lsa_printbuf(lsa, lsa->name, sizeof(lsa->name));
1057
1058 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1059 while (rtr_lsa) {
1060 if (OSPF6_LSA_IS_MAXAGE(rtr_lsa)) {
1061 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1062 continue;
1063 }
1064
1065 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
1066 lsd = OSPF6_LSA_HEADER_END(rtr_lsa->header) + 4;
1067 interface_id = ROUTER_LSDESC_GET_IFID(lsd);
1068 inet_ntop(AF_INET, &interface_id, ifbuf, sizeof(ifbuf));
996c9314
LB		 1069 zlog_debug(
1070 "%s: Next Router LSA %s to aggreat with len %u interface_id %s",
15569c58 1071 __func__, rtr_lsa->name,
996c9314 1072 ntohs(lsa_header->length), ifbuf);
da086a3b
CS		 1073 }
1074
1075 /* Append Next Link State ID LSA */
c4efd0f4 1076 lsa_header = rtr_lsa->header;
da086a3b
CS		 1077 memcpy(new_header, (OSPF6_LSA_HEADER_END(rtr_lsa->header) + 4),
1078 (ntohs(lsa_header->length) - lsa_length));
1079 new_header += (ntohs(lsa_header->length) - lsa_length);
1080 num_lsa--;
1081
1082 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1083 }
1084
1085 /* Calculate birth of this lsa */
1086 ospf6_lsa_age_set(lsa);
1087
1088 /* Store Aggregated LSA into area temp lsdb */
1089 ospf6_lsdb_add(lsa, area->temp_router_lsa_lsdb);
1090
1091 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1092 zlog_debug("%s: LSA %s id %u type 0%x len %u num_lsa %u",
15569c58
DA		 1093 __func__, lsa->name, ntohl(lsa->header->id),
1094 ntohs(lsa->header->type), ntohs(lsa->header->length),
1095 num_lsa);
da086a3b
CS		 1096
1097 return lsa;
1098}
1099
1100void ospf6_remove_temp_router_lsa(struct ospf6_area *area)
1101{
2e37407f 1102 struct ospf6_lsa *lsa = NULL, *lsanext;
da086a3b 1103
2e37407f 1104 for (ALL_LSDB(area->temp_router_lsa_lsdb, lsa, lsanext)) {
da086a3b 1105 if (IS_OSPF6_DEBUG_SPF(PROCESS))
996c9314
LB		 1106 zlog_debug(
1107 "%s Remove LSA %s lsa->lock %u lsdb count %u",
5e81f5dd 1108 __func__, lsa->name, lsa->lock,
996c9314 1109 area->temp_router_lsa_lsdb->count);
da086a3b
CS		 1110 ospf6_lsdb_remove(lsa, area->temp_router_lsa_lsdb);
1111 }
1112}
ad500b22
K		 1113
1114int ospf6_ase_calculate_route(struct ospf6 *ospf6, struct ospf6_lsa *lsa,
1115 struct ospf6_area *area)
1116{
35769de4 1117 struct ospf6_route *route;
ad500b22
K		 1118 struct ospf6_as_external_lsa *external;
1119 struct prefix prefix;
1120 void (*hook_add)(struct ospf6_route *) = NULL;
1121 void (*hook_remove)(struct ospf6_route *) = NULL;
1122
1123 assert(lsa);
1124
1125 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1126 zlog_debug("%s : start", __func__);
1127
1128 if (ntohs(lsa->header->type) == OSPF6_LSTYPE_TYPE_7)
1129 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1130 zlog_debug("%s: Processing Type-7", __func__);
1131
1132 /* Stay away from any Local Translated Type-7 LSAs */
1133 if (CHECK_FLAG(lsa->flag, OSPF6_LSA_LOCAL_XLT)) {
1134 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1135 zlog_debug("%s: Rejecting Local translated LSA",
1136 __func__);
1137 return 0;
1138 }
1139
1140 external = (struct ospf6_as_external_lsa *)OSPF6_LSA_HEADER_END(
1141 lsa->header);
1142 prefix.family = AF_INET6;
1143 prefix.prefixlen = external->prefix.prefix_length;
1144 ospf6_prefix_in6_addr(&prefix.u.prefix6, external, &external->prefix);
1145
1146 if (ntohs(lsa->header->type) == OSPF6_LSTYPE_AS_EXTERNAL) {
1147 hook_add = ospf6->route_table->hook_add;
1148 hook_remove = ospf6->route_table->hook_remove;
1149 ospf6->route_table->hook_add = NULL;
1150 ospf6->route_table->hook_remove = NULL;
1151
ad500b22
K		 1152 if (!OSPF6_LSA_IS_MAXAGE(lsa))
1153 ospf6_asbr_lsa_add(lsa);
1154
1155 ospf6->route_table->hook_add = hook_add;
1156 ospf6->route_table->hook_remove = hook_remove;
1157
1158 route = ospf6_route_lookup(&prefix, ospf6->route_table);
1159 if (route == NULL) {
1160 if (IS_OSPF6_DEBUG_SPF(PROCESS))
35769de4 1161 zlog_debug("%s: no external route %pFX",
ad500b22
K		 1162 __func__, &prefix);
1163 return 0;
1164 }
1165
1166 if (CHECK_FLAG(route->flag, OSPF6_ROUTE_REMOVE)
35769de4 1167 && CHECK_FLAG(route->flag, OSPF6_ROUTE_ADD)) {
ad500b22
K		 1168 UNSET_FLAG(route->flag, OSPF6_ROUTE_REMOVE);
1169 UNSET_FLAG(route->flag, OSPF6_ROUTE_ADD);
1170 }
1171
1172 if (CHECK_FLAG(route->flag, OSPF6_ROUTE_REMOVE))
1173 ospf6_route_remove(route, ospf6->route_table);
1174 else if (CHECK_FLAG(route->flag, OSPF6_ROUTE_ADD)
1175 || CHECK_FLAG(route->flag, OSPF6_ROUTE_CHANGE)) {
1176 if (hook_add) {
1177 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1178 zlog_debug(
1179 "%s: add external route %pFX",
1180 __func__, &prefix);
1181 (*hook_add)(route);
1182 }
ad500b22
K		 1183 }
1184 } else if (ntohs(lsa->header->type) == OSPF6_LSTYPE_TYPE_7) {
1185 hook_add = area->route_table->hook_add;
1186 hook_remove = area->route_table->hook_remove;
1187 area->route_table->hook_add = NULL;
1188 area->route_table->hook_remove = NULL;
1189
ad500b22
K		 1190 if (!OSPF6_LSA_IS_MAXAGE(lsa))
1191 ospf6_asbr_lsa_add(lsa);
1192
1193 area->route_table->hook_add = hook_add;
1194 area->route_table->hook_remove = hook_remove;
1195
1196 route = ospf6_route_lookup(&prefix, area->route_table);
1197 if (route == NULL) {
1198 if (IS_OSPF6_DEBUG_SPF(PROCESS))
35769de4 1199 zlog_debug("%s: no route %pFX, area %s",
ad500b22
K		 1200 __func__, &prefix, area->name);
1201 return 0;
1202 }
1203
1204 if (CHECK_FLAG(route->flag, OSPF6_ROUTE_REMOVE)
35769de4 1205 && CHECK_FLAG(route->flag, OSPF6_ROUTE_ADD)) {
ad500b22
K		 1206 UNSET_FLAG(route->flag, OSPF6_ROUTE_REMOVE);
1207 UNSET_FLAG(route->flag, OSPF6_ROUTE_ADD);
1208 }
1209
1210 if (CHECK_FLAG(route->flag, OSPF6_ROUTE_REMOVE)) {
1211 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1212 zlog_debug("%s : remove route %pFX, area %s",
1213 __func__, &prefix, area->name);
1214 ospf6_route_remove(route, area->route_table);
1215 } else if (CHECK_FLAG(route->flag, OSPF6_ROUTE_ADD)
1216 || CHECK_FLAG(route->flag, OSPF6_ROUTE_CHANGE)) {
1217 if (hook_add) {
1218 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1219 zlog_debug(
1220 "%s: add nssa route %pFX, area %s",
1221 __func__, &prefix, area->name);
1222 (*hook_add)(route);
1223 }
1224 ospf6_abr_check_translate_nssa(area, lsa);
ad500b22
K		 1225 }
1226 }
1227 return 0;
1228}
1229
e6685141 1230static void ospf6_ase_calculate_timer(struct event *t)
ad500b22
K		 1231{
1232 struct ospf6 *ospf6;
1233 struct ospf6_lsa *lsa;
1234 struct listnode *node, *nnode;
1235 struct ospf6_area *area;
1236 uint16_t type;
1237
e16d030c 1238 ospf6 = EVENT_ARG(t);
ad500b22
K		 1239
1240 /* Calculate external route for each AS-external-LSA */
1241 type = htons(OSPF6_LSTYPE_AS_EXTERNAL);
1242 for (ALL_LSDB_TYPED(ospf6->lsdb, type, lsa))
1243 ospf6_ase_calculate_route(ospf6, lsa, NULL);
1244
1245 /* This version simple adds to the table all NSSA areas */
1246 if (ospf6->anyNSSA) {
1247 for (ALL_LIST_ELEMENTS(ospf6->area_list, node, nnode, area)) {
1248 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1249 zlog_debug("%s : looking at area %s", __func__,
1250 area->name);
1251
6df89791
RW		 1252 type = htons(OSPF6_LSTYPE_TYPE_7);
1253 for (ALL_LSDB_TYPED(area->lsdb, type, lsa))
1254 ospf6_ase_calculate_route(ospf6, lsa, area);
ad500b22
K		 1255 }
1256 }
71165098
RW		 1257
1258 if (ospf6->gr_info.finishing_restart) {
1259 /*
1260 * The routing table computation is complete. Uninstall remnant
1261 * routes that were installed before the restart, but that are
1262 * no longer valid.
1263 */
1264 ospf6_zebra_gr_disable(ospf6);
1265 ospf6->gr_info.finishing_restart = false;
1266 }
ad500b22
K		 1267}
1268
1269void ospf6_ase_calculate_timer_add(struct ospf6 *ospf6)
1270{
1271 if (ospf6 == NULL)
1272 return;
1273
907a2395
DS		 1274 event_add_timer(master, ospf6_ase_calculate_timer, ospf6,
1275 OSPF6_ASE_CALC_INTERVAL, &ospf6->t_ase_calc);
ad500b22 1276}
637e6f29 1277
1278bool ospf6_merge_parents_nh_to_child(struct ospf6_vertex *v,
1279 struct ospf6_route *route,
1280 struct ospf6_route_table *result_table)
1281{
1282 struct ospf6_route *parent_route;
1283
1284 if (v->parent && v->parent->hops) {
1285 parent_route =
1286 ospf6_route_lookup(&v->parent->vertex_id, result_table);
1287 if (parent_route) {
1288 ospf6_route_merge_nexthops(route, parent_route);
1289 return true;
1290 }
1291 }
1292 return false;
1293}
FRRouting mirror