]> 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 #12798 from donaldsharp/rib_match_multicast
[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"
16#include "thread.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{
d62a17ae 313 struct ospf6_route *route, *parent_route;
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);
d62a17ae 333 ospf6_spf_merge_nexthops_to_route(route, v);
334
335 prev = (struct ospf6_vertex *)route->route_option;
336 assert(prev->hops <= v->hops);
d62a17ae 337
996c9314
LB		 338 if ((VERTEX_IS_TYPE(ROUTER, v)
339 && route->path.origin.id != v->lsa->header->id)) {
26e14616 340 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
996c9314
LB		 341 zlog_debug(
342 "%s: V lsa %s id %u, route id %u are different",
15569c58 343 __func__, v->lsa->name,
996c9314
LB		 344 ntohl(v->lsa->header->id),
345 ntohl(route->path.origin.id));
26e14616
CS		 346 }
347 return 0;
348 }
349
350 ospf6_vertex_delete(v);
d62a17ae 351 return -1;
c3c0ac83 352 }
508e53e2 353
d62a17ae 354 /* There should be no case where candidate being installed (variable
355 "v") is closer than the one in the SPF tree (variable "route").
356 In the case something has gone wrong with the behavior of
357 Priority-Queue. */
358
359 /* the case where the route exists already is handled and returned
360 up to here. */
361 assert(route == NULL);
362
22813fdb 363 route = ospf6_route_create(v->area->ospf6);
d62a17ae 364 memcpy(&route->prefix, &v->vertex_id, sizeof(struct prefix));
365 route->type = OSPF6_DEST_TYPE_LINKSTATE;
366 route->path.type = OSPF6_PATH_TYPE_INTRA;
367 route->path.origin.type = v->lsa->header->type;
368 route->path.origin.id = v->lsa->header->id;
369 route->path.origin.adv_router = v->lsa->header->adv_router;
370 route->path.metric_type = 1;
371 route->path.cost = v->cost;
372 route->path.u.cost_e2 = v->hops;
373 route->path.router_bits = v->capability;
374 route->path.options[0] = v->options[0];
375 route->path.options[1] = v->options[1];
376 route->path.options[2] = v->options[2];
377
378 ospf6_spf_copy_nexthops_to_route(route, v);
379
380 /*
381 * The SPF logic implementation does not transfer the multipathing
382 * properties
383 * of a parent to a child node. Thus if there was a 3-way multipath to a
384 * node's parent and a single hop from the parent to the child, the
385 * logic of
386 * creating new vertices and computing next hops prevents there from
387 * being 3
388 * paths to the child node. This is primarily because the resolution of
389 * multipath is done in this routine, not in the main spf loop.
390 *
391 * The following logic addresses that problem by merging the parent's
392 * nexthop
393 * information with the child's, if the parent is not the root of the
394 * tree.
395 * This is based on the assumption that before a node's route is
396 * installed,
397 * its parent's route's nexthops have already been installed.
398 */
399 if (v->parent && v->parent->hops) {
400 parent_route =
401 ospf6_route_lookup(&v->parent->vertex_id, result_table);
402 if (parent_route) {
403 ospf6_route_merge_nexthops(route, parent_route);
404 }
405 }
406
407 if (v->parent)
408 listnode_add_sort(v->parent->child_list, v);
409 route->route_option = v;
508e53e2 410
e285b70d 411 ospf6_route_add(route, result_table);
d62a17ae 412 return 0;
718e3744 413}
414
e285b70d 415void ospf6_spf_table_finish(struct ospf6_route_table *result_table)
718e3744 416{
d62a17ae 417 struct ospf6_route *route, *nroute;
418 struct ospf6_vertex *v;
419 for (route = ospf6_route_head(result_table); route; route = nroute) {
420 nroute = ospf6_route_next(route);
421 v = (struct ospf6_vertex *)route->route_option;
422 ospf6_vertex_delete(v);
e285b70d 423 ospf6_route_remove(route, result_table);
d62a17ae 424 }
718e3744 425}
426
71165098 427static const char *const ospf6_spf_reason_str[] = {
d0606e0a
DS		 428 "R+", /* OSPF6_SPF_FLAGS_ROUTER_LSA_ADDED */
429 "R-", /* OSPF6_SPF_FLAGS_ROUTER_LSA_REMOVED */
430 "N+", /* OSPF6_SPF_FLAGS_NETWORK_LSA_ADDED */
431 "N-", /* OSPF6_SPF_FLAGS_NETWORK_LSA_REMOVED */
432 "L+", /* OSPF6_SPF_FLAGS_NETWORK_LINK_LSA_ADDED */
433 "L-", /* OSPF6_SPF_FLAGS_NETWORK_LINK_LSA_REMOVED */
434 "R*", /* OSPF6_SPF_FLAGS_ROUTER_LSA_ORIGINATED */
435 "N*", /* OSPF6_SPF_FLAGS_NETWORK_LSA_ORIGINATED */
436 "C", /* OSPF6_SPF_FLAGS_CONFIG_CHANGE */
437 "A", /* OSPF6_SPF_FLAGS_ASBR_STATUS_CHANGE */
438 "GR", /* OSPF6_SPF_FLAGS_GR_FINISH */
439};
440
441void ospf6_spf_reason_string(uint32_t reason, char *buf, int size)
a0edf674 442{
d0606e0a 443 uint32_t bit;
d62a17ae 444 int len = 0;
445
446 if (!buf)
447 return;
448
f13d33cc
PG		 449 if (!reason) {
450 buf[0] = '\0';
451 return;
452 }
d62a17ae 453 for (bit = 0; bit < array_size(ospf6_spf_reason_str); bit++) {
454 if ((reason & (1 << bit)) && (len < size)) {
455 len += snprintf((buf + len), (size - len), "%s%s",
456 (len > 0) ? ", " : "",
457 ospf6_spf_reason_str[bit]);
458 }
a0edf674 459 }
a0edf674
DD		 460}
461
6452df09 462/* RFC2328 16.1. Calculating the shortest-path tree for an area */
463/* RFC2740 3.8.1. Calculating the shortest path tree for an area */
d7c0a89a 464void ospf6_spf_calculation(uint32_t router_id,
d62a17ae 465 struct ospf6_route_table *result_table,
466 struct ospf6_area *oa)
508e53e2 467{
4ab0496e 468 struct vertex_pqueue_head candidate_list;
d62a17ae 469 struct ospf6_vertex *root, *v, *w;
470 int size;
471 caddr_t lsdesc;
da086a3b 472 struct ospf6_lsa *lsa;
d62a17ae 473 struct in6_addr address;
474
e285b70d 475 ospf6_spf_table_finish(result_table);
d62a17ae 476
477 /* Install the calculating router itself as the root of the SPF tree */
478 /* construct root vertex */
da086a3b 479 lsa = ospf6_create_single_router_lsa(oa, oa->lsdb_self, router_id);
d62a17ae 480 if (lsa == NULL) {
1b1f7b4f 481 zlog_warn("%s: No router LSA for area %s", __func__, oa->name);
d62a17ae 482 return;
483 }
484
485 /* initialize */
4ab0496e 486 vertex_pqueue_init(&candidate_list);
d62a17ae 487
488 root = ospf6_vertex_create(lsa);
489 root->area = oa;
490 root->cost = 0;
491 root->hops = 0;
26e14616 492 root->link_id = lsa->header->id;
d62a17ae 493 inet_pton(AF_INET6, "::1", &address);
494
495 /* Actually insert root to the candidate-list as the only candidate */
4ab0496e 496 vertex_pqueue_add(&candidate_list, root);
d62a17ae 497
498 /* Iterate until candidate-list becomes empty */
4ab0496e 499 while ((v = vertex_pqueue_pop(&candidate_list))) {
d62a17ae 500 /* installing may result in merging or rejecting of the vertex
501 */
e285b70d 502 if (ospf6_spf_install(v, result_table) < 0)
d62a17ae 503 continue;
504
505 /* Skip overloaded routers */
506 if ((OSPF6_LSA_IS_TYPE(ROUTER, v->lsa)
507 && ospf6_router_is_stub_router(v->lsa)))
508 continue;
509
da086a3b
CS		 510 /* For each LS description in the just-added vertex V's LSA */
511 size = (VERTEX_IS_TYPE(ROUTER, v)
512 ? sizeof(struct ospf6_router_lsdesc)
513 : sizeof(struct ospf6_network_lsdesc));
514 for (lsdesc = OSPF6_LSA_HEADER_END(v->lsa->header) + 4;
515 lsdesc + size <= OSPF6_LSA_END(v->lsa->header);
516 lsdesc += size) {
517 lsa = ospf6_lsdesc_lsa(lsdesc, v);
518 if (lsa == NULL)
519 continue;
520
521 if (OSPF6_LSA_IS_MAXAGE(lsa))
522 continue;
523
524 if (!ospf6_lsdesc_backlink(lsa, lsdesc, v))
525 continue;
526
527 w = ospf6_vertex_create(lsa);
528 w->area = oa;
529 w->parent = v;
530 if (VERTEX_IS_TYPE(ROUTER, v)) {
531 w->cost = v->cost
26e14616 532 + ROUTER_LSDESC_GET_METRIC(lsdesc);
da086a3b
CS		 533 w->hops =
534 v->hops
535 + (VERTEX_IS_TYPE(NETWORK, w) ? 0 : 1);
536 } else {
537 /* NETWORK */
538 w->cost = v->cost;
539 w->hops = v->hops + 1;
540 }
541
542 /* nexthop calculation */
543 if (w->hops == 0)
544 ospf6_add_nexthop(
545 w->nh_list,
d62a17ae 546 ROUTER_LSDESC_GET_IFID(lsdesc), NULL);
da086a3b 547 else if (w->hops == 1 && v->hops == 0)
beadc736 548 ospf6_nexthop_calc(w, v, lsdesc, oa->ospf6);
da086a3b
CS		 549 else
550 ospf6_copy_nexthops(w->nh_list, v->nh_list);
551
552
553 /* add new candidate to the candidate_list */
554 if (IS_OSPF6_DEBUG_SPF(PROCESS))
555 zlog_debug(
d62a17ae 556 " New candidate: %s hops %d cost %d",
996c9314 557 w->name, w->hops, w->cost);
4ab0496e 558 vertex_pqueue_add(&candidate_list, w);
d62a17ae 559 }
560 }
561
4ab0496e 562 //vertex_pqueue_fini(&candidate_list);
d62a17ae 563
da086a3b
CS		 564 ospf6_remove_temp_router_lsa(oa);
565
d62a17ae 566 oa->spf_calculation++;
718e3744 567}
568
d62a17ae 569static void ospf6_spf_log_database(struct ospf6_area *oa)
2680aa2b 570{
d62a17ae 571 char *p, *end, buffer[256];
572 struct listnode *node;
573 struct ospf6_interface *oi;
574
575 p = buffer;
576 end = buffer + sizeof(buffer);
577
578 snprintf(p, end - p, "SPF on DB (#LSAs):");
579 p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) : end);
580 snprintf(p, end - p, " Area %s: %d", oa->name, oa->lsdb->count);
581 p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) : end);
582
583 for (ALL_LIST_ELEMENTS_RO(oa->if_list, node, oi)) {
584 snprintf(p, end - p, " I/F %s: %d", oi->interface->name,
585 oi->lsdb->count);
586 p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer)
587 : end);
588 }
589
590 zlog_debug("%s", buffer);
2680aa2b 591}
592
cc9f21da 593static void ospf6_spf_calculation_thread(struct thread *t)
718e3744 594{
d62a17ae 595 struct ospf6_area *oa;
596 struct ospf6 *ospf6;
597 struct timeval start, end, runtime;
598 struct listnode *node;
599 int areas_processed = 0;
600 char rbuf[32];
601
602 ospf6 = (struct ospf6 *)THREAD_ARG(t);
d62a17ae 603
604 /* execute SPF calculation */
605 monotime(&start);
ab0f1135 606 ospf6->ts_spf = start;
d62a17ae 607
95b3f03d 608 if (ospf6_check_and_set_router_abr(ospf6))
d62a17ae 609 ospf6_abr_range_reset_cost(ospf6);
610
611 for (ALL_LIST_ELEMENTS_RO(ospf6->area_list, node, oa)) {
612
613 if (oa == ospf6->backbone)
614 continue;
615
ab0f1135 616 monotime(&oa->ts_spf);
d62a17ae 617 if (IS_OSPF6_DEBUG_SPF(PROCESS))
618 zlog_debug("SPF calculation for Area %s", oa->name);
619 if (IS_OSPF6_DEBUG_SPF(DATABASE))
620 ospf6_spf_log_database(oa);
621
622 ospf6_spf_calculation(ospf6->router_id, oa->spf_table, oa);
623 ospf6_intra_route_calculation(oa);
624 ospf6_intra_brouter_calculation(oa);
625
626 areas_processed++;
627 }
628
629 if (ospf6->backbone) {
ab0f1135 630 monotime(&ospf6->backbone->ts_spf);
d62a17ae 631 if (IS_OSPF6_DEBUG_SPF(PROCESS))
632 zlog_debug("SPF calculation for Backbone area %s",
633 ospf6->backbone->name);
634 if (IS_OSPF6_DEBUG_SPF(DATABASE))
635 ospf6_spf_log_database(ospf6->backbone);
636
637 ospf6_spf_calculation(ospf6->router_id,
638 ospf6->backbone->spf_table,
639 ospf6->backbone);
640 ospf6_intra_route_calculation(ospf6->backbone);
641 ospf6_intra_brouter_calculation(ospf6->backbone);
642 areas_processed++;
643 }
644
ad500b22
K		 645 /* External LSA calculation */
646 ospf6_ase_calculate_timer_add(ospf6);
647
6735622c 648 if (ospf6_check_and_set_router_abr(ospf6)) {
d62a17ae 649 ospf6_abr_defaults_to_stub(ospf6);
6735622c
RW		 650 ospf6_abr_nssa_type_7_defaults(ospf6);
651 }
d62a17ae 652
653 monotime(&end);
654 timersub(&end, &start, &runtime);
655
656 ospf6->ts_spf_duration = runtime;
657
658 ospf6_spf_reason_string(ospf6->spf_reason, rbuf, sizeof(rbuf));
659
660 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
1bc19a9e
DS		 661 zlog_debug(
662 "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, Reason: %s",
663 areas_processed, (long long)runtime.tv_sec,
664 (long long)runtime.tv_usec, rbuf);
ab0f1135 665
d62a17ae 666 ospf6->last_spf_reason = ospf6->spf_reason;
667 ospf6_reset_spf_reason(ospf6);
718e3744 668}
669
3810e06e
DD		 670/* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
671 set timer for SPF calc. */
d62a17ae 672void ospf6_spf_schedule(struct ospf6 *ospf6, unsigned int reason)
718e3744 673{
d62a17ae 674 unsigned long delay, elapsed, ht;
675
cac84a16 676 /* OSPF instance does not exist. */
677 if (ospf6 == NULL)
678 return;
679
d62a17ae 680 ospf6_set_spf_reason(ospf6, reason);
681
682 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) {
683 char rbuf[32];
684 ospf6_spf_reason_string(reason, rbuf, sizeof(rbuf));
685 zlog_debug("SPF: calculation timer scheduled (reason %s)",
686 rbuf);
687 }
688
d62a17ae 689 /* SPF calculation timer is already scheduled. */
c905f04c 690 if (thread_is_scheduled(ospf6->t_spf_calc)) {
d62a17ae 691 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
692 zlog_debug(
693 "SPF: calculation timer is already scheduled: %p",
694 (void *)ospf6->t_spf_calc);
695 return;
696 }
697
698 elapsed = monotime_since(&ospf6->ts_spf, NULL) / 1000LL;
699 ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier;
700
701 if (ht > ospf6->spf_max_holdtime)
702 ht = ospf6->spf_max_holdtime;
703
704 /* Get SPF calculation delay time. */
705 if (elapsed < ht) {
706 /* Got an event within the hold time of last SPF. We need to
707 * increase the hold_multiplier, if it's not already at/past
708 * maximum value, and wasn't already increased..
709 */
710 if (ht < ospf6->spf_max_holdtime)
711 ospf6->spf_hold_multiplier++;
712
713 /* always honour the SPF initial delay */
714 if ((ht - elapsed) < ospf6->spf_delay)
715 delay = ospf6->spf_delay;
716 else
717 delay = ht - elapsed;
718 } else {
719 /* Event is past required hold-time of last SPF */
720 delay = ospf6->spf_delay;
721 ospf6->spf_hold_multiplier = 1;
722 }
723
724 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
1bc19a9e 725 zlog_debug("SPF: Rescheduling in %ld msec", delay);
d62a17ae 726
c905f04c 727 THREAD_OFF(ospf6->t_spf_calc);
d62a17ae 728 thread_add_timer_msec(master, ospf6_spf_calculation_thread, ospf6,
729 delay, &ospf6->t_spf_calc);
718e3744 730}
731
d62a17ae 732void ospf6_spf_display_subtree(struct vty *vty, const char *prefix, int rest,
305b639b
YR		 733 struct ospf6_vertex *v, json_object *json_obj,
734 bool use_json)
718e3744 735{
d62a17ae 736 struct listnode *node, *nnode;
737 struct ospf6_vertex *c;
738 char *next_prefix;
739 int len;
740 int restnum;
305b639b
YR		 741 json_object *json_childs = NULL;
742 json_object *json_child = NULL;
d62a17ae 743
305b639b
YR		 744 if (use_json) {
745 json_childs = json_object_new_object();
746 json_object_int_add(json_obj, "cost", v->cost);
747 } else {
748 /* "prefix" is the space prefix of the display line */
749 vty_out(vty, "%s+-%s [%d]\n", prefix, v->name, v->cost);
750 }
d62a17ae 751
752 len = strlen(prefix) + 4;
753 next_prefix = (char *)malloc(len);
754 if (next_prefix == NULL) {
755 vty_out(vty, "malloc failed\n");
756 return;
757 }
758 snprintf(next_prefix, len, "%s%s", prefix, (rest ? "| " : " "));
759
760 restnum = listcount(v->child_list);
761 for (ALL_LIST_ELEMENTS(v->child_list, node, nnode, c)) {
305b639b
YR		 762 if (use_json)
763 json_child = json_object_new_object();
764 else
765 restnum--;
d62a17ae 766
305b639b
YR		 767 ospf6_spf_display_subtree(vty, next_prefix, restnum, c,
768 json_child, use_json);
769
770 if (use_json)
771 json_object_object_add(json_childs, c->name,
772 json_child);
773 }
774 if (use_json) {
775 json_object_boolean_add(json_obj, "isLeafNode",
776 !listcount(v->child_list));
777 if (listcount(v->child_list))
778 json_object_object_add(json_obj, "children",
779 json_childs);
780 else
781 json_object_free(json_childs);
782 }
d62a17ae 783 free(next_prefix);
718e3744 784}
785
3b68735f 786DEFUN (debug_ospf6_spf_process,
787 debug_ospf6_spf_process_cmd,
788 "debug ospf6 spf process",
508e53e2 789 DEBUG_STR
790 OSPF6_STR
791 "Debug SPF Calculation\n"
3b68735f 792 "Debug Detailed SPF Process\n"
508e53e2 793 )
718e3744 794{
d62a17ae 795 unsigned char level = 0;
796 level = OSPF6_DEBUG_SPF_PROCESS;
797 OSPF6_DEBUG_SPF_ON(level);
798 return CMD_SUCCESS;
718e3744 799}
800
3b68735f 801DEFUN (debug_ospf6_spf_time,
802 debug_ospf6_spf_time_cmd,
803 "debug ospf6 spf time",
508e53e2 804 DEBUG_STR
718e3744 805 OSPF6_STR
508e53e2 806 "Debug SPF Calculation\n"
3b68735f 807 "Measure time taken by SPF Calculation\n"
508e53e2 808 )
718e3744 809{
d62a17ae 810 unsigned char level = 0;
811 level = OSPF6_DEBUG_SPF_TIME;
812 OSPF6_DEBUG_SPF_ON(level);
813 return CMD_SUCCESS;
718e3744 814}
815
2680aa2b 816DEFUN (debug_ospf6_spf_database,
817 debug_ospf6_spf_database_cmd,
818 "debug ospf6 spf database",
819 DEBUG_STR
820 OSPF6_STR
821 "Debug SPF Calculation\n"
822 "Log number of LSAs at SPF Calculation time\n"
823 )
824{
d62a17ae 825 unsigned char level = 0;
826 level = OSPF6_DEBUG_SPF_DATABASE;
827 OSPF6_DEBUG_SPF_ON(level);
828 return CMD_SUCCESS;
2680aa2b 829}
830
3b68735f 831DEFUN (no_debug_ospf6_spf_process,
832 no_debug_ospf6_spf_process_cmd,
833 "no debug ospf6 spf process",
508e53e2 834 NO_STR
835 DEBUG_STR
836 OSPF6_STR
837 "Quit Debugging SPF Calculation\n"
3b68735f 838 "Quit Debugging Detailed SPF Process\n"
508e53e2 839 )
718e3744 840{
d62a17ae 841 unsigned char level = 0;
842 level = OSPF6_DEBUG_SPF_PROCESS;
843 OSPF6_DEBUG_SPF_OFF(level);
844 return CMD_SUCCESS;
718e3744 845}
846
3b68735f 847DEFUN (no_debug_ospf6_spf_time,
848 no_debug_ospf6_spf_time_cmd,
849 "no debug ospf6 spf time",
508e53e2 850 NO_STR
851 DEBUG_STR
718e3744 852 OSPF6_STR
508e53e2 853 "Quit Debugging SPF Calculation\n"
3b68735f 854 "Quit Measuring time taken by SPF Calculation\n"
508e53e2 855 )
718e3744 856{
d62a17ae 857 unsigned char level = 0;
858 level = OSPF6_DEBUG_SPF_TIME;
859 OSPF6_DEBUG_SPF_OFF(level);
860 return CMD_SUCCESS;
718e3744 861}
862
2680aa2b 863DEFUN (no_debug_ospf6_spf_database,
864 no_debug_ospf6_spf_database_cmd,
865 "no debug ospf6 spf database",
866 NO_STR
867 DEBUG_STR
868 OSPF6_STR
869 "Debug SPF Calculation\n"
870 "Quit Logging number of LSAs at SPF Calculation time\n"
871 )
872{
d62a17ae 873 unsigned char level = 0;
874 level = OSPF6_DEBUG_SPF_DATABASE;
875 OSPF6_DEBUG_SPF_OFF(level);
876 return CMD_SUCCESS;
2680aa2b 877}
878
d62a17ae 879static int ospf6_timers_spf_set(struct vty *vty, unsigned int delay,
880 unsigned int hold, unsigned int max)
3810e06e 881{
d62a17ae 882 VTY_DECLVAR_CONTEXT(ospf6, ospf);
3810e06e 883
d62a17ae 884 ospf->spf_delay = delay;
885 ospf->spf_holdtime = hold;
886 ospf->spf_max_holdtime = max;
3810e06e 887
d62a17ae 888 return CMD_SUCCESS;
3810e06e
DD		 889}
890
891DEFUN (ospf6_timers_throttle_spf,
892 ospf6_timers_throttle_spf_cmd,
6147e2c6 893 "timers throttle spf (0-600000) (0-600000) (0-600000)",
3810e06e
DD		 894 "Adjust routing timers\n"
895 "Throttling adaptive timer\n"
896 "OSPF6 SPF timers\n"
897 "Delay (msec) from first change received till SPF calculation\n"
898 "Initial hold time (msec) between consecutive SPF calculations\n"
899 "Maximum hold time (msec)\n")
900{
d62a17ae 901 int idx_number = 3;
902 int idx_number_2 = 4;
903 int idx_number_3 = 5;
904 unsigned int delay, hold, max;
3810e06e 905
d62a17ae 906 delay = strtoul(argv[idx_number]->arg, NULL, 10);
907 hold = strtoul(argv[idx_number_2]->arg, NULL, 10);
908 max = strtoul(argv[idx_number_3]->arg, NULL, 10);
3810e06e 909
d62a17ae 910 return ospf6_timers_spf_set(vty, delay, hold, max);
3810e06e
DD		 911}
912
913DEFUN (no_ospf6_timers_throttle_spf,
914 no_ospf6_timers_throttle_spf_cmd,
1d68dbfe 915 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
3810e06e
DD		 916 NO_STR
917 "Adjust routing timers\n"
918 "Throttling adaptive timer\n"
1d68dbfe
DW		 919 "OSPF6 SPF timers\n"
920 "Delay (msec) from first change received till SPF calculation\n"
921 "Initial hold time (msec) between consecutive SPF calculations\n"
922 "Maximum hold time (msec)\n")
3810e06e 923{
d62a17ae 924 return ospf6_timers_spf_set(vty, OSPF_SPF_DELAY_DEFAULT,
925 OSPF_SPF_HOLDTIME_DEFAULT,
926 OSPF_SPF_MAX_HOLDTIME_DEFAULT);
3810e06e
DD		 927}
928
813d4307 929
d62a17ae 930int config_write_ospf6_debug_spf(struct vty *vty)
718e3744 931{
d62a17ae 932 if (IS_OSPF6_DEBUG_SPF(PROCESS))
933 vty_out(vty, "debug ospf6 spf process\n");
934 if (IS_OSPF6_DEBUG_SPF(TIME))
935 vty_out(vty, "debug ospf6 spf time\n");
936 if (IS_OSPF6_DEBUG_SPF(DATABASE))
937 vty_out(vty, "debug ospf6 spf database\n");
938 return 0;
718e3744 939}
940
beadc736 941void ospf6_spf_config_write(struct vty *vty, struct ospf6 *ospf6)
3810e06e
DD		 942{
943
d62a17ae 944 if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT
945 || ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT
946 || ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT)
947 vty_out(vty, " timers throttle spf %d %d %d\n",
948 ospf6->spf_delay, ospf6->spf_holdtime,
949 ospf6->spf_max_holdtime);
3810e06e
DD		 950}
951
d62a17ae 952void install_element_ospf6_debug_spf(void)
508e53e2 953{
d62a17ae 954 install_element(ENABLE_NODE, &debug_ospf6_spf_process_cmd);
955 install_element(ENABLE_NODE, &debug_ospf6_spf_time_cmd);
956 install_element(ENABLE_NODE, &debug_ospf6_spf_database_cmd);
957 install_element(ENABLE_NODE, &no_debug_ospf6_spf_process_cmd);
958 install_element(ENABLE_NODE, &no_debug_ospf6_spf_time_cmd);
959 install_element(ENABLE_NODE, &no_debug_ospf6_spf_database_cmd);
960 install_element(CONFIG_NODE, &debug_ospf6_spf_process_cmd);
961 install_element(CONFIG_NODE, &debug_ospf6_spf_time_cmd);
962 install_element(CONFIG_NODE, &debug_ospf6_spf_database_cmd);
963 install_element(CONFIG_NODE, &no_debug_ospf6_spf_process_cmd);
964 install_element(CONFIG_NODE, &no_debug_ospf6_spf_time_cmd);
965 install_element(CONFIG_NODE, &no_debug_ospf6_spf_database_cmd);
508e53e2 966}
718e3744 967
d62a17ae 968void ospf6_spf_init(void)
718e3744 969{
d62a17ae 970 install_element(OSPF6_NODE, &ospf6_timers_throttle_spf_cmd);
971 install_element(OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd);
718e3744 972}
da086a3b
CS		 973
974/* Create Aggregated Large Router-LSA from multiple Link-State IDs
975 * RFC 5340 A 4.3:
976 * When more than one router-LSA is received from a single router,
977 * the links are processed as if concatenated into a single LSA.*/
978struct ospf6_lsa *ospf6_create_single_router_lsa(struct ospf6_area *area,
979 struct ospf6_lsdb *lsdb,
980 uint32_t adv_router)
981{
982 struct ospf6_lsa *lsa = NULL;
983 struct ospf6_lsa *rtr_lsa = NULL;
984 struct ospf6_lsa_header *lsa_header = NULL;
985 uint8_t *new_header = NULL;
986 const struct route_node *end = NULL;
987 uint16_t lsa_length, total_lsa_length = 0, num_lsa = 0;
d7c0a89a 988 uint16_t type = 0;
da086a3b
CS		 989 char ifbuf[16];
990 uint32_t interface_id;
991 caddr_t lsd;
992
996c9314
LB		 993 lsa_length = sizeof(struct ospf6_lsa_header)
994 + sizeof(struct ospf6_router_lsa);
da086a3b
CS		 995 total_lsa_length = lsa_length;
996 type = htons(OSPF6_LSTYPE_ROUTER);
997
998 /* First check Aggregated LSA formed earlier in Cache */
999 lsa = ospf6_lsdb_lookup(type, htonl(0), adv_router,
1000 area->temp_router_lsa_lsdb);
1001 if (lsa)
1002 return lsa;
1003
1004 inet_ntop(AF_INET, &adv_router, ifbuf, sizeof(ifbuf));
1005
1006 /* Determine total LSA length from all link state ids */
1007 end = ospf6_lsdb_head(lsdb, 2, type, adv_router, &rtr_lsa);
1008 while (rtr_lsa) {
1009 lsa = rtr_lsa;
1010 if (OSPF6_LSA_IS_MAXAGE(rtr_lsa)) {
1011 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1012 continue;
1013 }
c4efd0f4 1014 lsa_header = rtr_lsa->header;
996c9314 1015 total_lsa_length += (ntohs(lsa_header->length) - lsa_length);
da086a3b
CS		 1016 num_lsa++;
1017 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1018 }
1019 if (IS_OSPF6_DEBUG_SPF(PROCESS))
15569c58
DA		 1020 zlog_debug("%s: adv_router %s num_lsa %u to convert.", __func__,
1021 ifbuf, num_lsa);
da086a3b
CS		 1022 if (num_lsa == 1)
1023 return lsa;
1024
1025 if (num_lsa == 0) {
1026 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1027 zlog_debug("%s: adv_router %s not found in LSDB.",
15569c58 1028 __func__, ifbuf);
da086a3b
CS		 1029 return NULL;
1030 }
1031
771e1fbe
DL		 1032 lsa = ospf6_lsa_alloc(total_lsa_length);
1033 new_header = (uint8_t *)lsa->header;
da086a3b
CS		 1034
1035 lsa->lsdb = area->temp_router_lsa_lsdb;
1036
1037 /* Fill Larger LSA Payload */
1038 end = ospf6_lsdb_head(lsdb, 2, type, adv_router, &rtr_lsa);
cf29dab3
DS		 1039
1040 /*
1041 * We assume at this point in time that rtr_lsa is
1042 * a valid pointer.
1043 */
1044 assert(rtr_lsa);
1045 if (!OSPF6_LSA_IS_MAXAGE(rtr_lsa)) {
1046 /* Append first Link State ID LSA */
c4efd0f4 1047 lsa_header = rtr_lsa->header;
cf29dab3
DS		 1048 memcpy(new_header, lsa_header, ntohs(lsa_header->length));
1049 /* Assign new lsa length as aggregated length. */
1050 ((struct ospf6_lsa_header *)new_header)->length =
1051 htons(total_lsa_length);
1052 new_header += ntohs(lsa_header->length);
1053 num_lsa--;
da086a3b
CS		 1054 }
1055
1056 /* Print LSA Name */
1057 ospf6_lsa_printbuf(lsa, lsa->name, sizeof(lsa->name));
1058
1059 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1060 while (rtr_lsa) {
1061 if (OSPF6_LSA_IS_MAXAGE(rtr_lsa)) {
1062 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1063 continue;
1064 }
1065
1066 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
1067 lsd = OSPF6_LSA_HEADER_END(rtr_lsa->header) + 4;
1068 interface_id = ROUTER_LSDESC_GET_IFID(lsd);
1069 inet_ntop(AF_INET, &interface_id, ifbuf, sizeof(ifbuf));
996c9314
LB		 1070 zlog_debug(
1071 "%s: Next Router LSA %s to aggreat with len %u interface_id %s",
15569c58 1072 __func__, rtr_lsa->name,
996c9314 1073 ntohs(lsa_header->length), ifbuf);
da086a3b
CS		 1074 }
1075
1076 /* Append Next Link State ID LSA */
c4efd0f4 1077 lsa_header = rtr_lsa->header;
da086a3b
CS		 1078 memcpy(new_header, (OSPF6_LSA_HEADER_END(rtr_lsa->header) + 4),
1079 (ntohs(lsa_header->length) - lsa_length));
1080 new_header += (ntohs(lsa_header->length) - lsa_length);
1081 num_lsa--;
1082
1083 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1084 }
1085
1086 /* Calculate birth of this lsa */
1087 ospf6_lsa_age_set(lsa);
1088
1089 /* Store Aggregated LSA into area temp lsdb */
1090 ospf6_lsdb_add(lsa, area->temp_router_lsa_lsdb);
1091
1092 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1093 zlog_debug("%s: LSA %s id %u type 0%x len %u num_lsa %u",
15569c58
DA		 1094 __func__, lsa->name, ntohl(lsa->header->id),
1095 ntohs(lsa->header->type), ntohs(lsa->header->length),
1096 num_lsa);
da086a3b
CS		 1097
1098 return lsa;
1099}
1100
1101void ospf6_remove_temp_router_lsa(struct ospf6_area *area)
1102{
2e37407f 1103 struct ospf6_lsa *lsa = NULL, *lsanext;
da086a3b 1104
2e37407f 1105 for (ALL_LSDB(area->temp_router_lsa_lsdb, lsa, lsanext)) {
da086a3b 1106 if (IS_OSPF6_DEBUG_SPF(PROCESS))
996c9314
LB		 1107 zlog_debug(
1108 "%s Remove LSA %s lsa->lock %u lsdb count %u",
5e81f5dd 1109 __func__, lsa->name, lsa->lock,
996c9314 1110 area->temp_router_lsa_lsdb->count);
da086a3b
CS		 1111 ospf6_lsdb_remove(lsa, area->temp_router_lsa_lsdb);
1112 }
1113}
ad500b22
K		 1114
1115int ospf6_ase_calculate_route(struct ospf6 *ospf6, struct ospf6_lsa *lsa,
1116 struct ospf6_area *area)
1117{
35769de4 1118 struct ospf6_route *route;
ad500b22
K		 1119 struct ospf6_as_external_lsa *external;
1120 struct prefix prefix;
1121 void (*hook_add)(struct ospf6_route *) = NULL;
1122 void (*hook_remove)(struct ospf6_route *) = NULL;
1123
1124 assert(lsa);
1125
1126 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1127 zlog_debug("%s : start", __func__);
1128
1129 if (ntohs(lsa->header->type) == OSPF6_LSTYPE_TYPE_7)
1130 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1131 zlog_debug("%s: Processing Type-7", __func__);
1132
1133 /* Stay away from any Local Translated Type-7 LSAs */
1134 if (CHECK_FLAG(lsa->flag, OSPF6_LSA_LOCAL_XLT)) {
1135 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1136 zlog_debug("%s: Rejecting Local translated LSA",
1137 __func__);
1138 return 0;
1139 }
1140
1141 external = (struct ospf6_as_external_lsa *)OSPF6_LSA_HEADER_END(
1142 lsa->header);
1143 prefix.family = AF_INET6;
1144 prefix.prefixlen = external->prefix.prefix_length;
1145 ospf6_prefix_in6_addr(&prefix.u.prefix6, external, &external->prefix);
1146
1147 if (ntohs(lsa->header->type) == OSPF6_LSTYPE_AS_EXTERNAL) {
1148 hook_add = ospf6->route_table->hook_add;
1149 hook_remove = ospf6->route_table->hook_remove;
1150 ospf6->route_table->hook_add = NULL;
1151 ospf6->route_table->hook_remove = NULL;
1152
ad500b22
K		 1153 if (!OSPF6_LSA_IS_MAXAGE(lsa))
1154 ospf6_asbr_lsa_add(lsa);
1155
1156 ospf6->route_table->hook_add = hook_add;
1157 ospf6->route_table->hook_remove = hook_remove;
1158
1159 route = ospf6_route_lookup(&prefix, ospf6->route_table);
1160 if (route == NULL) {
1161 if (IS_OSPF6_DEBUG_SPF(PROCESS))
35769de4 1162 zlog_debug("%s: no external route %pFX",
ad500b22
K		 1163 __func__, &prefix);
1164 return 0;
1165 }
1166
1167 if (CHECK_FLAG(route->flag, OSPF6_ROUTE_REMOVE)
35769de4 1168 && CHECK_FLAG(route->flag, OSPF6_ROUTE_ADD)) {
ad500b22
K		 1169 UNSET_FLAG(route->flag, OSPF6_ROUTE_REMOVE);
1170 UNSET_FLAG(route->flag, OSPF6_ROUTE_ADD);
1171 }
1172
1173 if (CHECK_FLAG(route->flag, OSPF6_ROUTE_REMOVE))
1174 ospf6_route_remove(route, ospf6->route_table);
1175 else if (CHECK_FLAG(route->flag, OSPF6_ROUTE_ADD)
1176 || CHECK_FLAG(route->flag, OSPF6_ROUTE_CHANGE)) {
1177 if (hook_add) {
1178 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1179 zlog_debug(
1180 "%s: add external route %pFX",
1181 __func__, &prefix);
1182 (*hook_add)(route);
1183 }
ad500b22
K		 1184 }
1185 } else if (ntohs(lsa->header->type) == OSPF6_LSTYPE_TYPE_7) {
1186 hook_add = area->route_table->hook_add;
1187 hook_remove = area->route_table->hook_remove;
1188 area->route_table->hook_add = NULL;
1189 area->route_table->hook_remove = NULL;
1190
ad500b22
K		 1191 if (!OSPF6_LSA_IS_MAXAGE(lsa))
1192 ospf6_asbr_lsa_add(lsa);
1193
1194 area->route_table->hook_add = hook_add;
1195 area->route_table->hook_remove = hook_remove;
1196
1197 route = ospf6_route_lookup(&prefix, area->route_table);
1198 if (route == NULL) {
1199 if (IS_OSPF6_DEBUG_SPF(PROCESS))
35769de4 1200 zlog_debug("%s: no route %pFX, area %s",
ad500b22
K		 1201 __func__, &prefix, area->name);
1202 return 0;
1203 }
1204
1205 if (CHECK_FLAG(route->flag, OSPF6_ROUTE_REMOVE)
35769de4 1206 && CHECK_FLAG(route->flag, OSPF6_ROUTE_ADD)) {
ad500b22
K		 1207 UNSET_FLAG(route->flag, OSPF6_ROUTE_REMOVE);
1208 UNSET_FLAG(route->flag, OSPF6_ROUTE_ADD);
1209 }
1210
1211 if (CHECK_FLAG(route->flag, OSPF6_ROUTE_REMOVE)) {
1212 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1213 zlog_debug("%s : remove route %pFX, area %s",
1214 __func__, &prefix, area->name);
1215 ospf6_route_remove(route, area->route_table);
1216 } else if (CHECK_FLAG(route->flag, OSPF6_ROUTE_ADD)
1217 || CHECK_FLAG(route->flag, OSPF6_ROUTE_CHANGE)) {
1218 if (hook_add) {
1219 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1220 zlog_debug(
1221 "%s: add nssa route %pFX, area %s",
1222 __func__, &prefix, area->name);
1223 (*hook_add)(route);
1224 }
1225 ospf6_abr_check_translate_nssa(area, lsa);
ad500b22
K		 1226 }
1227 }
1228 return 0;
1229}
1230
cc9f21da 1231static void ospf6_ase_calculate_timer(struct thread *t)
ad500b22
K		 1232{
1233 struct ospf6 *ospf6;
1234 struct ospf6_lsa *lsa;
1235 struct listnode *node, *nnode;
1236 struct ospf6_area *area;
1237 uint16_t type;
1238
1239 ospf6 = THREAD_ARG(t);
ad500b22
K		 1240
1241 /* Calculate external route for each AS-external-LSA */
1242 type = htons(OSPF6_LSTYPE_AS_EXTERNAL);
1243 for (ALL_LSDB_TYPED(ospf6->lsdb, type, lsa))
1244 ospf6_ase_calculate_route(ospf6, lsa, NULL);
1245
1246 /* This version simple adds to the table all NSSA areas */
1247 if (ospf6->anyNSSA) {
1248 for (ALL_LIST_ELEMENTS(ospf6->area_list, node, nnode, area)) {
1249 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1250 zlog_debug("%s : looking at area %s", __func__,
1251 area->name);
1252
6df89791
RW		 1253 type = htons(OSPF6_LSTYPE_TYPE_7);
1254 for (ALL_LSDB_TYPED(area->lsdb, type, lsa))
1255 ospf6_ase_calculate_route(ospf6, lsa, area);
ad500b22
K		 1256 }
1257 }
71165098
RW		 1258
1259 if (ospf6->gr_info.finishing_restart) {
1260 /*
1261 * The routing table computation is complete. Uninstall remnant
1262 * routes that were installed before the restart, but that are
1263 * no longer valid.
1264 */
1265 ospf6_zebra_gr_disable(ospf6);
1266 ospf6->gr_info.finishing_restart = false;
1267 }
ad500b22
K		 1268}
1269
1270void ospf6_ase_calculate_timer_add(struct ospf6 *ospf6)
1271{
1272 if (ospf6 == NULL)
1273 return;
1274
1275 thread_add_timer(master, ospf6_ase_calculate_timer, ospf6,
1276 OSPF6_ASE_CALC_INTERVAL, &ospf6->t_ase_calc);
1277}
FRRouting mirror