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