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
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
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 *
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
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 *
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 *
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
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
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; ospf6_nexthop_is_set (&v->nexthop[i]) &&
311: i < OSPF6_MULTI_PATH_LIMIT; 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; ospf6_nexthop_is_set (&v->nexthop[i]) &&
360: i < OSPF6_MULTI_PATH_LIMIT; 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
372: ospf6_spf_table_finish (struct ospf6_route_table *result_table)
373: {
374: struct ospf6_route *route;
375: struct ospf6_vertex *v;
376: for (route = ospf6_route_head (result_table); route;
377: route = ospf6_route_next (route))
378: {
379: v = (struct ospf6_vertex *) route->route_option;
380: ospf6_vertex_delete (v);
381: ospf6_route_remove (route, result_table);
382: }
383: }
384:
385: static const char *ospf6_spf_reason_str[] =
386: {
387: "R+",
388: "R-",
389: "N+",
390: "N-",
391: "L+",
392: "L-",
393: "R*",
394: "N*",
395: };
396:
397: void ospf6_spf_reason_string (unsigned int reason, char *buf, int size)
398: {
399: size_t bit;
400: int len = 0;
401:
402: if (!buf)
403: return;
404:
405: for (bit = 0; bit <= (sizeof(ospf6_spf_reason_str) / sizeof(char *)); bit++)
406: {
407: if ((reason & (1 << bit)) && (len < size))
408: {
409: len += snprintf((buf + len), (size - len), "%s%s",
410: (len > 0) ? ", " : "", ospf6_spf_reason_str[bit]);
411: }
412: }
413: }
414:
415: /* RFC2328 16.1. Calculating the shortest-path tree for an area */
416: /* RFC2740 3.8.1. Calculating the shortest path tree for an area */
417: void
418: ospf6_spf_calculation (u_int32_t router_id,
419: struct ospf6_route_table *result_table,
420: struct ospf6_area *oa)
421: {
422: struct pqueue *candidate_list;
423: struct ospf6_vertex *root, *v, *w;
424: int i;
425: int size;
426: caddr_t lsdesc;
427: struct ospf6_lsa *lsa;
428:
429: ospf6_spf_table_finish (result_table);
430:
431: /* Install the calculating router itself as the root of the SPF tree */
432: /* construct root vertex */
433: lsa = ospf6_lsdb_lookup (htons (OSPF6_LSTYPE_ROUTER), htonl (0),
434: router_id, oa->lsdb);
435: if (lsa == NULL)
436: return;
437:
438: /* initialize */
439: candidate_list = pqueue_create ();
440: candidate_list->cmp = ospf6_vertex_cmp;
441:
442: root = ospf6_vertex_create (lsa);
443: root->area = oa;
444: root->cost = 0;
445: root->hops = 0;
446: root->nexthop[0].ifindex = 0; /* loopbak I/F is better ... */
447: inet_pton (AF_INET6, "::1", &root->nexthop[0].address);
448:
449: /* Actually insert root to the candidate-list as the only candidate */
450: pqueue_enqueue (root, candidate_list);
451:
452: /* Iterate until candidate-list becomes empty */
453: while (candidate_list->size)
454: {
455: /* get closest candidate from priority queue */
456: v = pqueue_dequeue (candidate_list);
457:
458: /* installing may result in merging or rejecting of the vertex */
459: if (ospf6_spf_install (v, result_table) < 0)
460: continue;
461:
462: /* Skip overloaded routers */
463: if ((OSPF6_LSA_IS_TYPE (ROUTER, v->lsa) &&
464: ospf6_router_is_stub_router (v->lsa)))
465: continue;
466:
467: /* For each LS description in the just-added vertex V's LSA */
468: size = (VERTEX_IS_TYPE (ROUTER, v) ?
469: sizeof (struct ospf6_router_lsdesc) :
470: sizeof (struct ospf6_network_lsdesc));
471: for (lsdesc = OSPF6_LSA_HEADER_END (v->lsa->header) + 4;
472: lsdesc + size <= OSPF6_LSA_END (v->lsa->header); lsdesc += size)
473: {
474: lsa = ospf6_lsdesc_lsa (lsdesc, v);
475: if (lsa == NULL)
476: continue;
477:
478: if (! ospf6_lsdesc_backlink (lsa, lsdesc, v))
479: continue;
480:
481: w = ospf6_vertex_create (lsa);
482: w->area = oa;
483: w->parent = v;
484: if (VERTEX_IS_TYPE (ROUTER, v))
485: {
486: w->cost = v->cost + ROUTER_LSDESC_GET_METRIC (lsdesc);
487: w->hops = v->hops + (VERTEX_IS_TYPE (NETWORK, w) ? 0 : 1);
488: }
489: else /* NETWORK */
490: {
491: w->cost = v->cost;
492: w->hops = v->hops + 1;
493: }
494:
495: /* nexthop calculation */
496: if (w->hops == 0)
497: w->nexthop[0].ifindex = ROUTER_LSDESC_GET_IFID (lsdesc);
498: else if (w->hops == 1 && v->hops == 0)
499: ospf6_nexthop_calc (w, v, lsdesc);
500: else
501: {
502: for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) &&
503: i < OSPF6_MULTI_PATH_LIMIT; i++)
504: ospf6_nexthop_copy (&w->nexthop[i], &v->nexthop[i]);
505: }
506:
507: /* add new candidate to the candidate_list */
508: if (IS_OSPF6_DEBUG_SPF (PROCESS))
509: zlog_debug (" New candidate: %s hops %d cost %d",
510: w->name, w->hops, w->cost);
511: pqueue_enqueue (w, candidate_list);
512: }
513: }
514:
515: pqueue_delete (candidate_list);
516:
517: oa->spf_calculation++;
518: }
519:
520: static void
521: ospf6_spf_log_database (struct ospf6_area *oa)
522: {
523: char *p, *end, buffer[256];
524: struct listnode *node;
525: struct ospf6_interface *oi;
526:
527: p = buffer;
528: end = buffer + sizeof (buffer);
529:
530: snprintf (p, end - p, "SPF on DB (#LSAs):");
531: p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
532: snprintf (p, end - p, " Area %s: %d", oa->name, oa->lsdb->count);
533: p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
534:
535: for (ALL_LIST_ELEMENTS_RO (oa->if_list, node, oi))
536: {
537: snprintf (p, end - p, " I/F %s: %d",
538: oi->interface->name, oi->lsdb->count);
539: p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
540: }
541:
542: zlog_debug ("%s", buffer);
543: }
544:
545: static int
546: ospf6_spf_calculation_thread (struct thread *t)
547: {
548: struct ospf6_area *oa;
549: struct ospf6 *ospf6;
550: struct timeval start, end, runtime;
551: struct listnode *node;
552: struct ospf6_route *route;
553: int areas_processed = 0;
554: char rbuf[32];
555:
556: ospf6 = (struct ospf6 *)THREAD_ARG (t);
557: ospf6->t_spf_calc = NULL;
558:
559: /* execute SPF calculation */
560: quagga_gettime (QUAGGA_CLK_MONOTONIC, &start);
561:
562: for (ALL_LIST_ELEMENTS_RO(ospf6->area_list, node, oa))
563: {
564:
565: if (oa == ospf6->backbone)
566: continue;
567:
568: if (IS_OSPF6_DEBUG_SPF (PROCESS))
569: zlog_debug ("SPF calculation for Area %s", oa->name);
570: if (IS_OSPF6_DEBUG_SPF (DATABASE))
571: ospf6_spf_log_database (oa);
572:
573: ospf6_spf_calculation (ospf6->router_id, oa->spf_table, oa);
574: ospf6_intra_route_calculation (oa);
575: ospf6_intra_brouter_calculation (oa);
576:
577: areas_processed++;
578: }
579:
580: if (ospf6->backbone)
581: {
582: if (IS_OSPF6_DEBUG_SPF (PROCESS))
583: zlog_debug ("SPF calculation for Backbone area %s",
584: ospf6->backbone->name);
585: if (IS_OSPF6_DEBUG_SPF (DATABASE))
586: ospf6_spf_log_database(ospf6->backbone);
587:
588: ospf6_spf_calculation(ospf6->router_id, ospf6->backbone->spf_table,
589: ospf6->backbone);
590: ospf6_intra_route_calculation(ospf6->backbone);
591: ospf6_intra_brouter_calculation(ospf6->backbone);
592: areas_processed++;
593: }
594:
595: /* Redo summaries if required */
596: for (route = ospf6_route_head (ospf6->route_table); route;
597: route = ospf6_route_next (route))
598: ospf6_abr_originate_summary(route);
599:
600: quagga_gettime (QUAGGA_CLK_MONOTONIC, &end);
601: timersub (&end, &start, &runtime);
602:
603: ospf6->ts_spf_duration = runtime;
604:
605: ospf6_spf_reason_string(ospf6->spf_reason, rbuf, sizeof(rbuf));
606:
607: if (IS_OSPF6_DEBUG_SPF (PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
608: zlog_debug ("SPF runtime: %lld sec %lld usec",
609: (long long)runtime.tv_sec, (long long)runtime.tv_usec);
610:
611: zlog_info("SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
612: "Reason: %s\n", areas_processed,
613: (long long)runtime.tv_sec, (long long)runtime.tv_usec,
614: rbuf);
615: ospf6->last_spf_reason = ospf6->spf_reason;
616: ospf6_reset_spf_reason(ospf6);
617: return 0;
618: }
619:
620: /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
621: set timer for SPF calc. */
622: void
623: ospf6_spf_schedule (struct ospf6 *ospf6, unsigned int reason)
624: {
625: unsigned long delay, elapsed, ht;
626: struct timeval now, result;
627:
628: ospf6_set_spf_reason(ospf6, reason);
629:
630: if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
631: {
632: char rbuf[32];
633: ospf6_spf_reason_string(reason, rbuf, sizeof(rbuf));
634: zlog_debug ("SPF: calculation timer scheduled (reason %s)", rbuf);
635: }
636:
637: /* OSPF instance does not exist. */
638: if (ospf6 == NULL)
639: return;
640:
641: /* SPF calculation timer is already scheduled. */
642: if (ospf6->t_spf_calc)
643: {
644: if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
645: zlog_debug ("SPF: calculation timer is already scheduled: %p",
646: (void *)ospf6->t_spf_calc);
647: return;
648: }
649:
650: /* XXX Monotic timers: we only care about relative time here. */
651: now = recent_relative_time ();
652: timersub (&now, &ospf6->ts_spf, &result);
653:
654: elapsed = (result.tv_sec * 1000) + (result.tv_usec / 1000);
655: ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier;
656:
657: if (ht > ospf6->spf_max_holdtime)
658: ht = ospf6->spf_max_holdtime;
659:
660: /* Get SPF calculation delay time. */
661: if (elapsed < ht)
662: {
663: /* Got an event within the hold time of last SPF. We need to
664: * increase the hold_multiplier, if it's not already at/past
665: * maximum value, and wasn't already increased..
666: */
667: if (ht < ospf6->spf_max_holdtime)
668: ospf6->spf_hold_multiplier++;
669:
670: /* always honour the SPF initial delay */
671: if ( (ht - elapsed) < ospf6->spf_delay)
672: delay = ospf6->spf_delay;
673: else
674: delay = ht - elapsed;
675: }
676: else
677: {
678: /* Event is past required hold-time of last SPF */
679: delay = ospf6->spf_delay;
680: ospf6->spf_hold_multiplier = 1;
681: }
682:
683: if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
684: zlog_debug ("SPF: calculation timer delay = %ld", delay);
685:
686: zlog_info ("SPF: Scheduled in %ld msec", delay);
687:
688: ospf6->t_spf_calc =
689: thread_add_timer_msec (master, ospf6_spf_calculation_thread, ospf6, delay);
690: }
691:
692: void
693: ospf6_spf_display_subtree (struct vty *vty, const char *prefix, int rest,
694: struct ospf6_vertex *v)
695: {
696: struct listnode *node, *nnode;
697: struct ospf6_vertex *c;
698: char *next_prefix;
699: int len;
700: int restnum;
701:
702: /* "prefix" is the space prefix of the display line */
703: vty_out (vty, "%s+-%s [%d]%s", prefix, v->name, v->cost, VNL);
704:
705: len = strlen (prefix) + 4;
706: next_prefix = (char *) malloc (len);
707: if (next_prefix == NULL)
708: {
709: vty_out (vty, "malloc failed%s", VNL);
710: return;
711: }
712: snprintf (next_prefix, len, "%s%s", prefix, (rest ? "| " : " "));
713:
714: restnum = listcount (v->child_list);
715: for (ALL_LIST_ELEMENTS (v->child_list, node, nnode, c))
716: {
717: restnum--;
718: ospf6_spf_display_subtree (vty, next_prefix, restnum, c);
719: }
720:
721: free (next_prefix);
722: }
723:
724: DEFUN (debug_ospf6_spf_process,
725: debug_ospf6_spf_process_cmd,
726: "debug ospf6 spf process",
727: DEBUG_STR
728: OSPF6_STR
729: "Debug SPF Calculation\n"
730: "Debug Detailed SPF Process\n"
731: )
732: {
733: unsigned char level = 0;
734: level = OSPF6_DEBUG_SPF_PROCESS;
735: OSPF6_DEBUG_SPF_ON (level);
736: return CMD_SUCCESS;
737: }
738:
739: DEFUN (debug_ospf6_spf_time,
740: debug_ospf6_spf_time_cmd,
741: "debug ospf6 spf time",
742: DEBUG_STR
743: OSPF6_STR
744: "Debug SPF Calculation\n"
745: "Measure time taken by SPF Calculation\n"
746: )
747: {
748: unsigned char level = 0;
749: level = OSPF6_DEBUG_SPF_TIME;
750: OSPF6_DEBUG_SPF_ON (level);
751: return CMD_SUCCESS;
752: }
753:
754: DEFUN (debug_ospf6_spf_database,
755: debug_ospf6_spf_database_cmd,
756: "debug ospf6 spf database",
757: DEBUG_STR
758: OSPF6_STR
759: "Debug SPF Calculation\n"
760: "Log number of LSAs at SPF Calculation time\n"
761: )
762: {
763: unsigned char level = 0;
764: level = OSPF6_DEBUG_SPF_DATABASE;
765: OSPF6_DEBUG_SPF_ON (level);
766: return CMD_SUCCESS;
767: }
768:
769: DEFUN (no_debug_ospf6_spf_process,
770: no_debug_ospf6_spf_process_cmd,
771: "no debug ospf6 spf process",
772: NO_STR
773: DEBUG_STR
774: OSPF6_STR
775: "Quit Debugging SPF Calculation\n"
776: "Quit Debugging Detailed SPF Process\n"
777: )
778: {
779: unsigned char level = 0;
780: level = OSPF6_DEBUG_SPF_PROCESS;
781: OSPF6_DEBUG_SPF_OFF (level);
782: return CMD_SUCCESS;
783: }
784:
785: DEFUN (no_debug_ospf6_spf_time,
786: no_debug_ospf6_spf_time_cmd,
787: "no debug ospf6 spf time",
788: NO_STR
789: DEBUG_STR
790: OSPF6_STR
791: "Quit Debugging SPF Calculation\n"
792: "Quit Measuring time taken by SPF Calculation\n"
793: )
794: {
795: unsigned char level = 0;
796: level = OSPF6_DEBUG_SPF_TIME;
797: OSPF6_DEBUG_SPF_OFF (level);
798: return CMD_SUCCESS;
799: }
800:
801: DEFUN (no_debug_ospf6_spf_database,
802: no_debug_ospf6_spf_database_cmd,
803: "no debug ospf6 spf database",
804: NO_STR
805: DEBUG_STR
806: OSPF6_STR
807: "Debug SPF Calculation\n"
808: "Quit Logging number of LSAs at SPF Calculation time\n"
809: )
810: {
811: unsigned char level = 0;
812: level = OSPF6_DEBUG_SPF_DATABASE;
813: OSPF6_DEBUG_SPF_OFF (level);
814: return CMD_SUCCESS;
815: }
816:
817: static int
818: ospf6_timers_spf_set (struct vty *vty, unsigned int delay,
819: unsigned int hold,
820: unsigned int max)
821: {
822: struct ospf6 *ospf = vty->index;
823:
824: ospf->spf_delay = delay;
825: ospf->spf_holdtime = hold;
826: ospf->spf_max_holdtime = max;
827:
828: return CMD_SUCCESS;
829: }
830:
831: DEFUN (ospf6_timers_throttle_spf,
832: ospf6_timers_throttle_spf_cmd,
833: "timers throttle spf <0-600000> <0-600000> <0-600000>",
834: "Adjust routing timers\n"
835: "Throttling adaptive timer\n"
836: "OSPF6 SPF timers\n"
837: "Delay (msec) from first change received till SPF calculation\n"
838: "Initial hold time (msec) between consecutive SPF calculations\n"
839: "Maximum hold time (msec)\n")
840: {
841: unsigned int delay, hold, max;
842:
843: if (argc != 3)
844: {
845: vty_out (vty, "Insufficient arguments%s", VTY_NEWLINE);
846: return CMD_WARNING;
847: }
848:
849: VTY_GET_INTEGER_RANGE ("SPF delay timer", delay, argv[0], 0, 600000);
850: VTY_GET_INTEGER_RANGE ("SPF hold timer", hold, argv[1], 0, 600000);
851: VTY_GET_INTEGER_RANGE ("SPF max-hold timer", max, argv[2], 0, 600000);
852:
853: return ospf6_timers_spf_set (vty, delay, hold, max);
854: }
855:
856: DEFUN (no_ospf6_timers_throttle_spf,
857: no_ospf6_timers_throttle_spf_cmd,
858: "no timers throttle spf",
859: NO_STR
860: "Adjust routing timers\n"
861: "Throttling adaptive timer\n"
862: "OSPF6 SPF timers\n")
863: {
864: return ospf6_timers_spf_set (vty,
865: OSPF_SPF_DELAY_DEFAULT,
866: OSPF_SPF_HOLDTIME_DEFAULT,
867: OSPF_SPF_MAX_HOLDTIME_DEFAULT);
868: }
869:
870: int
871: config_write_ospf6_debug_spf (struct vty *vty)
872: {
873: if (IS_OSPF6_DEBUG_SPF (PROCESS))
874: vty_out (vty, "debug ospf6 spf process%s", VNL);
875: if (IS_OSPF6_DEBUG_SPF (TIME))
876: vty_out (vty, "debug ospf6 spf time%s", VNL);
877: if (IS_OSPF6_DEBUG_SPF (DATABASE))
878: vty_out (vty, "debug ospf6 spf database%s", VNL);
879: return 0;
880: }
881:
882: void
883: ospf6_spf_config_write (struct vty *vty)
884: {
885:
886: if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT ||
887: ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT ||
888: ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT)
889: vty_out (vty, " timers throttle spf %d %d %d%s",
890: ospf6->spf_delay, ospf6->spf_holdtime,
891: ospf6->spf_max_holdtime, VTY_NEWLINE);
892:
893: }
894:
895: void
896: install_element_ospf6_debug_spf (void)
897: {
898: install_element (ENABLE_NODE, &debug_ospf6_spf_process_cmd);
899: install_element (ENABLE_NODE, &debug_ospf6_spf_time_cmd);
900: install_element (ENABLE_NODE, &debug_ospf6_spf_database_cmd);
901: install_element (ENABLE_NODE, &no_debug_ospf6_spf_process_cmd);
902: install_element (ENABLE_NODE, &no_debug_ospf6_spf_time_cmd);
903: install_element (ENABLE_NODE, &no_debug_ospf6_spf_database_cmd);
904: install_element (CONFIG_NODE, &debug_ospf6_spf_process_cmd);
905: install_element (CONFIG_NODE, &debug_ospf6_spf_time_cmd);
906: install_element (CONFIG_NODE, &debug_ospf6_spf_database_cmd);
907: install_element (CONFIG_NODE, &no_debug_ospf6_spf_process_cmd);
908: install_element (CONFIG_NODE, &no_debug_ospf6_spf_time_cmd);
909: install_element (CONFIG_NODE, &no_debug_ospf6_spf_database_cmd);
910: }
911:
912: void
913: ospf6_spf_init (void)
914: {
915: install_element (OSPF6_NODE, &ospf6_timers_throttle_spf_cmd);
916: install_element (OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd);
917: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ospf6_spf.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / ospf6d