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
17 * along with GNU Zebra; see the file COPYING. If not, write to the
18 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 * Boston, MA 02111-1307, USA.
20 */
21
22 /* Shortest Path First calculation for OSPFv3 */
23
24 #include <zebra.h>
25
26 #include "log.h"
27 #include "memory.h"
28 #include "command.h"
29 #include "vty.h"
30 #include "prefix.h"
31 #include "pqueue.h"
32 #include "linklist.h"
33 #include "thread.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_spf.h"
40 #include "ospf6_intra.h"
41 #include "ospf6_interface.h"
42 #include "ospf6d.h"
43 #include "ospf6_abr.h"
44
45 unsigned char conf_debug_ospf6_spf = 0;
46
47 static int
ospf6_vertex_cmp(void * a,void * b)48 ospf6_vertex_cmp (void *a, void *b)
49 {
50 struct ospf6_vertex *va = (struct ospf6_vertex *) a;
51 struct ospf6_vertex *vb = (struct ospf6_vertex *) b;
52
53 /* ascending order */
54 if (va->cost != vb->cost)
55 return (va->cost - vb->cost);
56 return (va->hops - vb->hops);
57 }
58
59 static int
ospf6_vertex_id_cmp(void * a,void * b)60 ospf6_vertex_id_cmp (void *a, void *b)
61 {
62 struct ospf6_vertex *va = (struct ospf6_vertex *) a;
63 struct ospf6_vertex *vb = (struct ospf6_vertex *) b;
64 int ret = 0;
65
66 ret = ntohl (ospf6_linkstate_prefix_adv_router (&va->vertex_id)) -
67 ntohl (ospf6_linkstate_prefix_adv_router (&vb->vertex_id));
68 if (ret)
69 return ret;
70
71 ret = ntohl (ospf6_linkstate_prefix_id (&va->vertex_id)) -
72 ntohl (ospf6_linkstate_prefix_id (&vb->vertex_id));
73 return ret;
74 }
75
76 static struct ospf6_vertex *
ospf6_vertex_create(struct ospf6_lsa * lsa)77 ospf6_vertex_create (struct ospf6_lsa *lsa)
78 {
79 struct ospf6_vertex *v;
80 int i;
81
82 v = (struct ospf6_vertex *)
83 XMALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_vertex));
84
85 /* type */
86 if (ntohs (lsa->header->type) == OSPF6_LSTYPE_ROUTER)
87 v->type = OSPF6_VERTEX_TYPE_ROUTER;
88 else if (ntohs (lsa->header->type) == OSPF6_LSTYPE_NETWORK)
89 v->type = OSPF6_VERTEX_TYPE_NETWORK;
90 else
91 assert (0);
92
93 /* vertex_id */
94 ospf6_linkstate_prefix (lsa->header->adv_router, lsa->header->id,
95 &v->vertex_id);
96
97 /* name */
98 ospf6_linkstate_prefix2str (&v->vertex_id, v->name, sizeof (v->name));
99
100 /* Associated LSA */
101 v->lsa = lsa;
102
103 /* capability bits + options */
104 v->capability = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header));
105 v->options[0] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 1);
106 v->options[1] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 2);
107 v->options[2] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 3);
108
109 for (i = 0; i < OSPF6_MULTI_PATH_LIMIT; i++)
110 ospf6_nexthop_clear (&v->nexthop[i]);
111
112 v->parent = NULL;
113 v->child_list = list_new ();
114 v->child_list->cmp = ospf6_vertex_id_cmp;
115
116 return v;
117 }
118
119 static void
ospf6_vertex_delete(struct ospf6_vertex * v)120 ospf6_vertex_delete (struct ospf6_vertex *v)
121 {
122 list_delete (v->child_list);
123 XFREE (MTYPE_OSPF6_VERTEX, v);
124 }
125
126 static struct ospf6_lsa *
ospf6_lsdesc_lsa(caddr_t lsdesc,struct ospf6_vertex * v)127 ospf6_lsdesc_lsa (caddr_t lsdesc, struct ospf6_vertex *v)
128 {
129 struct ospf6_lsa *lsa;
130 u_int16_t type = 0;
131 u_int32_t id = 0, adv_router = 0;
132
133 if (VERTEX_IS_TYPE (NETWORK, v))
134 {
135 type = htons (OSPF6_LSTYPE_ROUTER);
136 id = htonl (0);
137 adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc);
138 }
139 else
140 {
141 if (ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc))
142 {
143 type = htons (OSPF6_LSTYPE_ROUTER);
144 id = htonl (0);
145 adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc);
146 }
147 else if (ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, lsdesc))
148 {
149 type = htons (OSPF6_LSTYPE_NETWORK);
150 id = htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc));
151 adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc);
152 }
153 }
154
155 lsa = ospf6_lsdb_lookup (type, id, adv_router, v->area->lsdb);
156
157 if (IS_OSPF6_DEBUG_SPF (PROCESS))
158 {
159 char ibuf[16], abuf[16];
160 inet_ntop (AF_INET, &id, ibuf, sizeof (ibuf));
161 inet_ntop (AF_INET, &adv_router, abuf, sizeof (abuf));
162 if (lsa)
163 zlog_debug (" Link to: %s", lsa->name);
164 else
165 zlog_debug (" Link to: [%s Id:%s Adv:%s] No LSA",
166 ospf6_lstype_name (type), ibuf, abuf);
167 }
168
169 return lsa;
170 }
171
172 static char *
ospf6_lsdesc_backlink(struct ospf6_lsa * lsa,caddr_t lsdesc,struct ospf6_vertex * v)173 ospf6_lsdesc_backlink (struct ospf6_lsa *lsa,
174 caddr_t lsdesc, struct ospf6_vertex *v)
175 {
176 caddr_t backlink, found = NULL;
177 int size;
178
179 size = (OSPF6_LSA_IS_TYPE (ROUTER, lsa) ?
180 sizeof (struct ospf6_router_lsdesc) :
181 sizeof (struct ospf6_network_lsdesc));
182 for (backlink = OSPF6_LSA_HEADER_END (lsa->header) + 4;
183 backlink + size <= OSPF6_LSA_END (lsa->header); backlink += size)
184 {
185 assert (! (OSPF6_LSA_IS_TYPE (NETWORK, lsa) &&
186 VERTEX_IS_TYPE (NETWORK, v)));
187
188 if (OSPF6_LSA_IS_TYPE (NETWORK, lsa) &&
189 NETWORK_LSDESC_GET_NBR_ROUTERID (backlink)
190 == v->lsa->header->adv_router)
191 found = backlink;
192 else if (VERTEX_IS_TYPE (NETWORK, v) &&
193 ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, backlink) &&
194 ROUTER_LSDESC_GET_NBR_ROUTERID (backlink)
195 == v->lsa->header->adv_router &&
196 ROUTER_LSDESC_GET_NBR_IFID (backlink)
197 == ntohl (v->lsa->header->id))
198 found = backlink;
199 else
200 {
201 if (! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, backlink) ||
202 ! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc))
203 continue;
204 if (ROUTER_LSDESC_GET_NBR_IFID (backlink) !=
205 ROUTER_LSDESC_GET_IFID (lsdesc) ||
206 ROUTER_LSDESC_GET_NBR_IFID (lsdesc) !=
207 ROUTER_LSDESC_GET_IFID (backlink))
208 continue;
209 if (ROUTER_LSDESC_GET_NBR_ROUTERID (backlink) !=
210 v->lsa->header->adv_router ||
211 ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc) !=
212 lsa->header->adv_router)
213 continue;
214 found = backlink;
215 }
216 }
217
218 if (IS_OSPF6_DEBUG_SPF (PROCESS))
219 zlog_debug (" Backlink %s", (found ? "OK" : "FAIL"));
220
221 return found;
222 }
223
224 static void
ospf6_nexthop_calc(struct ospf6_vertex * w,struct ospf6_vertex * v,caddr_t lsdesc)225 ospf6_nexthop_calc (struct ospf6_vertex *w, struct ospf6_vertex *v,
226 caddr_t lsdesc)
227 {
228 int i;
229 ifindex_t ifindex;
230 struct ospf6_interface *oi;
231 u_int16_t type;
232 u_int32_t adv_router;
233 struct ospf6_lsa *lsa;
234 struct ospf6_link_lsa *link_lsa;
235 char buf[64];
236
237 assert (VERTEX_IS_TYPE (ROUTER, w));
238 ifindex = (VERTEX_IS_TYPE (NETWORK, v) ? v->nexthop[0].ifindex :
239 /* v is the local router & the interface_id is a local ifindex */
240 (ifindex_t) ROUTER_LSDESC_GET_IFID (lsdesc));
241 assert (ifindex >= 0);
242
243 oi = ospf6_interface_lookup_by_ifindex (ifindex);
244 if (oi == NULL)
245 {
246 if (IS_OSPF6_DEBUG_SPF (PROCESS))
247 zlog_debug ("Can't find interface in SPF: ifindex %d", ifindex);
248 return;
249 }
250
251 type = htons (OSPF6_LSTYPE_LINK);
252 adv_router = (VERTEX_IS_TYPE (NETWORK, v) ?
253 NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc) :
254 ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc));
255
256 i = 0;
257 for (lsa = ospf6_lsdb_type_router_head (type, adv_router, oi->lsdb); lsa;
258 lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa))
259 {
260 if (VERTEX_IS_TYPE (ROUTER, v) &&
261 htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc)) != lsa->header->id)
262 continue;
263
264 link_lsa = (struct ospf6_link_lsa *) OSPF6_LSA_HEADER_END (lsa->header);
265 if (IS_OSPF6_DEBUG_SPF (PROCESS))
266 {
267 inet_ntop (AF_INET6, &link_lsa->linklocal_addr, buf, sizeof (buf));
268 zlog_debug (" nexthop %s from %s", buf, lsa->name);
269 }
270
271 if (i < OSPF6_MULTI_PATH_LIMIT)
272 {
273 memcpy (&w->nexthop[i].address, &link_lsa->linklocal_addr,
274 sizeof (struct in6_addr));
275 w->nexthop[i].ifindex = ifindex;
276 i++;
277 }
278 }
279
280 if (i == 0 && IS_OSPF6_DEBUG_SPF (PROCESS))
281 zlog_debug ("No nexthop for %s found", w->name);
282 }
283
284 static int
ospf6_spf_install(struct ospf6_vertex * v,struct ospf6_route_table * result_table)285 ospf6_spf_install (struct ospf6_vertex *v,
286 struct ospf6_route_table *result_table)
287 {
288 struct ospf6_route *route;
289 int i, j;
290 struct ospf6_vertex *prev;
291
292 if (IS_OSPF6_DEBUG_SPF (PROCESS))
293 zlog_debug ("SPF install %s hops %d cost %d",
294 v->name, v->hops, v->cost);
295
296 route = ospf6_route_lookup (&v->vertex_id, result_table);
297 if (route && route->path.cost < v->cost)
298 {
299 if (IS_OSPF6_DEBUG_SPF (PROCESS))
300 zlog_debug (" already installed with lower cost (%d), ignore",
301 route->path.cost);
302 ospf6_vertex_delete (v);
303 return -1;
304 }
305 else if (route && route->path.cost == v->cost)
306 {
307 if (IS_OSPF6_DEBUG_SPF (PROCESS))
308 zlog_debug (" another path found, merge");
309
310 for (i = 0; i < OSPF6_MULTI_PATH_LIMIT &&
311 ospf6_nexthop_is_set (&v->nexthop[i]); i++)
312 {
313 for (j = 0; j < OSPF6_MULTI_PATH_LIMIT; j++)
314 {
315 if (ospf6_nexthop_is_set (&route->nexthop[j]))
316 {
317 if (ospf6_nexthop_is_same (&route->nexthop[j],
318 &v->nexthop[i]))
319 break;
320 else
321 continue;
322 }
323 ospf6_nexthop_copy (&route->nexthop[j], &v->nexthop[i]);
324 break;
325 }
326 }
327
328 prev = (struct ospf6_vertex *) route->route_option;
329 assert (prev->hops <= v->hops);
330 ospf6_vertex_delete (v);
331
332 return -1;
333 }
334
335 /* There should be no case where candidate being installed (variable
336 "v") is closer than the one in the SPF tree (variable "route").
337 In the case something has gone wrong with the behavior of
338 Priority-Queue. */
339
340 /* the case where the route exists already is handled and returned
341 up to here. */
342 assert (route == NULL);
343
344 route = ospf6_route_create ();
345 memcpy (&route->prefix, &v->vertex_id, sizeof (struct prefix));
346 route->type = OSPF6_DEST_TYPE_LINKSTATE;
347 route->path.type = OSPF6_PATH_TYPE_INTRA;
348 route->path.origin.type = v->lsa->header->type;
349 route->path.origin.id = v->lsa->header->id;
350 route->path.origin.adv_router = v->lsa->header->adv_router;
351 route->path.metric_type = 1;
352 route->path.cost = v->cost;
353 route->path.cost_e2 = v->hops;
354 route->path.router_bits = v->capability;
355 route->path.options[0] = v->options[0];
356 route->path.options[1] = v->options[1];
357 route->path.options[2] = v->options[2];
358
359 for (i = 0; i < OSPF6_MULTI_PATH_LIMIT &&
360 ospf6_nexthop_is_set (&v->nexthop[i]); i++)
361 ospf6_nexthop_copy (&route->nexthop[i], &v->nexthop[i]);
362
363 if (v->parent)
364 listnode_add_sort (v->parent->child_list, v);
365 route->route_option = v;
366
367 ospf6_route_add (route, result_table);
368 return 0;
369 }
370
371 void
ospf6_spf_table_finish(struct ospf6_route_table * result_table)372 ospf6_spf_table_finish (struct ospf6_route_table *result_table)
373 {
374 struct ospf6_route *route, *nroute;
375 struct ospf6_vertex *v;
376 for (route = ospf6_route_head (result_table); route;
377 route = nroute)
378 {
379 nroute = ospf6_route_next (route);
380 v = (struct ospf6_vertex *) route->route_option;
381 ospf6_vertex_delete (v);
382 ospf6_route_remove (route, result_table);
383 }
384 }
385
386 static const char *ospf6_spf_reason_str[] =
387 {
388 "R+",
389 "R-",
390 "N+",
391 "N-",
392 "L+",
393 "L-",
394 "R*",
395 "N*",
396 };
397
ospf6_spf_reason_string(unsigned int reason,char * buf,int size)398 void ospf6_spf_reason_string (unsigned int reason, char *buf, int size)
399 {
400 size_t bit;
401 int len = 0;
402
403 if (!buf)
404 return;
405
406 for (bit = 0; bit < array_size(ospf6_spf_reason_str); bit++)
407 {
408 if ((reason & (1 << bit)) && (len < size))
409 {
410 len += snprintf((buf + len), (size - len), "%s%s",
411 (len > 0) ? ", " : "", ospf6_spf_reason_str[bit]);
412 }
413 }
414 }
415
416 /* RFC2328 16.1. Calculating the shortest-path tree for an area */
417 /* RFC2740 3.8.1. Calculating the shortest path tree for an area */
418 void
ospf6_spf_calculation(u_int32_t router_id,struct ospf6_route_table * result_table,struct ospf6_area * oa)419 ospf6_spf_calculation (u_int32_t router_id,
420 struct ospf6_route_table *result_table,
421 struct ospf6_area *oa)
422 {
423 struct pqueue *candidate_list;
424 struct ospf6_vertex *root, *v, *w;
425 int i;
426 int size;
427 caddr_t lsdesc;
428 struct ospf6_lsa *lsa;
429
430 ospf6_spf_table_finish (result_table);
431
432 /* Install the calculating router itself as the root of the SPF tree */
433 /* construct root vertex */
434 lsa = ospf6_lsdb_lookup (htons (OSPF6_LSTYPE_ROUTER), htonl (0),
435 router_id, oa->lsdb);
436 if (lsa == NULL)
437 return;
438
439 /* initialize */
440 candidate_list = pqueue_create ();
441 candidate_list->cmp = ospf6_vertex_cmp;
442
443 root = ospf6_vertex_create (lsa);
444 root->area = oa;
445 root->cost = 0;
446 root->hops = 0;
447 root->nexthop[0].ifindex = 0; /* loopbak I/F is better ... */
448 inet_pton (AF_INET6, "::1", &root->nexthop[0].address);
449
450 /* Actually insert root to the candidate-list as the only candidate */
451 pqueue_enqueue (root, candidate_list);
452
453 /* Iterate until candidate-list becomes empty */
454 while (candidate_list->size)
455 {
456 /* get closest candidate from priority queue */
457 v = pqueue_dequeue (candidate_list);
458
459 /* installing may result in merging or rejecting of the vertex */
460 if (ospf6_spf_install (v, result_table) < 0)
461 continue;
462
463 /* Skip overloaded routers */
464 if ((OSPF6_LSA_IS_TYPE (ROUTER, v->lsa) &&
465 ospf6_router_is_stub_router (v->lsa)))
466 continue;
467
468 /* For each LS description in the just-added vertex V's LSA */
469 size = (VERTEX_IS_TYPE (ROUTER, v) ?
470 sizeof (struct ospf6_router_lsdesc) :
471 sizeof (struct ospf6_network_lsdesc));
472 for (lsdesc = OSPF6_LSA_HEADER_END (v->lsa->header) + 4;
473 lsdesc + size <= OSPF6_LSA_END (v->lsa->header); lsdesc += size)
474 {
475 lsa = ospf6_lsdesc_lsa (lsdesc, v);
476 if (lsa == NULL)
477 continue;
478
479 if (! ospf6_lsdesc_backlink (lsa, lsdesc, v))
480 continue;
481
482 w = ospf6_vertex_create (lsa);
483 w->area = oa;
484 w->parent = v;
485 if (VERTEX_IS_TYPE (ROUTER, v))
486 {
487 w->cost = v->cost + ROUTER_LSDESC_GET_METRIC (lsdesc);
488 w->hops = v->hops + (VERTEX_IS_TYPE (NETWORK, w) ? 0 : 1);
489 }
490 else /* NETWORK */
491 {
492 w->cost = v->cost;
493 w->hops = v->hops + 1;
494 }
495
496 /* nexthop calculation */
497 if (w->hops == 0)
498 w->nexthop[0].ifindex = ROUTER_LSDESC_GET_IFID (lsdesc);
499 else if (w->hops == 1 && v->hops == 0)
500 ospf6_nexthop_calc (w, v, lsdesc);
501 else
502 {
503 for (i = 0; i < OSPF6_MULTI_PATH_LIMIT &&
504 ospf6_nexthop_is_set (&v->nexthop[i]); i++)
505 ospf6_nexthop_copy (&w->nexthop[i], &v->nexthop[i]);
506 }
507
508 /* add new candidate to the candidate_list */
509 if (IS_OSPF6_DEBUG_SPF (PROCESS))
510 zlog_debug (" New candidate: %s hops %d cost %d",
511 w->name, w->hops, w->cost);
512 pqueue_enqueue (w, candidate_list);
513 }
514 }
515
516 pqueue_delete (candidate_list);
517
518 oa->spf_calculation++;
519 }
520
521 static void
ospf6_spf_log_database(struct ospf6_area * oa)522 ospf6_spf_log_database (struct ospf6_area *oa)
523 {
524 char *p, *end, buffer[256];
525 struct listnode *node;
526 struct ospf6_interface *oi;
527
528 p = buffer;
529 end = buffer + sizeof (buffer);
530
531 snprintf (p, end - p, "SPF on DB (#LSAs):");
532 p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
533 snprintf (p, end - p, " Area %s: %d", oa->name, oa->lsdb->count);
534 p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
535
536 for (ALL_LIST_ELEMENTS_RO (oa->if_list, node, oi))
537 {
538 snprintf (p, end - p, " I/F %s: %d",
539 oi->interface->name, oi->lsdb->count);
540 p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
541 }
542
543 zlog_debug ("%s", buffer);
544 }
545
546 static int
ospf6_spf_calculation_thread(struct thread * t)547 ospf6_spf_calculation_thread (struct thread *t)
548 {
549 struct ospf6_area *oa;
550 struct ospf6 *ospf6;
551 struct timeval start, end, runtime;
552 struct listnode *node;
553 struct ospf6_route *route;
554 int areas_processed = 0;
555 char rbuf[32];
556
557 ospf6 = (struct ospf6 *)THREAD_ARG (t);
558 ospf6->t_spf_calc = NULL;
559
560 /* execute SPF calculation */
561 quagga_gettime (QUAGGA_CLK_MONOTONIC, &start);
562
563 for (ALL_LIST_ELEMENTS_RO(ospf6->area_list, node, oa))
564 {
565
566 if (oa == ospf6->backbone)
567 continue;
568
569 if (IS_OSPF6_DEBUG_SPF (PROCESS))
570 zlog_debug ("SPF calculation for Area %s", oa->name);
571 if (IS_OSPF6_DEBUG_SPF (DATABASE))
572 ospf6_spf_log_database (oa);
573
574 ospf6_spf_calculation (ospf6->router_id, oa->spf_table, oa);
575 ospf6_intra_route_calculation (oa);
576 ospf6_intra_brouter_calculation (oa);
577
578 areas_processed++;
579 }
580
581 if (ospf6->backbone)
582 {
583 if (IS_OSPF6_DEBUG_SPF (PROCESS))
584 zlog_debug ("SPF calculation for Backbone area %s",
585 ospf6->backbone->name);
586 if (IS_OSPF6_DEBUG_SPF (DATABASE))
587 ospf6_spf_log_database(ospf6->backbone);
588
589 ospf6_spf_calculation(ospf6->router_id, ospf6->backbone->spf_table,
590 ospf6->backbone);
591 ospf6_intra_route_calculation(ospf6->backbone);
592 ospf6_intra_brouter_calculation(ospf6->backbone);
593 areas_processed++;
594 }
595
596 /* Redo summaries if required */
597 for (route = ospf6_route_head (ospf6->route_table); route;
598 route = ospf6_route_next (route))
599 ospf6_abr_originate_summary(route);
600
601 quagga_gettime (QUAGGA_CLK_MONOTONIC, &end);
602 timersub (&end, &start, &runtime);
603
604 ospf6->ts_spf_duration = runtime;
605
606 ospf6_spf_reason_string(ospf6->spf_reason, rbuf, sizeof(rbuf));
607
608 if (IS_OSPF6_DEBUG_SPF (PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
609 zlog_debug ("SPF runtime: %lld sec %lld usec",
610 (long long)runtime.tv_sec, (long long)runtime.tv_usec);
611
612 zlog_info("SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
613 "Reason: %s\n", areas_processed,
614 (long long)runtime.tv_sec, (long long)runtime.tv_usec,
615 rbuf);
616 ospf6->last_spf_reason = ospf6->spf_reason;
617 ospf6_reset_spf_reason(ospf6);
618 return 0;
619 }
620
621 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
622 set timer for SPF calc. */
623 void
ospf6_spf_schedule(struct ospf6 * ospf6,unsigned int reason)624 ospf6_spf_schedule (struct ospf6 *ospf6, unsigned int reason)
625 {
626 unsigned long delay, elapsed, ht;
627 struct timeval now, result;
628
629 ospf6_set_spf_reason(ospf6, reason);
630
631 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
632 {
633 char rbuf[32];
634 ospf6_spf_reason_string(reason, rbuf, sizeof(rbuf));
635 zlog_debug ("SPF: calculation timer scheduled (reason %s)", rbuf);
636 }
637
638 /* OSPF instance does not exist. */
639 if (ospf6 == NULL)
640 return;
641
642 /* SPF calculation timer is already scheduled. */
643 if (ospf6->t_spf_calc)
644 {
645 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
646 zlog_debug ("SPF: calculation timer is already scheduled: %p",
647 (void *)ospf6->t_spf_calc);
648 return;
649 }
650
651 /* XXX Monotic timers: we only care about relative time here. */
652 now = recent_relative_time ();
653 timersub (&now, &ospf6->ts_spf, &result);
654
655 elapsed = (result.tv_sec * 1000) + (result.tv_usec / 1000);
656 ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier;
657
658 if (ht > ospf6->spf_max_holdtime)
659 ht = ospf6->spf_max_holdtime;
660
661 /* Get SPF calculation delay time. */
662 if (elapsed < ht)
663 {
664 /* Got an event within the hold time of last SPF. We need to
665 * increase the hold_multiplier, if it's not already at/past
666 * maximum value, and wasn't already increased..
667 */
668 if (ht < ospf6->spf_max_holdtime)
669 ospf6->spf_hold_multiplier++;
670
671 /* always honour the SPF initial delay */
672 if ( (ht - elapsed) < ospf6->spf_delay)
673 delay = ospf6->spf_delay;
674 else
675 delay = ht - elapsed;
676 }
677 else
678 {
679 /* Event is past required hold-time of last SPF */
680 delay = ospf6->spf_delay;
681 ospf6->spf_hold_multiplier = 1;
682 }
683
684 if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
685 zlog_debug ("SPF: calculation timer delay = %ld", delay);
686
687 zlog_info ("SPF: Scheduled in %ld msec", delay);
688
689 ospf6->t_spf_calc =
690 thread_add_timer_msec (master, ospf6_spf_calculation_thread, ospf6, delay);
691 }
692
693 void
ospf6_spf_display_subtree(struct vty * vty,const char * prefix,int rest,struct ospf6_vertex * v)694 ospf6_spf_display_subtree (struct vty *vty, const char *prefix, int rest,
695 struct ospf6_vertex *v)
696 {
697 struct listnode *node, *nnode;
698 struct ospf6_vertex *c;
699 char *next_prefix;
700 int len;
701 int restnum;
702
703 /* "prefix" is the space prefix of the display line */
704 vty_out (vty, "%s+-%s [%d]%s", prefix, v->name, v->cost, VNL);
705
706 len = strlen (prefix) + 4;
707 next_prefix = (char *) malloc (len);
708 if (next_prefix == NULL)
709 {
710 vty_out (vty, "malloc failed%s", VNL);
711 return;
712 }
713 snprintf (next_prefix, len, "%s%s", prefix, (rest ? "| " : " "));
714
715 restnum = listcount (v->child_list);
716 for (ALL_LIST_ELEMENTS (v->child_list, node, nnode, c))
717 {
718 restnum--;
719 ospf6_spf_display_subtree (vty, next_prefix, restnum, c);
720 }
721
722 free (next_prefix);
723 }
724
725 DEFUN (debug_ospf6_spf_process,
726 debug_ospf6_spf_process_cmd,
727 "debug ospf6 spf process",
728 DEBUG_STR
729 OSPF6_STR
730 "Debug SPF Calculation\n"
731 "Debug Detailed SPF Process\n"
732 )
733 {
734 unsigned char level = 0;
735 level = OSPF6_DEBUG_SPF_PROCESS;
736 OSPF6_DEBUG_SPF_ON (level);
737 return CMD_SUCCESS;
738 }
739
740 DEFUN (debug_ospf6_spf_time,
741 debug_ospf6_spf_time_cmd,
742 "debug ospf6 spf time",
743 DEBUG_STR
744 OSPF6_STR
745 "Debug SPF Calculation\n"
746 "Measure time taken by SPF Calculation\n"
747 )
748 {
749 unsigned char level = 0;
750 level = OSPF6_DEBUG_SPF_TIME;
751 OSPF6_DEBUG_SPF_ON (level);
752 return CMD_SUCCESS;
753 }
754
755 DEFUN (debug_ospf6_spf_database,
756 debug_ospf6_spf_database_cmd,
757 "debug ospf6 spf database",
758 DEBUG_STR
759 OSPF6_STR
760 "Debug SPF Calculation\n"
761 "Log number of LSAs at SPF Calculation time\n"
762 )
763 {
764 unsigned char level = 0;
765 level = OSPF6_DEBUG_SPF_DATABASE;
766 OSPF6_DEBUG_SPF_ON (level);
767 return CMD_SUCCESS;
768 }
769
770 DEFUN (no_debug_ospf6_spf_process,
771 no_debug_ospf6_spf_process_cmd,
772 "no debug ospf6 spf process",
773 NO_STR
774 DEBUG_STR
775 OSPF6_STR
776 "Quit Debugging SPF Calculation\n"
777 "Quit Debugging Detailed SPF Process\n"
778 )
779 {
780 unsigned char level = 0;
781 level = OSPF6_DEBUG_SPF_PROCESS;
782 OSPF6_DEBUG_SPF_OFF (level);
783 return CMD_SUCCESS;
784 }
785
786 DEFUN (no_debug_ospf6_spf_time,
787 no_debug_ospf6_spf_time_cmd,
788 "no debug ospf6 spf time",
789 NO_STR
790 DEBUG_STR
791 OSPF6_STR
792 "Quit Debugging SPF Calculation\n"
793 "Quit Measuring time taken by SPF Calculation\n"
794 )
795 {
796 unsigned char level = 0;
797 level = OSPF6_DEBUG_SPF_TIME;
798 OSPF6_DEBUG_SPF_OFF (level);
799 return CMD_SUCCESS;
800 }
801
802 DEFUN (no_debug_ospf6_spf_database,
803 no_debug_ospf6_spf_database_cmd,
804 "no debug ospf6 spf database",
805 NO_STR
806 DEBUG_STR
807 OSPF6_STR
808 "Debug SPF Calculation\n"
809 "Quit Logging number of LSAs at SPF Calculation time\n"
810 )
811 {
812 unsigned char level = 0;
813 level = OSPF6_DEBUG_SPF_DATABASE;
814 OSPF6_DEBUG_SPF_OFF (level);
815 return CMD_SUCCESS;
816 }
817
818 static int
ospf6_timers_spf_set(struct vty * vty,unsigned int delay,unsigned int hold,unsigned int max)819 ospf6_timers_spf_set (struct vty *vty, unsigned int delay,
820 unsigned int hold,
821 unsigned int max)
822 {
823 struct ospf6 *ospf = vty->index;
824
825 ospf->spf_delay = delay;
826 ospf->spf_holdtime = hold;
827 ospf->spf_max_holdtime = max;
828
829 return CMD_SUCCESS;
830 }
831
832 DEFUN (ospf6_timers_throttle_spf,
833 ospf6_timers_throttle_spf_cmd,
834 "timers throttle spf <0-600000> <0-600000> <0-600000>",
835 "Adjust routing timers\n"
836 "Throttling adaptive timer\n"
837 "OSPF6 SPF timers\n"
838 "Delay (msec) from first change received till SPF calculation\n"
839 "Initial hold time (msec) between consecutive SPF calculations\n"
840 "Maximum hold time (msec)\n")
841 {
842 unsigned int delay, hold, max;
843
844 if (argc != 3)
845 {
846 vty_out (vty, "Insufficient arguments%s", VTY_NEWLINE);
847 return CMD_WARNING;
848 }
849
850 VTY_GET_INTEGER_RANGE ("SPF delay timer", delay, argv[0], 0, 600000);
851 VTY_GET_INTEGER_RANGE ("SPF hold timer", hold, argv[1], 0, 600000);
852 VTY_GET_INTEGER_RANGE ("SPF max-hold timer", max, argv[2], 0, 600000);
853
854 return ospf6_timers_spf_set (vty, delay, hold, max);
855 }
856
857 DEFUN (no_ospf6_timers_throttle_spf,
858 no_ospf6_timers_throttle_spf_cmd,
859 "no timers throttle spf",
860 NO_STR
861 "Adjust routing timers\n"
862 "Throttling adaptive timer\n"
863 "OSPF6 SPF timers\n")
864 {
865 return ospf6_timers_spf_set (vty,
866 OSPF_SPF_DELAY_DEFAULT,
867 OSPF_SPF_HOLDTIME_DEFAULT,
868 OSPF_SPF_MAX_HOLDTIME_DEFAULT);
869 }
870
871 int
config_write_ospf6_debug_spf(struct vty * vty)872 config_write_ospf6_debug_spf (struct vty *vty)
873 {
874 if (IS_OSPF6_DEBUG_SPF (PROCESS))
875 vty_out (vty, "debug ospf6 spf process%s", VNL);
876 if (IS_OSPF6_DEBUG_SPF (TIME))
877 vty_out (vty, "debug ospf6 spf time%s", VNL);
878 if (IS_OSPF6_DEBUG_SPF (DATABASE))
879 vty_out (vty, "debug ospf6 spf database%s", VNL);
880 return 0;
881 }
882
883 void
ospf6_spf_config_write(struct vty * vty)884 ospf6_spf_config_write (struct vty *vty)
885 {
886
887 if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT ||
888 ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT ||
889 ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT)
890 vty_out (vty, " timers throttle spf %d %d %d%s",
891 ospf6->spf_delay, ospf6->spf_holdtime,
892 ospf6->spf_max_holdtime, VTY_NEWLINE);
893
894 }
895
896 void
install_element_ospf6_debug_spf(void)897 install_element_ospf6_debug_spf (void)
898 {
899 install_element (ENABLE_NODE, &debug_ospf6_spf_process_cmd);
900 install_element (ENABLE_NODE, &debug_ospf6_spf_time_cmd);
901 install_element (ENABLE_NODE, &debug_ospf6_spf_database_cmd);
902 install_element (ENABLE_NODE, &no_debug_ospf6_spf_process_cmd);
903 install_element (ENABLE_NODE, &no_debug_ospf6_spf_time_cmd);
904 install_element (ENABLE_NODE, &no_debug_ospf6_spf_database_cmd);
905 install_element (CONFIG_NODE, &debug_ospf6_spf_process_cmd);
906 install_element (CONFIG_NODE, &debug_ospf6_spf_time_cmd);
907 install_element (CONFIG_NODE, &debug_ospf6_spf_database_cmd);
908 install_element (CONFIG_NODE, &no_debug_ospf6_spf_process_cmd);
909 install_element (CONFIG_NODE, &no_debug_ospf6_spf_time_cmd);
910 install_element (CONFIG_NODE, &no_debug_ospf6_spf_database_cmd);
911 }
912
913 void
ospf6_spf_init(void)914 ospf6_spf_init (void)
915 {
916 install_element (OSPF6_NODE, &ospf6_timers_throttle_spf_cmd);
917 install_element (OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd);
918 }
919