Annotation of embedaddon/quagga/ospf6d/ospf6_spf.c, revision 1.1.1.4
1.1 misho 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"
1.1.1.4 ! misho 43: #include "ospf6_abr.h"
1.1 misho 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: {
1.1.1.4 ! misho 228: int i;
! 229: ifindex_t ifindex;
1.1 misho 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 :
1.1.1.4 ! misho 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:
1.1 misho 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:
1.1.1.4 ! misho 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:
1.1 misho 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:
1.1.1.2 misho 429: ospf6_spf_table_finish (result_table);
430:
1.1 misho 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:
1.1.1.4 ! misho 462: /* Skip overloaded routers */
! 463: if ((OSPF6_LSA_IS_TYPE (ROUTER, v->lsa) &&
! 464: ospf6_router_is_stub_router (v->lsa)))
! 465: continue;
! 466:
1.1 misho 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);
1.1.1.3 misho 516:
517: oa->spf_calculation++;
1.1 misho 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;
1.1.1.4 ! misho 549: struct ospf6 *ospf6;
1.1 misho 550: struct timeval start, end, runtime;
1.1.1.4 ! misho 551: struct listnode *node;
! 552: struct ospf6_route *route;
! 553: int areas_processed = 0;
! 554: char rbuf[32];
1.1 misho 555:
1.1.1.4 ! misho 556: ospf6 = (struct ospf6 *)THREAD_ARG (t);
! 557: ospf6->t_spf_calc = NULL;
1.1 misho 558:
559: /* execute SPF calculation */
560: quagga_gettime (QUAGGA_CLK_MONOTONIC, &start);
1.1.1.4 ! misho 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:
1.1 misho 600: quagga_gettime (QUAGGA_CLK_MONOTONIC, &end);
601: timersub (&end, &start, &runtime);
602:
1.1.1.4 ! misho 603: ospf6->ts_spf_duration = runtime;
1.1 misho 604:
1.1.1.4 ! misho 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);
1.1 misho 610:
1.1.1.4 ! misho 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);
1.1 misho 617: return 0;
618: }
619:
1.1.1.4 ! misho 620: /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
! 621: set timer for SPF calc. */
1.1 misho 622: void
1.1.1.4 ! misho 623: ospf6_spf_schedule (struct ospf6 *ospf6, unsigned int reason)
1.1 misho 624: {
1.1.1.4 ! misho 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)
1.1 misho 639: return;
1.1.1.4 ! misho 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);
1.1 misho 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:
1.1.1.4 ! misho 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:
1.1 misho 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
1.1.1.4 ! misho 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
1.1 misho 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: {
1.1.1.4 ! misho 915: install_element (OSPF6_NODE, &ospf6_timers_throttle_spf_cmd);
! 916: install_element (OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd);
1.1 misho 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