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