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