]> git.proxmox.com Git - mirror_frr.git/blob - ospf6d/ospf6_spf.c
projects / mirror_frr.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Merge pull request #4192 from bisdhdh/biswajitfrr_4
[mirror_frr.git] / ospf6d / ospf6_spf.c
1 /*
2 * Copyright (C) 2003 Yasuhiro Ohara
3 *
4 * This file is part of GNU Zebra.
5 *
6 * GNU Zebra is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation; either version 2, or (at your option) any
9 * later version.
10 *
11 * GNU Zebra is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License 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_spf.h"
41 #include "ospf6_intra.h"
42 #include "ospf6_interface.h"
43 #include "ospf6d.h"
44 #include "ospf6_abr.h"
45
46 unsigned char conf_debug_ospf6_spf = 0;
47
48 static void ospf6_spf_copy_nexthops_to_route(struct ospf6_route *rt,
49 struct ospf6_vertex *v)
50 {
51 if (rt && v)
52 ospf6_copy_nexthops(rt->nh_list, v->nh_list);
53 }
54
55 static void ospf6_spf_merge_nexthops_to_route(struct ospf6_route *rt,
56 struct ospf6_vertex *v)
57 {
58 if (rt && v)
59 ospf6_merge_nexthops(rt->nh_list, v->nh_list);
60 }
61
62 static unsigned int ospf6_spf_get_ifindex_from_nh(struct ospf6_vertex *v)
63 {
64 struct ospf6_nexthop *nh;
65 struct listnode *node;
66
67 if (v) {
68 node = listhead(v->nh_list);
69 if (node) {
70 nh = listgetdata(node);
71 if (nh)
72 return (nh->ifindex);
73 }
74 }
75 return 0;
76 }
77
78 static int ospf6_vertex_cmp(const struct ospf6_vertex *va,
79 const struct ospf6_vertex *vb)
80 {
81 /* ascending order */
82 if (va->cost != vb->cost)
83 return (va->cost - vb->cost);
84 if (va->hops != vb->hops)
85 return (va->hops - vb->hops);
86 return 0;
87 }
88 DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue, struct ospf6_vertex, pqi,
89 ospf6_vertex_cmp)
90
91 static int ospf6_vertex_id_cmp(void *a, void *b)
92 {
93 struct ospf6_vertex *va = (struct ospf6_vertex *)a;
94 struct ospf6_vertex *vb = (struct ospf6_vertex *)b;
95 int ret = 0;
96
97 ret = ntohl(ospf6_linkstate_prefix_adv_router(&va->vertex_id))
98 - ntohl(ospf6_linkstate_prefix_adv_router(&vb->vertex_id));
99 if (ret)
100 return ret;
101
102 ret = ntohl(ospf6_linkstate_prefix_id(&va->vertex_id))
103 - ntohl(ospf6_linkstate_prefix_id(&vb->vertex_id));
104 return ret;
105 }
106
107 static struct ospf6_vertex *ospf6_vertex_create(struct ospf6_lsa *lsa)
108 {
109 struct ospf6_vertex *v;
110
111 v = XMALLOC(MTYPE_OSPF6_VERTEX, sizeof(struct ospf6_vertex));
112
113 /* type */
114 if (ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER) {
115 v->type = OSPF6_VERTEX_TYPE_ROUTER;
116 /* Router LSA use Link ID 0 as base in vertex_id */
117 ospf6_linkstate_prefix(lsa->header->adv_router, htonl(0),
118 &v->vertex_id);
119 } else if (ntohs(lsa->header->type) == OSPF6_LSTYPE_NETWORK) {
120 v->type = OSPF6_VERTEX_TYPE_NETWORK;
121 /* vertex_id */
122 ospf6_linkstate_prefix(lsa->header->adv_router, lsa->header->id,
123 &v->vertex_id);
124 } else
125 assert(0);
126
127 /* name */
128 ospf6_linkstate_prefix2str(&v->vertex_id, v->name, sizeof(v->name));
129
130 if (IS_OSPF6_DEBUG_SPF(PROCESS))
131 zlog_debug("%s: Creating vertex %s of type %s (0x%04hx) lsa %s",
132 __func__, v->name,
133 ((ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER)
134 ? "Router"
135 : "N/W"),
136 ntohs(lsa->header->type), lsa->name);
137
138
139 /* Associated LSA */
140 v->lsa = lsa;
141
142 /* capability bits + options */
143 v->capability = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa->header));
144 v->options[0] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa->header) + 1);
145 v->options[1] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa->header) + 2);
146 v->options[2] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa->header) + 3);
147
148 v->nh_list = list_new();
149 v->nh_list->cmp = (int (*)(void *, void *))ospf6_nexthop_cmp;
150 v->nh_list->del = (void (*)(void *))ospf6_nexthop_delete;
151
152 v->parent = NULL;
153 v->child_list = list_new();
154 v->child_list->cmp = ospf6_vertex_id_cmp;
155
156 return v;
157 }
158
159 static void ospf6_vertex_delete(struct ospf6_vertex *v)
160 {
161 list_delete(&v->nh_list);
162 list_delete(&v->child_list);
163 XFREE(MTYPE_OSPF6_VERTEX, v);
164 }
165
166 static struct ospf6_lsa *ospf6_lsdesc_lsa(caddr_t lsdesc,
167 struct ospf6_vertex *v)
168 {
169 struct ospf6_lsa *lsa = NULL;
170 uint16_t type = 0;
171 uint32_t id = 0, adv_router = 0;
172
173 if (VERTEX_IS_TYPE(NETWORK, v)) {
174 type = htons(OSPF6_LSTYPE_ROUTER);
175 id = htonl(0);
176 adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc);
177 } else {
178 if (ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, lsdesc)) {
179 type = htons(OSPF6_LSTYPE_ROUTER);
180 id = htonl(0);
181 adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc);
182 } else if (ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK, lsdesc)) {
183 type = htons(OSPF6_LSTYPE_NETWORK);
184 id = htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc));
185 adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc);
186 }
187 }
188
189 if (type == htons(OSPF6_LSTYPE_NETWORK))
190 lsa = ospf6_lsdb_lookup(type, id, adv_router, v->area->lsdb);
191 else
192 lsa = ospf6_create_single_router_lsa(v->area, v->area->lsdb,
193 adv_router);
194 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
195 char ibuf[16], abuf[16];
196 inet_ntop(AF_INET, &id, ibuf, sizeof(ibuf));
197 inet_ntop(AF_INET, &adv_router, abuf, sizeof(abuf));
198 if (lsa)
199 zlog_debug(" Link to: %s len %u, V %s", lsa->name,
200 ntohs(lsa->header->length), v->name);
201 else
202 zlog_debug(" Link to: [%s Id:%s Adv:%s] No LSA , V %s",
203 ospf6_lstype_name(type), ibuf, abuf,
204 v->name);
205 }
206
207 return lsa;
208 }
209
210 static char *ospf6_lsdesc_backlink(struct ospf6_lsa *lsa, caddr_t lsdesc,
211 struct ospf6_vertex *v)
212 {
213 caddr_t backlink, found = NULL;
214 int size;
215
216 size = (OSPF6_LSA_IS_TYPE(ROUTER, lsa)
217 ? sizeof(struct ospf6_router_lsdesc)
218 : sizeof(struct ospf6_network_lsdesc));
219 for (backlink = OSPF6_LSA_HEADER_END(lsa->header) + 4;
220 backlink + size <= OSPF6_LSA_END(lsa->header); backlink += size) {
221 assert(!(OSPF6_LSA_IS_TYPE(NETWORK, lsa)
222 && VERTEX_IS_TYPE(NETWORK, v)));
223
224 if (OSPF6_LSA_IS_TYPE(NETWORK, lsa)
225 && NETWORK_LSDESC_GET_NBR_ROUTERID(backlink)
226 == v->lsa->header->adv_router)
227 found = backlink;
228 else if (VERTEX_IS_TYPE(NETWORK, v)
229 && ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK, backlink)
230 && ROUTER_LSDESC_GET_NBR_ROUTERID(backlink)
231 == v->lsa->header->adv_router
232 && ROUTER_LSDESC_GET_NBR_IFID(backlink)
233 == ntohl(v->lsa->header->id))
234 found = backlink;
235 else {
236 if (!ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, backlink)
237 || !ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, lsdesc))
238 continue;
239 if (ROUTER_LSDESC_GET_NBR_IFID(backlink)
240 != ROUTER_LSDESC_GET_IFID(lsdesc)
241 || ROUTER_LSDESC_GET_NBR_IFID(lsdesc)
242 != ROUTER_LSDESC_GET_IFID(backlink))
243 continue;
244 if (ROUTER_LSDESC_GET_NBR_ROUTERID(backlink)
245 != v->lsa->header->adv_router
246 || ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc)
247 != lsa->header->adv_router)
248 continue;
249 found = backlink;
250 }
251 }
252
253 if (IS_OSPF6_DEBUG_SPF(PROCESS))
254 zlog_debug("Vertex %s Lsa %s Backlink %s", v->name, lsa->name,
255 (found ? "OK" : "FAIL"));
256
257 return found;
258 }
259
260 static void ospf6_nexthop_calc(struct ospf6_vertex *w, struct ospf6_vertex *v,
261 caddr_t lsdesc)
262 {
263 int i;
264 ifindex_t ifindex;
265 struct ospf6_interface *oi;
266 uint16_t type;
267 uint32_t adv_router;
268 struct ospf6_lsa *lsa;
269 struct ospf6_link_lsa *link_lsa;
270 char buf[64];
271
272 assert(VERTEX_IS_TYPE(ROUTER, w));
273 ifindex = (VERTEX_IS_TYPE(NETWORK, v) ? ospf6_spf_get_ifindex_from_nh(v)
274 : ROUTER_LSDESC_GET_IFID(lsdesc));
275 if (ifindex == 0) {
276 flog_err(EC_LIB_DEVELOPMENT, "No nexthop ifindex at vertex %s",
277 v->name);
278 return;
279 }
280
281 oi = ospf6_interface_lookup_by_ifindex(ifindex);
282 if (oi == NULL) {
283 if (IS_OSPF6_DEBUG_SPF(PROCESS))
284 zlog_debug("Can't find interface in SPF: ifindex %d",
285 ifindex);
286 return;
287 }
288
289 type = htons(OSPF6_LSTYPE_LINK);
290 adv_router = (VERTEX_IS_TYPE(NETWORK, v)
291 ? NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc)
292 : ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc));
293
294 i = 0;
295 for (ALL_LSDB_TYPED_ADVRTR(oi->lsdb, type, adv_router, lsa)) {
296 if (VERTEX_IS_TYPE(ROUTER, v)
297 && htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc))
298 != lsa->header->id)
299 continue;
300
301 link_lsa = (struct ospf6_link_lsa *)OSPF6_LSA_HEADER_END(
302 lsa->header);
303 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
304 inet_ntop(AF_INET6, &link_lsa->linklocal_addr, buf,
305 sizeof(buf));
306 zlog_debug(" nexthop %s from %s", buf, lsa->name);
307 }
308
309 ospf6_add_nexthop(w->nh_list, ifindex,
310 &link_lsa->linklocal_addr);
311 i++;
312 }
313
314 if (i == 0 && IS_OSPF6_DEBUG_SPF(PROCESS))
315 zlog_debug("No nexthop for %s found", w->name);
316 }
317
318 static int ospf6_spf_install(struct ospf6_vertex *v,
319 struct ospf6_route_table *result_table)
320 {
321 struct ospf6_route *route, *parent_route;
322 struct ospf6_vertex *prev;
323 char pbuf[PREFIX2STR_BUFFER];
324
325 if (IS_OSPF6_DEBUG_SPF(PROCESS))
326 zlog_debug("SPF install %s (lsa %s) hops %d cost %d", v->name,
327 v->lsa->name, v->hops, v->cost);
328
329 route = ospf6_route_lookup(&v->vertex_id, result_table);
330 if (route && route->path.cost < v->cost) {
331 if (IS_OSPF6_DEBUG_SPF(PROCESS))
332 zlog_debug(
333 " already installed with lower cost (%d), ignore",
334 route->path.cost);
335 ospf6_vertex_delete(v);
336 return -1;
337 } else if (route && route->path.cost == v->cost) {
338 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
339 prefix2str(&route->prefix, pbuf, sizeof(pbuf));
340 zlog_debug(
341 " another path found to route %s lsa %s, merge",
342 pbuf, v->lsa->name);
343 }
344 ospf6_spf_merge_nexthops_to_route(route, v);
345
346 prev = (struct ospf6_vertex *)route->route_option;
347 assert(prev->hops <= v->hops);
348
349 if ((VERTEX_IS_TYPE(ROUTER, v)
350 && route->path.origin.id != v->lsa->header->id)) {
351 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
352 zlog_debug(
353 "%s: V lsa %s id %u, route id %u are different",
354 __PRETTY_FUNCTION__, v->lsa->name,
355 ntohl(v->lsa->header->id),
356 ntohl(route->path.origin.id));
357 }
358 return 0;
359 }
360
361 ospf6_vertex_delete(v);
362 return -1;
363 }
364
365 /* There should be no case where candidate being installed (variable
366 "v") is closer than the one in the SPF tree (variable "route").
367 In the case something has gone wrong with the behavior of
368 Priority-Queue. */
369
370 /* the case where the route exists already is handled and returned
371 up to here. */
372 assert(route == NULL);
373
374 route = ospf6_route_create();
375 memcpy(&route->prefix, &v->vertex_id, sizeof(struct prefix));
376 route->type = OSPF6_DEST_TYPE_LINKSTATE;
377 route->path.type = OSPF6_PATH_TYPE_INTRA;
378 route->path.origin.type = v->lsa->header->type;
379 route->path.origin.id = v->lsa->header->id;
380 route->path.origin.adv_router = v->lsa->header->adv_router;
381 route->path.metric_type = 1;
382 route->path.cost = v->cost;
383 route->path.u.cost_e2 = v->hops;
384 route->path.router_bits = v->capability;
385 route->path.options[0] = v->options[0];
386 route->path.options[1] = v->options[1];
387 route->path.options[2] = v->options[2];
388
389 ospf6_spf_copy_nexthops_to_route(route, v);
390
391 /*
392 * The SPF logic implementation does not transfer the multipathing
393 * properties
394 * of a parent to a child node. Thus if there was a 3-way multipath to a
395 * node's parent and a single hop from the parent to the child, the
396 * logic of
397 * creating new vertices and computing next hops prevents there from
398 * being 3
399 * paths to the child node. This is primarily because the resolution of
400 * multipath is done in this routine, not in the main spf loop.
401 *
402 * The following logic addresses that problem by merging the parent's
403 * nexthop
404 * information with the child's, if the parent is not the root of the
405 * tree.
406 * This is based on the assumption that before a node's route is
407 * installed,
408 * its parent's route's nexthops have already been installed.
409 */
410 if (v->parent && v->parent->hops) {
411 parent_route =
412 ospf6_route_lookup(&v->parent->vertex_id, result_table);
413 if (parent_route) {
414 ospf6_route_merge_nexthops(route, parent_route);
415 }
416 }
417
418 if (v->parent)
419 listnode_add_sort(v->parent->child_list, v);
420 route->route_option = v;
421
422 ospf6_route_add(route, result_table);
423 return 0;
424 }
425
426 void ospf6_spf_table_finish(struct ospf6_route_table *result_table)
427 {
428 struct ospf6_route *route, *nroute;
429 struct ospf6_vertex *v;
430 for (route = ospf6_route_head(result_table); route; route = nroute) {
431 nroute = ospf6_route_next(route);
432 v = (struct ospf6_vertex *)route->route_option;
433 ospf6_vertex_delete(v);
434 ospf6_route_remove(route, result_table);
435 }
436 }
437
438 static const char *ospf6_spf_reason_str[] = {
439 "R+", "R-", "N+", "N-", "L+", "L-", "R*", "N*",
440 };
441
442 void ospf6_spf_reason_string(unsigned int reason, char *buf, int size)
443 {
444 unsigned int bit;
445 int len = 0;
446
447 if (!buf)
448 return;
449
450 for (bit = 0; bit < array_size(ospf6_spf_reason_str); bit++) {
451 if ((reason & (1 << bit)) && (len < size)) {
452 len += snprintf((buf + len), (size - len), "%s%s",
453 (len > 0) ? ", " : "",
454 ospf6_spf_reason_str[bit]);
455 }
456 }
457 }
458
459 /* RFC2328 16.1. Calculating the shortest-path tree for an area */
460 /* RFC2740 3.8.1. Calculating the shortest path tree for an area */
461 void ospf6_spf_calculation(uint32_t router_id,
462 struct ospf6_route_table *result_table,
463 struct ospf6_area *oa)
464 {
465 struct vertex_pqueue_head candidate_list;
466 struct ospf6_vertex *root, *v, *w;
467 int size;
468 caddr_t lsdesc;
469 struct ospf6_lsa *lsa;
470 struct in6_addr address;
471
472 ospf6_spf_table_finish(result_table);
473
474 /* Install the calculating router itself as the root of the SPF tree */
475 /* construct root vertex */
476 lsa = ospf6_create_single_router_lsa(oa, oa->lsdb_self, router_id);
477 if (lsa == NULL) {
478 if (IS_OSPF6_DEBUG_SPF(PROCESS))
479 zlog_debug("%s: No router LSA for area %s", __func__,
480 oa->name);
481 return;
482 }
483
484 /* initialize */
485 vertex_pqueue_init(&candidate_list);
486
487 root = ospf6_vertex_create(lsa);
488 root->area = oa;
489 root->cost = 0;
490 root->hops = 0;
491 root->link_id = lsa->header->id;
492 inet_pton(AF_INET6, "::1", &address);
493
494 /* Actually insert root to the candidate-list as the only candidate */
495 vertex_pqueue_add(&candidate_list, root);
496
497 /* Iterate until candidate-list becomes empty */
498 while ((v = vertex_pqueue_pop(&candidate_list))) {
499 /* installing may result in merging or rejecting of the vertex
500 */
501 if (ospf6_spf_install(v, result_table) < 0)
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
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
531 + ROUTER_LSDESC_GET_METRIC(lsdesc);
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,
545 ROUTER_LSDESC_GET_IFID(lsdesc), NULL);
546 else if (w->hops == 1 && v->hops == 0)
547 ospf6_nexthop_calc(w, v, lsdesc);
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(
555 " New candidate: %s hops %d cost %d",
556 w->name, w->hops, w->cost);
557 vertex_pqueue_add(&candidate_list, w);
558 }
559 }
560
561 //vertex_pqueue_fini(&candidate_list);
562
563 ospf6_remove_temp_router_lsa(oa);
564
565 oa->spf_calculation++;
566 }
567
568 static void ospf6_spf_log_database(struct ospf6_area *oa)
569 {
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);
590 }
591
592 static int ospf6_spf_calculation_thread(struct thread *t)
593 {
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
601 ospf6 = (struct ospf6 *)THREAD_ARG(t);
602 ospf6->t_spf_calc = NULL;
603
604 /* execute SPF calculation */
605 monotime(&start);
606 ospf6->ts_spf = start;
607
608 if (ospf6_is_router_abr(ospf6))
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
616 monotime(&oa->ts_spf);
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) {
630 monotime(&ospf6->backbone->ts_spf);
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
645 if (ospf6_is_router_abr(ospf6))
646 ospf6_abr_defaults_to_stub(ospf6);
647
648 monotime(&end);
649 timersub(&end, &start, &runtime);
650
651 ospf6->ts_spf_duration = runtime;
652
653 ospf6_spf_reason_string(ospf6->spf_reason, rbuf, sizeof(rbuf));
654
655 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
656 zlog_debug("SPF runtime: %lld sec %lld usec",
657 (long long)runtime.tv_sec,
658 (long long)runtime.tv_usec);
659
660 zlog_info(
661 "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
662 "Reason: %s\n",
663 areas_processed, (long long)runtime.tv_sec,
664 (long long)runtime.tv_usec, rbuf);
665
666 ospf6->last_spf_reason = ospf6->spf_reason;
667 ospf6_reset_spf_reason(ospf6);
668 return 0;
669 }
670
671 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
672 set timer for SPF calc. */
673 void ospf6_spf_schedule(struct ospf6 *ospf6, unsigned int reason)
674 {
675 unsigned long delay, elapsed, ht;
676
677 /* OSPF instance does not exist. */
678 if (ospf6 == NULL)
679 return;
680
681 ospf6_set_spf_reason(ospf6, reason);
682
683 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) {
684 char rbuf[32];
685 ospf6_spf_reason_string(reason, rbuf, sizeof(rbuf));
686 zlog_debug("SPF: calculation timer scheduled (reason %s)",
687 rbuf);
688 }
689
690 /* SPF calculation timer is already scheduled. */
691 if (ospf6->t_spf_calc) {
692 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
693 zlog_debug(
694 "SPF: calculation timer is already scheduled: %p",
695 (void *)ospf6->t_spf_calc);
696 return;
697 }
698
699 elapsed = monotime_since(&ospf6->ts_spf, NULL) / 1000LL;
700 ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier;
701
702 if (ht > ospf6->spf_max_holdtime)
703 ht = ospf6->spf_max_holdtime;
704
705 /* Get SPF calculation delay time. */
706 if (elapsed < ht) {
707 /* Got an event within the hold time of last SPF. We need to
708 * increase the hold_multiplier, if it's not already at/past
709 * maximum value, and wasn't already increased..
710 */
711 if (ht < ospf6->spf_max_holdtime)
712 ospf6->spf_hold_multiplier++;
713
714 /* always honour the SPF initial delay */
715 if ((ht - elapsed) < ospf6->spf_delay)
716 delay = ospf6->spf_delay;
717 else
718 delay = ht - elapsed;
719 } else {
720 /* Event is past required hold-time of last SPF */
721 delay = ospf6->spf_delay;
722 ospf6->spf_hold_multiplier = 1;
723 }
724
725 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME))
726 zlog_debug("SPF: calculation timer delay = %ld", delay);
727
728 zlog_info("SPF: Scheduled in %ld msec", delay);
729
730 ospf6->t_spf_calc = NULL;
731 thread_add_timer_msec(master, ospf6_spf_calculation_thread, ospf6,
732 delay, &ospf6->t_spf_calc);
733 }
734
735 void ospf6_spf_display_subtree(struct vty *vty, const char *prefix, int rest,
736 struct ospf6_vertex *v)
737 {
738 struct listnode *node, *nnode;
739 struct ospf6_vertex *c;
740 char *next_prefix;
741 int len;
742 int restnum;
743
744 /* "prefix" is the space prefix of the display line */
745 vty_out(vty, "%s+-%s [%d]\n", prefix, v->name, v->cost);
746
747 len = strlen(prefix) + 4;
748 next_prefix = (char *)malloc(len);
749 if (next_prefix == NULL) {
750 vty_out(vty, "malloc failed\n");
751 return;
752 }
753 snprintf(next_prefix, len, "%s%s", prefix, (rest ? "| " : " "));
754
755 restnum = listcount(v->child_list);
756 for (ALL_LIST_ELEMENTS(v->child_list, node, nnode, c)) {
757 restnum--;
758 ospf6_spf_display_subtree(vty, next_prefix, restnum, c);
759 }
760
761 free(next_prefix);
762 }
763
764 DEFUN (debug_ospf6_spf_process,
765 debug_ospf6_spf_process_cmd,
766 "debug ospf6 spf process",
767 DEBUG_STR
768 OSPF6_STR
769 "Debug SPF Calculation\n"
770 "Debug Detailed SPF Process\n"
771 )
772 {
773 unsigned char level = 0;
774 level = OSPF6_DEBUG_SPF_PROCESS;
775 OSPF6_DEBUG_SPF_ON(level);
776 return CMD_SUCCESS;
777 }
778
779 DEFUN (debug_ospf6_spf_time,
780 debug_ospf6_spf_time_cmd,
781 "debug ospf6 spf time",
782 DEBUG_STR
783 OSPF6_STR
784 "Debug SPF Calculation\n"
785 "Measure time taken by SPF Calculation\n"
786 )
787 {
788 unsigned char level = 0;
789 level = OSPF6_DEBUG_SPF_TIME;
790 OSPF6_DEBUG_SPF_ON(level);
791 return CMD_SUCCESS;
792 }
793
794 DEFUN (debug_ospf6_spf_database,
795 debug_ospf6_spf_database_cmd,
796 "debug ospf6 spf database",
797 DEBUG_STR
798 OSPF6_STR
799 "Debug SPF Calculation\n"
800 "Log number of LSAs at SPF Calculation time\n"
801 )
802 {
803 unsigned char level = 0;
804 level = OSPF6_DEBUG_SPF_DATABASE;
805 OSPF6_DEBUG_SPF_ON(level);
806 return CMD_SUCCESS;
807 }
808
809 DEFUN (no_debug_ospf6_spf_process,
810 no_debug_ospf6_spf_process_cmd,
811 "no debug ospf6 spf process",
812 NO_STR
813 DEBUG_STR
814 OSPF6_STR
815 "Quit Debugging SPF Calculation\n"
816 "Quit Debugging Detailed SPF Process\n"
817 )
818 {
819 unsigned char level = 0;
820 level = OSPF6_DEBUG_SPF_PROCESS;
821 OSPF6_DEBUG_SPF_OFF(level);
822 return CMD_SUCCESS;
823 }
824
825 DEFUN (no_debug_ospf6_spf_time,
826 no_debug_ospf6_spf_time_cmd,
827 "no debug ospf6 spf time",
828 NO_STR
829 DEBUG_STR
830 OSPF6_STR
831 "Quit Debugging SPF Calculation\n"
832 "Quit Measuring time taken by SPF Calculation\n"
833 )
834 {
835 unsigned char level = 0;
836 level = OSPF6_DEBUG_SPF_TIME;
837 OSPF6_DEBUG_SPF_OFF(level);
838 return CMD_SUCCESS;
839 }
840
841 DEFUN (no_debug_ospf6_spf_database,
842 no_debug_ospf6_spf_database_cmd,
843 "no debug ospf6 spf database",
844 NO_STR
845 DEBUG_STR
846 OSPF6_STR
847 "Debug SPF Calculation\n"
848 "Quit Logging number of LSAs at SPF Calculation time\n"
849 )
850 {
851 unsigned char level = 0;
852 level = OSPF6_DEBUG_SPF_DATABASE;
853 OSPF6_DEBUG_SPF_OFF(level);
854 return CMD_SUCCESS;
855 }
856
857 static int ospf6_timers_spf_set(struct vty *vty, unsigned int delay,
858 unsigned int hold, unsigned int max)
859 {
860 VTY_DECLVAR_CONTEXT(ospf6, ospf);
861
862 ospf->spf_delay = delay;
863 ospf->spf_holdtime = hold;
864 ospf->spf_max_holdtime = max;
865
866 return CMD_SUCCESS;
867 }
868
869 DEFUN (ospf6_timers_throttle_spf,
870 ospf6_timers_throttle_spf_cmd,
871 "timers throttle spf (0-600000) (0-600000) (0-600000)",
872 "Adjust routing timers\n"
873 "Throttling adaptive timer\n"
874 "OSPF6 SPF timers\n"
875 "Delay (msec) from first change received till SPF calculation\n"
876 "Initial hold time (msec) between consecutive SPF calculations\n"
877 "Maximum hold time (msec)\n")
878 {
879 int idx_number = 3;
880 int idx_number_2 = 4;
881 int idx_number_3 = 5;
882 unsigned int delay, hold, max;
883
884 delay = strtoul(argv[idx_number]->arg, NULL, 10);
885 hold = strtoul(argv[idx_number_2]->arg, NULL, 10);
886 max = strtoul(argv[idx_number_3]->arg, NULL, 10);
887
888 return ospf6_timers_spf_set(vty, delay, hold, max);
889 }
890
891 DEFUN (no_ospf6_timers_throttle_spf,
892 no_ospf6_timers_throttle_spf_cmd,
893 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
894 NO_STR
895 "Adjust routing timers\n"
896 "Throttling adaptive timer\n"
897 "OSPF6 SPF timers\n"
898 "Delay (msec) from first change received till SPF calculation\n"
899 "Initial hold time (msec) between consecutive SPF calculations\n"
900 "Maximum hold time (msec)\n")
901 {
902 return ospf6_timers_spf_set(vty, OSPF_SPF_DELAY_DEFAULT,
903 OSPF_SPF_HOLDTIME_DEFAULT,
904 OSPF_SPF_MAX_HOLDTIME_DEFAULT);
905 }
906
907
908 int config_write_ospf6_debug_spf(struct vty *vty)
909 {
910 if (IS_OSPF6_DEBUG_SPF(PROCESS))
911 vty_out(vty, "debug ospf6 spf process\n");
912 if (IS_OSPF6_DEBUG_SPF(TIME))
913 vty_out(vty, "debug ospf6 spf time\n");
914 if (IS_OSPF6_DEBUG_SPF(DATABASE))
915 vty_out(vty, "debug ospf6 spf database\n");
916 return 0;
917 }
918
919 void ospf6_spf_config_write(struct vty *vty)
920 {
921
922 if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT
923 || ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT
924 || ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT)
925 vty_out(vty, " timers throttle spf %d %d %d\n",
926 ospf6->spf_delay, ospf6->spf_holdtime,
927 ospf6->spf_max_holdtime);
928 }
929
930 void install_element_ospf6_debug_spf(void)
931 {
932 install_element(ENABLE_NODE, &debug_ospf6_spf_process_cmd);
933 install_element(ENABLE_NODE, &debug_ospf6_spf_time_cmd);
934 install_element(ENABLE_NODE, &debug_ospf6_spf_database_cmd);
935 install_element(ENABLE_NODE, &no_debug_ospf6_spf_process_cmd);
936 install_element(ENABLE_NODE, &no_debug_ospf6_spf_time_cmd);
937 install_element(ENABLE_NODE, &no_debug_ospf6_spf_database_cmd);
938 install_element(CONFIG_NODE, &debug_ospf6_spf_process_cmd);
939 install_element(CONFIG_NODE, &debug_ospf6_spf_time_cmd);
940 install_element(CONFIG_NODE, &debug_ospf6_spf_database_cmd);
941 install_element(CONFIG_NODE, &no_debug_ospf6_spf_process_cmd);
942 install_element(CONFIG_NODE, &no_debug_ospf6_spf_time_cmd);
943 install_element(CONFIG_NODE, &no_debug_ospf6_spf_database_cmd);
944 }
945
946 void ospf6_spf_init(void)
947 {
948 install_element(OSPF6_NODE, &ospf6_timers_throttle_spf_cmd);
949 install_element(OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd);
950 }
951
952 /* Create Aggregated Large Router-LSA from multiple Link-State IDs
953 * RFC 5340 A 4.3:
954 * When more than one router-LSA is received from a single router,
955 * the links are processed as if concatenated into a single LSA.*/
956 struct ospf6_lsa *ospf6_create_single_router_lsa(struct ospf6_area *area,
957 struct ospf6_lsdb *lsdb,
958 uint32_t adv_router)
959 {
960 struct ospf6_lsa *lsa = NULL;
961 struct ospf6_lsa *rtr_lsa = NULL;
962 struct ospf6_lsa_header *lsa_header = NULL;
963 uint8_t *new_header = NULL;
964 const struct route_node *end = NULL;
965 uint16_t lsa_length, total_lsa_length = 0, num_lsa = 0;
966 uint16_t type = 0;
967 char ifbuf[16];
968 uint32_t interface_id;
969 caddr_t lsd;
970
971 lsa_length = sizeof(struct ospf6_lsa_header)
972 + sizeof(struct ospf6_router_lsa);
973 total_lsa_length = lsa_length;
974 type = htons(OSPF6_LSTYPE_ROUTER);
975
976 /* First check Aggregated LSA formed earlier in Cache */
977 lsa = ospf6_lsdb_lookup(type, htonl(0), adv_router,
978 area->temp_router_lsa_lsdb);
979 if (lsa)
980 return lsa;
981
982 inet_ntop(AF_INET, &adv_router, ifbuf, sizeof(ifbuf));
983
984 /* Determine total LSA length from all link state ids */
985 end = ospf6_lsdb_head(lsdb, 2, type, adv_router, &rtr_lsa);
986 while (rtr_lsa) {
987 lsa = rtr_lsa;
988 if (OSPF6_LSA_IS_MAXAGE(rtr_lsa)) {
989 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
990 continue;
991 }
992 lsa_header = (struct ospf6_lsa_header *)rtr_lsa->header;
993 total_lsa_length += (ntohs(lsa_header->length) - lsa_length);
994 num_lsa++;
995 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
996 }
997 if (IS_OSPF6_DEBUG_SPF(PROCESS))
998 zlog_debug("%s: adv_router %s num_lsa %u to convert.",
999 __PRETTY_FUNCTION__, ifbuf, num_lsa);
1000 if (num_lsa == 1)
1001 return lsa;
1002
1003 if (num_lsa == 0) {
1004 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1005 zlog_debug("%s: adv_router %s not found in LSDB.",
1006 __PRETTY_FUNCTION__, ifbuf);
1007 return NULL;
1008 }
1009
1010 /* Allocate memory for this LSA */
1011 new_header = XMALLOC(MTYPE_OSPF6_LSA_HEADER, total_lsa_length);
1012
1013 /* LSA information structure */
1014 lsa = XCALLOC(MTYPE_OSPF6_LSA, sizeof(struct ospf6_lsa));
1015
1016 lsa->header = (struct ospf6_lsa_header *)new_header;
1017
1018 lsa->lsdb = area->temp_router_lsa_lsdb;
1019
1020 /* Fill Larger LSA Payload */
1021 end = ospf6_lsdb_head(lsdb, 2, type, adv_router, &rtr_lsa);
1022
1023 /*
1024 * We assume at this point in time that rtr_lsa is
1025 * a valid pointer.
1026 */
1027 assert(rtr_lsa);
1028 if (!OSPF6_LSA_IS_MAXAGE(rtr_lsa)) {
1029 /* Append first Link State ID LSA */
1030 lsa_header = (struct ospf6_lsa_header *)rtr_lsa->header;
1031 memcpy(new_header, lsa_header, ntohs(lsa_header->length));
1032 /* Assign new lsa length as aggregated length. */
1033 ((struct ospf6_lsa_header *)new_header)->length =
1034 htons(total_lsa_length);
1035 new_header += ntohs(lsa_header->length);
1036 num_lsa--;
1037 }
1038
1039 /* Print LSA Name */
1040 ospf6_lsa_printbuf(lsa, lsa->name, sizeof(lsa->name));
1041
1042 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1043 while (rtr_lsa) {
1044 if (OSPF6_LSA_IS_MAXAGE(rtr_lsa)) {
1045 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1046 continue;
1047 }
1048
1049 if (IS_OSPF6_DEBUG_SPF(PROCESS)) {
1050 lsd = OSPF6_LSA_HEADER_END(rtr_lsa->header) + 4;
1051 interface_id = ROUTER_LSDESC_GET_IFID(lsd);
1052 inet_ntop(AF_INET, &interface_id, ifbuf, sizeof(ifbuf));
1053 zlog_debug(
1054 "%s: Next Router LSA %s to aggreat with len %u interface_id %s",
1055 __PRETTY_FUNCTION__, rtr_lsa->name,
1056 ntohs(lsa_header->length), ifbuf);
1057 }
1058
1059 /* Append Next Link State ID LSA */
1060 lsa_header = (struct ospf6_lsa_header *)rtr_lsa->header;
1061 memcpy(new_header, (OSPF6_LSA_HEADER_END(rtr_lsa->header) + 4),
1062 (ntohs(lsa_header->length) - lsa_length));
1063 new_header += (ntohs(lsa_header->length) - lsa_length);
1064 num_lsa--;
1065
1066 rtr_lsa = ospf6_lsdb_next(end, rtr_lsa);
1067 }
1068
1069 /* Calculate birth of this lsa */
1070 ospf6_lsa_age_set(lsa);
1071
1072 /* Store Aggregated LSA into area temp lsdb */
1073 ospf6_lsdb_add(lsa, area->temp_router_lsa_lsdb);
1074
1075 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1076 zlog_debug("%s: LSA %s id %u type 0%x len %u num_lsa %u",
1077 __PRETTY_FUNCTION__, lsa->name,
1078 ntohl(lsa->header->id), ntohs(lsa->header->type),
1079 ntohs(lsa->header->length), num_lsa);
1080
1081 return lsa;
1082 }
1083
1084 void ospf6_remove_temp_router_lsa(struct ospf6_area *area)
1085 {
1086 struct ospf6_lsa *lsa = NULL;
1087
1088 for (ALL_LSDB(area->temp_router_lsa_lsdb, lsa)) {
1089 if (IS_OSPF6_DEBUG_SPF(PROCESS))
1090 zlog_debug(
1091 "%s Remove LSA %s lsa->lock %u lsdb count %u",
1092 __PRETTY_FUNCTION__, lsa->name, lsa->lock,
1093 area->temp_router_lsa_lsdb->count);
1094 ospf6_lsdb_remove(lsa, area->temp_router_lsa_lsdb);
1095 }
1096 }
FRRouting mirror