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