blob: 15d27be7fd4fb8bc3fb73c53a9c30f73a1676d39 [file] [log] [blame]
paul718e3742002-12-13 20:15:29 +00001/* OSPF SPF calculation.
2 Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
3
4This file is part of GNU Zebra.
5
6GNU Zebra is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 2, or (at your option) any
9later version.
10
11GNU Zebra is distributed in the hope that it will be useful, but
12WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with GNU Zebra; see the file COPYING. If not, write to the Free
18Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
1902111-1307, USA. */
20
21#include <zebra.h>
22
23#include "thread.h"
24#include "memory.h"
25#include "hash.h"
26#include "linklist.h"
27#include "prefix.h"
28#include "if.h"
29#include "table.h"
30#include "log.h"
31#include "sockunion.h" /* for inet_ntop () */
hasso462f20d2005-02-23 11:29:02 +000032#include "pqueue.h"
paul718e3742002-12-13 20:15:29 +000033
34#include "ospfd/ospfd.h"
35#include "ospfd/ospf_interface.h"
36#include "ospfd/ospf_ism.h"
37#include "ospfd/ospf_asbr.h"
38#include "ospfd/ospf_lsa.h"
39#include "ospfd/ospf_lsdb.h"
40#include "ospfd/ospf_neighbor.h"
41#include "ospfd/ospf_nsm.h"
42#include "ospfd/ospf_spf.h"
43#include "ospfd/ospf_route.h"
44#include "ospfd/ospf_ia.h"
45#include "ospfd/ospf_ase.h"
46#include "ospfd/ospf_abr.h"
47#include "ospfd/ospf_dump.h"
48
Paul Jakma9c27ef92006-05-04 07:32:57 +000049static void ospf_vertex_free (void *);
50/* List of allocated vertices, to simplify cleanup of SPF.
51 * Not thread-safe obviously. If it ever needs to be, it'd have to be
52 * dynamically allocated at begin of ospf_spf_calculate
53 */
54static struct list vertex_list = { .del = ospf_vertex_free };
55
hasso462f20d2005-02-23 11:29:02 +000056/* Heap related functions, for the managment of the candidates, to
57 * be used with pqueue. */
58static int
59cmp (void * node1 , void * node2)
60{
61 struct vertex * v1 = (struct vertex *) node1;
62 struct vertex * v2 = (struct vertex *) node2;
63 if (v1 != NULL && v2 != NULL )
Paul Jakma9c27ef92006-05-04 07:32:57 +000064 {
65 /* network vertices must be chosen before router vertices of same
66 * cost in order to find all shortest paths
67 */
68 if ( ((v1->distance - v2->distance) == 0)
69 && (v1->type != v2->type))
70 {
71 switch (v1->type)
72 {
73 case OSPF_VERTEX_NETWORK:
74 return -1;
75 case OSPF_VERTEX_ROUTER:
76 return 1;
77 }
78 }
79 else
80 return (v1->distance - v2->distance);
81 }
82 return 0;
hasso462f20d2005-02-23 11:29:02 +000083}
84
85static void
pauleb3da6d2005-10-18 04:20:33 +000086update_stat (void *node , int position)
hasso462f20d2005-02-23 11:29:02 +000087{
pauleb3da6d2005-10-18 04:20:33 +000088 struct vertex *v = node;
89
hasso462f20d2005-02-23 11:29:02 +000090 /* Set the status of the vertex, when its position changes. */
91 *(v->stat) = position;
92}
pauleb3da6d2005-10-18 04:20:33 +000093
paul4dadc292005-05-06 21:37:42 +000094static struct vertex_nexthop *
pauleb3da6d2005-10-18 04:20:33 +000095vertex_nexthop_new (void)
paul718e3742002-12-13 20:15:29 +000096{
pauleb3da6d2005-10-18 04:20:33 +000097 return XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop));
paul718e3742002-12-13 20:15:29 +000098}
99
paul4dadc292005-05-06 21:37:42 +0000100static void
paul718e3742002-12-13 20:15:29 +0000101vertex_nexthop_free (struct vertex_nexthop *nh)
102{
103 XFREE (MTYPE_OSPF_NEXTHOP, nh);
104}
105
pauleb3da6d2005-10-18 04:20:33 +0000106/* Free the canonical nexthop objects for an area, ie the nexthop objects
Paul Jakma9c27ef92006-05-04 07:32:57 +0000107 * attached to the first-hop router vertices, and any intervening network
108 * vertices.
pauleb3da6d2005-10-18 04:20:33 +0000109 */
110static void
111ospf_canonical_nexthops_free (struct vertex *root)
paul718e3742002-12-13 20:15:29 +0000112{
pauleb3da6d2005-10-18 04:20:33 +0000113 struct listnode *node, *nnode;
114 struct vertex *child;
115
116 for (ALL_LIST_ELEMENTS (root->children, node, nnode, child))
117 {
118 struct listnode *n2, *nn2;
119 struct vertex_parent *vp;
120
paul58e1bef2005-11-11 12:10:03 +0000121 /* router vertices through an attached network each
122 * have a distinct (canonical / not inherited) nexthop
123 * which must be freed.
124 *
125 * A network vertex can only have router vertices as its
126 * children, so only one level of recursion is possible.
127 */
pauleb3da6d2005-10-18 04:20:33 +0000128 if (child->type == OSPF_VERTEX_NETWORK)
129 ospf_canonical_nexthops_free (child);
130
paul58e1bef2005-11-11 12:10:03 +0000131 /* Free child nexthops pointing back to this root vertex */
pauleb3da6d2005-10-18 04:20:33 +0000132 for (ALL_LIST_ELEMENTS (child->parents, n2, nn2, vp))
Paul Jakma9c27ef92006-05-04 07:32:57 +0000133 if (vp->parent == root && vp->nexthop)
paul58e1bef2005-11-11 12:10:03 +0000134 vertex_nexthop_free (vp->nexthop);
pauleb3da6d2005-10-18 04:20:33 +0000135 }
136}
137
Paul Jakma9c27ef92006-05-04 07:32:57 +0000138/* TODO: Parent list should be excised, in favour of maintaining only
139 * vertex_nexthop, with refcounts.
140 */
pauleb3da6d2005-10-18 04:20:33 +0000141static struct vertex_parent *
142vertex_parent_new (struct vertex *v, int backlink, struct vertex_nexthop *hop)
143{
144 struct vertex_parent *new;
145
146 new = XMALLOC (MTYPE_OSPF_VERTEX_PARENT, sizeof (struct vertex_parent));
147
148 if (new == NULL)
149 return NULL;
150
151 new->parent = v;
152 new->backlink = backlink;
153 new->nexthop = hop;
paul718e3742002-12-13 20:15:29 +0000154 return new;
155}
paul0c0f9cd2003-06-06 23:27:04 +0000156
pauleb3da6d2005-10-18 04:20:33 +0000157static void
Paul Jakma9c27ef92006-05-04 07:32:57 +0000158vertex_parent_free (void *p)
pauleb3da6d2005-10-18 04:20:33 +0000159{
160 XFREE (MTYPE_OSPF_VERTEX_PARENT, p);
161}
162
paul4dadc292005-05-06 21:37:42 +0000163static struct vertex *
paul718e3742002-12-13 20:15:29 +0000164ospf_vertex_new (struct ospf_lsa *lsa)
165{
166 struct vertex *new;
167
pauleb3da6d2005-10-18 04:20:33 +0000168 new = XCALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex));
paul718e3742002-12-13 20:15:29 +0000169
170 new->flags = 0;
hasso462f20d2005-02-23 11:29:02 +0000171 new->stat = &(lsa->stat);
paul718e3742002-12-13 20:15:29 +0000172 new->type = lsa->data->type;
173 new->id = lsa->data->id;
174 new->lsa = lsa->data;
pauleb3da6d2005-10-18 04:20:33 +0000175 new->children = list_new ();
176 new->parents = list_new ();
Paul Jakma9c27ef92006-05-04 07:32:57 +0000177 new->parents->del = vertex_parent_free;
pauleb3da6d2005-10-18 04:20:33 +0000178
Paul Jakma9c27ef92006-05-04 07:32:57 +0000179 listnode_add (&vertex_list, new);
180
181 if (IS_DEBUG_OSPF_EVENT)
182 zlog_debug ("%s: Created %s vertex %s", __func__,
183 new->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
184 inet_ntoa (new->lsa->id));
paul718e3742002-12-13 20:15:29 +0000185 return new;
186}
187
paul4dadc292005-05-06 21:37:42 +0000188static void
Paul Jakma9c27ef92006-05-04 07:32:57 +0000189ospf_vertex_free (void *data)
paul718e3742002-12-13 20:15:29 +0000190{
Paul Jakma9c27ef92006-05-04 07:32:57 +0000191 struct vertex *v = data;
paul7461d452005-06-13 13:57:16 +0000192
Paul Jakma9c27ef92006-05-04 07:32:57 +0000193 if (IS_DEBUG_OSPF_EVENT)
194 zlog_debug ("%s: Free %s vertex %s", __func__,
195 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
196 inet_ntoa (v->lsa->id));
pauleb3da6d2005-10-18 04:20:33 +0000197
Paul Jakma9c27ef92006-05-04 07:32:57 +0000198 /* There should be no parents potentially holding references to this vertex
199 * Children however may still be there, but presumably referenced by other
200 * vertices
pauleb3da6d2005-10-18 04:20:33 +0000201 */
Paul Jakma9c27ef92006-05-04 07:32:57 +0000202 //assert (listcount (v->parents) == 0);
pauleb3da6d2005-10-18 04:20:33 +0000203
Paul Jakma9c27ef92006-05-04 07:32:57 +0000204 if (v->children)
205 list_delete (v->children);
206 v->children = NULL;
207
208 if (v->parents)
209 list_delete (v->parents);
pauleb3da6d2005-10-18 04:20:33 +0000210 v->parents = NULL;
211
212 v->lsa = NULL;
paul7461d452005-06-13 13:57:16 +0000213
paul718e3742002-12-13 20:15:29 +0000214 XFREE (MTYPE_OSPF_VERTEX, v);
215}
216
paul4dadc292005-05-06 21:37:42 +0000217static void
hassoeb1ce602004-10-08 08:17:22 +0000218ospf_vertex_dump(const char *msg, struct vertex *v,
pauleb3da6d2005-10-18 04:20:33 +0000219 int print_parents, int print_children)
gdt630e4802004-08-31 17:28:41 +0000220{
221 if ( ! IS_DEBUG_OSPF_EVENT)
222 return;
223
pauleb3da6d2005-10-18 04:20:33 +0000224 zlog_debug("%s %s vertex %s distance %u flags %u",
gdt630e4802004-08-31 17:28:41 +0000225 msg,
226 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
227 inet_ntoa(v->lsa->id),
228 v->distance,
gdt630e4802004-08-31 17:28:41 +0000229 (unsigned int)v->flags);
230
pauleb3da6d2005-10-18 04:20:33 +0000231 if (print_parents)
gdt630e4802004-08-31 17:28:41 +0000232 {
paul1eb8ef22005-04-07 07:30:20 +0000233 struct listnode *node;
pauleb3da6d2005-10-18 04:20:33 +0000234 struct vertex_parent *vp;
paul1eb8ef22005-04-07 07:30:20 +0000235
pauleb3da6d2005-10-18 04:20:33 +0000236 for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
gdt630e4802004-08-31 17:28:41 +0000237 {
238 char buf1[BUFSIZ];
pauleb3da6d2005-10-18 04:20:33 +0000239
240 if (vp)
gdt630e4802004-08-31 17:28:41 +0000241 {
pauleb3da6d2005-10-18 04:20:33 +0000242 zlog_debug ("parent %s backlink %d nexthop %s interface %s",
243 inet_ntoa(vp->parent->lsa->id), vp->backlink,
244 inet_ntop(AF_INET, &vp->nexthop->router, buf1, BUFSIZ),
245 vp->nexthop->oi ? IF_NAME(vp->nexthop->oi) : "NULL");
gdt630e4802004-08-31 17:28:41 +0000246 }
247 }
248 }
249
250 if (print_children)
251 {
hasso52dc7ee2004-09-23 19:18:23 +0000252 struct listnode *cnode;
paul1eb8ef22005-04-07 07:30:20 +0000253 struct vertex *cv;
254
pauleb3da6d2005-10-18 04:20:33 +0000255 for (ALL_LIST_ELEMENTS_RO (v->children, cnode, cv))
paul1eb8ef22005-04-07 07:30:20 +0000256 ospf_vertex_dump(" child:", cv, 0, 0);
gdt630e4802004-08-31 17:28:41 +0000257 }
258}
259
260
261/* Add a vertex to the list of children in each of its parents. */
paul4dadc292005-05-06 21:37:42 +0000262static void
paul718e3742002-12-13 20:15:29 +0000263ospf_vertex_add_parent (struct vertex *v)
264{
pauleb3da6d2005-10-18 04:20:33 +0000265 struct vertex_parent *vp;
hasso52dc7ee2004-09-23 19:18:23 +0000266 struct listnode *node;
paul7461d452005-06-13 13:57:16 +0000267
Paul Jakma9c27ef92006-05-04 07:32:57 +0000268 assert (v && v->parents);
paul7461d452005-06-13 13:57:16 +0000269
pauleb3da6d2005-10-18 04:20:33 +0000270 for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
paul718e3742002-12-13 20:15:29 +0000271 {
pauleb3da6d2005-10-18 04:20:33 +0000272 assert (vp->parent && vp->parent->children);
paul7461d452005-06-13 13:57:16 +0000273
paul718e3742002-12-13 20:15:29 +0000274 /* No need to add two links from the same parent. */
pauleb3da6d2005-10-18 04:20:33 +0000275 if (listnode_lookup (vp->parent->children, v) == NULL)
276 listnode_add (vp->parent->children, v);
paul718e3742002-12-13 20:15:29 +0000277 }
278}
279
paul4dadc292005-05-06 21:37:42 +0000280static void
paul718e3742002-12-13 20:15:29 +0000281ospf_spf_init (struct ospf_area *area)
282{
283 struct vertex *v;
Paul Jakma9c27ef92006-05-04 07:32:57 +0000284
paul718e3742002-12-13 20:15:29 +0000285 /* Create root node. */
286 v = ospf_vertex_new (area->router_lsa_self);
Paul Jakmabd34fb32007-02-26 17:14:48 +0000287
paul718e3742002-12-13 20:15:29 +0000288 area->spf = v;
289
290 /* Reset ABR and ASBR router counts. */
291 area->abr_count = 0;
292 area->asbr_count = 0;
293}
294
pauld355bfa2004-04-08 07:43:45 +0000295/* return index of link back to V from W, or -1 if no link found */
paul4dadc292005-05-06 21:37:42 +0000296static int
paul718e3742002-12-13 20:15:29 +0000297ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v)
298{
hassoeb1ce602004-10-08 08:17:22 +0000299 unsigned int i, length;
paul718e3742002-12-13 20:15:29 +0000300 struct router_lsa *rl;
301 struct network_lsa *nl;
302
303 /* In case of W is Network LSA. */
304 if (w->type == OSPF_NETWORK_LSA)
305 {
306 if (v->type == OSPF_NETWORK_LSA)
pauld355bfa2004-04-08 07:43:45 +0000307 return -1;
paul718e3742002-12-13 20:15:29 +0000308
309 nl = (struct network_lsa *) w;
310 length = (ntohs (w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;
paul0c0f9cd2003-06-06 23:27:04 +0000311
paul718e3742002-12-13 20:15:29 +0000312 for (i = 0; i < length; i++)
313 if (IPV4_ADDR_SAME (&nl->routers[i], &v->id))
pauld355bfa2004-04-08 07:43:45 +0000314 return i;
315 return -1;
paul718e3742002-12-13 20:15:29 +0000316 }
317
318 /* In case of W is Router LSA. */
319 if (w->type == OSPF_ROUTER_LSA)
320 {
321 rl = (struct router_lsa *) w;
322
323 length = ntohs (w->length);
324
325 for (i = 0;
paul0c0f9cd2003-06-06 23:27:04 +0000326 i < ntohs (rl->links) && length >= sizeof (struct router_lsa);
327 i++, length -= 12)
paul718e3742002-12-13 20:15:29 +0000328 {
329 switch (rl->link[i].type)
330 {
331 case LSA_LINK_TYPE_POINTOPOINT:
332 case LSA_LINK_TYPE_VIRTUALLINK:
333 /* Router LSA ID. */
334 if (v->type == OSPF_ROUTER_LSA &&
335 IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
336 {
pauld355bfa2004-04-08 07:43:45 +0000337 return i;
paul718e3742002-12-13 20:15:29 +0000338 }
339 break;
340 case LSA_LINK_TYPE_TRANSIT:
341 /* Network LSA ID. */
342 if (v->type == OSPF_NETWORK_LSA &&
343 IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
344 {
pauld355bfa2004-04-08 07:43:45 +0000345 return i;
paul0c0f9cd2003-06-06 23:27:04 +0000346 }
paul718e3742002-12-13 20:15:29 +0000347 break;
348 case LSA_LINK_TYPE_STUB:
pauleb3da6d2005-10-18 04:20:33 +0000349 /* Stub can't lead anywhere, carry on */
paul718e3742002-12-13 20:15:29 +0000350 continue;
351 default:
352 break;
353 }
354 }
355 }
pauld355bfa2004-04-08 07:43:45 +0000356 return -1;
paul718e3742002-12-13 20:15:29 +0000357}
358
paul718e3742002-12-13 20:15:29 +0000359#define ROUTER_LSA_MIN_SIZE 12
360#define ROUTER_LSA_TOS_SIZE 4
361
gdt630e4802004-08-31 17:28:41 +0000362/* Find the next link after prev_link from v to w. If prev_link is
363 * NULL, return the first link from v to w. Ignore stub and virtual links;
364 * these link types will never be returned.
365 */
paul4dadc292005-05-06 21:37:42 +0000366static struct router_lsa_link *
paul718e3742002-12-13 20:15:29 +0000367ospf_get_next_link (struct vertex *v, struct vertex *w,
paul0c0f9cd2003-06-06 23:27:04 +0000368 struct router_lsa_link *prev_link)
paul718e3742002-12-13 20:15:29 +0000369{
370 u_char *p;
371 u_char *lim;
372 struct router_lsa_link *l;
373
374 if (prev_link == NULL)
gdt630e4802004-08-31 17:28:41 +0000375 p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
paul718e3742002-12-13 20:15:29 +0000376 else
377 {
paul0c0f9cd2003-06-06 23:27:04 +0000378 p = (u_char *) prev_link;
paul718e3742002-12-13 20:15:29 +0000379 p += (ROUTER_LSA_MIN_SIZE +
380 (prev_link->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
381 }
paul0c0f9cd2003-06-06 23:27:04 +0000382
paul718e3742002-12-13 20:15:29 +0000383 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
384
385 while (p < lim)
386 {
387 l = (struct router_lsa_link *) p;
388
paul0c0f9cd2003-06-06 23:27:04 +0000389 p += (ROUTER_LSA_MIN_SIZE + (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
paul718e3742002-12-13 20:15:29 +0000390
391 if (l->m[0].type == LSA_LINK_TYPE_STUB)
392 continue;
393
394 /* Defer NH calculation via VLs until summaries from
395 transit areas area confidered */
396
397 if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
paul0c0f9cd2003-06-06 23:27:04 +0000398 continue;
paul718e3742002-12-13 20:15:29 +0000399
400 if (IPV4_ADDR_SAME (&l->link_id, &w->id))
paul0c0f9cd2003-06-06 23:27:04 +0000401 return l;
paul718e3742002-12-13 20:15:29 +0000402 }
403
404 return NULL;
405}
406
pauleb3da6d2005-10-18 04:20:33 +0000407static void
408ospf_spf_flush_parents (struct vertex *w)
409{
410 struct vertex_parent *vp;
411 struct listnode *ln, *nn;
412
413 /* delete the existing nexthops */
414 for (ALL_LIST_ELEMENTS (w->parents, ln, nn, vp))
415 {
416 list_delete_node (w->parents, ln);
417 vertex_parent_free (vp);
418 }
419}
420
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000421/*
422 * Consider supplied next-hop for inclusion to the supplied list of
423 * equal-cost next-hops, adjust list as neccessary.
424 */
425static void
426ospf_spf_add_parent (struct vertex *v, struct vertex *w,
427 struct vertex_nexthop *newhop,
Paul Jakmabd34fb32007-02-26 17:14:48 +0000428 unsigned int distance)
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000429{
430 struct vertex_parent *vp;
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000431
Paul Jakma08d3d5b2007-05-07 16:38:35 +0000432 /* we must have a newhop, and a distance */
Paul Jakmabd34fb32007-02-26 17:14:48 +0000433 assert (v && w && newhop);
Paul Jakma08d3d5b2007-05-07 16:38:35 +0000434 assert (distance);
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000435
Paul Jakma08d3d5b2007-05-07 16:38:35 +0000436 /* IFF w has already been assigned a distance, then we shouldn't get here
437 * unless callers have determined V(l)->W is shortest / equal-shortest
438 * path (0 is a special case distance (no distance yet assigned)).
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000439 */
Paul Jakma08d3d5b2007-05-07 16:38:35 +0000440 if (w->distance)
441 assert (distance <= w->distance);
442 else
443 w->distance = distance;
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000444
Paul Jakmab75ae992007-03-23 11:17:28 +0000445 if (IS_DEBUG_OSPF_EVENT)
446 {
447 char buf[2][INET_ADDRSTRLEN];
448 zlog_debug ("%s: Adding %s as parent of %s",
449 __func__,
450 inet_ntop(AF_INET, &v->lsa->id, buf[0], sizeof(buf[0])),
451 inet_ntop(AF_INET, &w->lsa->id, buf[1], sizeof(buf[1])));
452 }
453
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000454 /* Adding parent for a new, better path: flush existing parents from W. */
Paul Jakmabd34fb32007-02-26 17:14:48 +0000455 if (distance < w->distance)
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000456 {
Paul Jakmab75ae992007-03-23 11:17:28 +0000457 if (IS_DEBUG_OSPF_EVENT)
458 zlog_debug ("%s: distance %d better than %d, flushing existing parents",
459 __func__, distance, w->distance);
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000460 ospf_spf_flush_parents (w);
Paul Jakmabd34fb32007-02-26 17:14:48 +0000461 w->distance = distance;
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000462 }
463
464 /* new parent is <= existing parents, add it to parent list */
465 vp = vertex_parent_new (v, ospf_lsa_has_link (w->lsa, v->lsa), newhop);
466 listnode_add (w->parents, vp);
467
468 return;
469}
470
gdt630e4802004-08-31 17:28:41 +0000471/* 16.1.1. Calculate nexthop from root through V (parent) to
Paul Jakmabd34fb32007-02-26 17:14:48 +0000472 * vertex W (destination), with given distance from root->W.
pauleb3da6d2005-10-18 04:20:33 +0000473 *
474 * The link must be supplied if V is the root vertex. In all other cases
475 * it may be NULL.
Paul Jakmabd34fb32007-02-26 17:14:48 +0000476 *
477 * Note that this function may fail, hence the state of the destination
478 * vertex, W, should /not/ be modified in a dependent manner until
479 * this function returns. This function will update the W vertex with the
480 * provided distance as appropriate.
gdt630e4802004-08-31 17:28:41 +0000481 */
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000482static unsigned int
pauleb3da6d2005-10-18 04:20:33 +0000483ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
Paul Jakmabd34fb32007-02-26 17:14:48 +0000484 struct vertex *w, struct router_lsa_link *l,
485 unsigned int distance)
paul718e3742002-12-13 20:15:29 +0000486{
paul1eb8ef22005-04-07 07:30:20 +0000487 struct listnode *node, *nnode;
pauleb3da6d2005-10-18 04:20:33 +0000488 struct vertex_nexthop *nh;
489 struct vertex_parent *vp;
paul718e3742002-12-13 20:15:29 +0000490 struct ospf_interface *oi = NULL;
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000491 unsigned int added = 0;
paul0c0f9cd2003-06-06 23:27:04 +0000492
paul718e3742002-12-13 20:15:29 +0000493 if (IS_DEBUG_OSPF_EVENT)
gdt630e4802004-08-31 17:28:41 +0000494 {
ajs2a42e282004-12-08 18:43:03 +0000495 zlog_debug ("ospf_nexthop_calculation(): Start");
gdt630e4802004-08-31 17:28:41 +0000496 ospf_vertex_dump("V (parent):", v, 1, 1);
497 ospf_vertex_dump("W (dest) :", w, 1, 1);
Paul Jakmabd34fb32007-02-26 17:14:48 +0000498 zlog_debug ("V->W distance: %d", distance);
gdt630e4802004-08-31 17:28:41 +0000499 }
paul718e3742002-12-13 20:15:29 +0000500
paul718e3742002-12-13 20:15:29 +0000501 if (v == area->spf)
Paul Jakma9c27ef92006-05-04 07:32:57 +0000502 {
gdt630e4802004-08-31 17:28:41 +0000503 /* 16.1.1 para 4. In the first case, the parent vertex (V) is the
504 root (the calculating router itself). This means that the
505 destination is either a directly connected network or directly
506 connected router. The outgoing interface in this case is simply
507 the OSPF interface connecting to the destination network/router.
508 */
509
paul718e3742002-12-13 20:15:29 +0000510 if (w->type == OSPF_VERTEX_ROUTER)
paul0c0f9cd2003-06-06 23:27:04 +0000511 {
pauleb3da6d2005-10-18 04:20:33 +0000512 /* l is a link from v to w
513 * l2 will be link from w to v
514 */
515 struct router_lsa_link *l2 = NULL;
516
517 /* we *must* be supplied with the link data */
518 assert (l != NULL);
519
520 if (IS_DEBUG_OSPF_EVENT)
paul0c0f9cd2003-06-06 23:27:04 +0000521 {
pauleb3da6d2005-10-18 04:20:33 +0000522 char buf1[BUFSIZ];
523 char buf2[BUFSIZ];
524
525 zlog_debug("ospf_nexthop_calculation(): considering link "
526 "type %d link_id %s link_data %s",
527 l->m[0].type,
528 inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
529 inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
530 }
paul0c0f9cd2003-06-06 23:27:04 +0000531
pauleb3da6d2005-10-18 04:20:33 +0000532 if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
533 {
534 /* If the destination is a router which connects to
535 the calculating router via a Point-to-MultiPoint
536 network, the destination's next hop IP address(es)
537 can be determined by examining the destination's
538 router-LSA: each link pointing back to the
539 calculating router and having a Link Data field
540 belonging to the Point-to-MultiPoint network
541 provides an IP address of the next hop router.
gdt630e4802004-08-31 17:28:41 +0000542
pauleb3da6d2005-10-18 04:20:33 +0000543 At this point l is a link from V to W, and V is the
544 root ("us"). Find the local interface associated
545 with l (its address is in l->link_data). If it
546 is a point-to-multipoint interface, then look through
547 the links in the opposite direction (W to V). If
548 any of them have an address that lands within the
549 subnet declared by the PtMP link, then that link
550 is a constituent of the PtMP link, and its address is
551 a nexthop address for V.
552 */
553 oi = ospf_if_is_configured (area->ospf, &l->link_data);
554 if (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
paul0c0f9cd2003-06-06 23:27:04 +0000555 {
pauleb3da6d2005-10-18 04:20:33 +0000556 struct prefix_ipv4 la;
gdt630e4802004-08-31 17:28:41 +0000557
pauleb3da6d2005-10-18 04:20:33 +0000558 la.family = AF_INET;
559 la.prefixlen = oi->address->prefixlen;
560
561 /* V links to W on PtMP interface
562 - find the interface address on W */
563 while ((l2 = ospf_get_next_link (w, v, l2)))
paul0c0f9cd2003-06-06 23:27:04 +0000564 {
pauleb3da6d2005-10-18 04:20:33 +0000565 la.prefix = l2->link_data;
gdt630e4802004-08-31 17:28:41 +0000566
pauleb3da6d2005-10-18 04:20:33 +0000567 if (prefix_cmp ((struct prefix *) &la,
568 oi->address) == 0)
569 /* link_data is on our PtMP network */
570 break;
paul0c0f9cd2003-06-06 23:27:04 +0000571 }
pauleb3da6d2005-10-18 04:20:33 +0000572 } /* end l is on point-to-multipoint link */
573 else
574 {
575 /* l is a regular point-to-point link.
576 Look for a link from W to V.
577 */
578 while ((l2 = ospf_get_next_link (w, v, l2)))
paul0c0f9cd2003-06-06 23:27:04 +0000579 {
pauleb3da6d2005-10-18 04:20:33 +0000580 oi = ospf_if_is_configured (area->ospf,
581 &(l2->link_data));
582
583 if (oi == NULL)
584 continue;
585
586 if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
587 &l->link_data))
588 continue;
589
590 break;
paul0c0f9cd2003-06-06 23:27:04 +0000591 }
pauleb3da6d2005-10-18 04:20:33 +0000592 }
593
594 if (oi && l2)
595 {
596 /* found all necessary info to build nexthop */
597 nh = vertex_nexthop_new ();
598 nh->oi = oi;
599 nh->router = l2->link_data;
Paul Jakmabd34fb32007-02-26 17:14:48 +0000600 ospf_spf_add_parent (v, w, nh, distance);
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000601 return 1;
pauleb3da6d2005-10-18 04:20:33 +0000602 }
603 else
Paul Jakma9c27ef92006-05-04 07:32:57 +0000604 zlog_info("ospf_nexthop_calculation(): "
605 "could not determine nexthop for link");
pauleb3da6d2005-10-18 04:20:33 +0000606 } /* end point-to-point link from V to W */
Paul Jakma9c27ef92006-05-04 07:32:57 +0000607 else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
608 {
609 struct ospf_vl_data *vl_data;
610
611 /* VLink implementation limitations:
612 * a) vl_data can only reference one nexthop, so no ECMP
613 * to backbone through VLinks. Though transit-area
614 * summaries may be considered, and those can be ECMP.
615 * b) We can only use /one/ VLink, even if multiple ones
616 * exist this router through multiple transit-areas.
617 */
618 vl_data = ospf_vl_lookup (area->ospf, NULL, l->link_id);
619
620 if (vl_data
621 && CHECK_FLAG (vl_data->flags, OSPF_VL_FLAG_APPROVED))
622 {
623 nh = vertex_nexthop_new ();
624 nh->oi = vl_data->nexthop.oi;
625 nh->router = vl_data->nexthop.router;
Paul Jakmabd34fb32007-02-26 17:14:48 +0000626 ospf_spf_add_parent (v, w, nh, distance);
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000627 return 1;
Paul Jakma9c27ef92006-05-04 07:32:57 +0000628 }
629 else
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000630 zlog_info("ospf_nexthop_calculation(): "
631 "vl_data for VL link not found");
Paul Jakma9c27ef92006-05-04 07:32:57 +0000632 } /* end virtual-link from V to W */
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000633 return 0;
gdt630e4802004-08-31 17:28:41 +0000634 } /* end W is a Router vertex */
paul718e3742002-12-13 20:15:29 +0000635 else
paul0c0f9cd2003-06-06 23:27:04 +0000636 {
pauleb3da6d2005-10-18 04:20:33 +0000637 assert(w->type == OSPF_VERTEX_NETWORK);
638 oi = ospf_if_is_configured (area->ospf, &(l->link_data));
639 if (oi)
paul0c0f9cd2003-06-06 23:27:04 +0000640 {
pauleb3da6d2005-10-18 04:20:33 +0000641 nh = vertex_nexthop_new ();
642 nh->oi = oi;
643 nh->router.s_addr = 0;
Paul Jakmabd34fb32007-02-26 17:14:48 +0000644 ospf_spf_add_parent (v, w, nh, distance);
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000645 return 1;
paul0c0f9cd2003-06-06 23:27:04 +0000646 }
647 }
Paul Jakma9c27ef92006-05-04 07:32:57 +0000648 zlog_info("ospf_nexthop_calculation(): "
649 "Unknown attached link");
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000650 return 0;
gdt630e4802004-08-31 17:28:41 +0000651 } /* end V is the root */
gdt630e4802004-08-31 17:28:41 +0000652 /* Check if W's parent is a network connected to root. */
paul718e3742002-12-13 20:15:29 +0000653 else if (v->type == OSPF_VERTEX_NETWORK)
654 {
gdt630e4802004-08-31 17:28:41 +0000655 /* See if any of V's parents are the root. */
pauleb3da6d2005-10-18 04:20:33 +0000656 for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
paul718e3742002-12-13 20:15:29 +0000657 {
pauleb3da6d2005-10-18 04:20:33 +0000658 if (vp->parent == area->spf) /* connects to root? */
gdt630e4802004-08-31 17:28:41 +0000659 {
660 /* 16.1.1 para 5. ...the parent vertex is a network that
661 * directly connects the calculating router to the destination
662 * router. The list of next hops is then determined by
663 * examining the destination's router-LSA...
664 */
665
666 assert(w->type == OSPF_VERTEX_ROUTER);
paul0c0f9cd2003-06-06 23:27:04 +0000667 while ((l = ospf_get_next_link (w, v, l)))
668 {
gdt630e4802004-08-31 17:28:41 +0000669 /* ...For each link in the router-LSA that points back to the
670 * parent network, the link's Link Data field provides the IP
671 * address of a next hop router. The outgoing interface to
672 * use can then be derived from the next hop IP address (or
673 * it can be inherited from the parent network).
674 */
pauleb3da6d2005-10-18 04:20:33 +0000675 nh = vertex_nexthop_new ();
676 nh->oi = vp->nexthop->oi;
677 nh->router = l->link_data;
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000678 added = 1;
Paul Jakmabd34fb32007-02-26 17:14:48 +0000679 ospf_spf_add_parent (v, w, nh, distance);
paul0c0f9cd2003-06-06 23:27:04 +0000680 }
paul0c0f9cd2003-06-06 23:27:04 +0000681 }
paul718e3742002-12-13 20:15:29 +0000682 }
Paul Jakma85ef7842007-03-23 11:19:08 +0000683 if (added)
684 return added;
paul718e3742002-12-13 20:15:29 +0000685 }
686
gdt630e4802004-08-31 17:28:41 +0000687 /* 16.1.1 para 4. If there is at least one intervening router in the
688 * current shortest path between the destination and the root, the
689 * destination simply inherits the set of next hops from the
690 * parent.
691 */
Paul Jakmab75ae992007-03-23 11:17:28 +0000692 if (IS_DEBUG_OSPF_EVENT)
693 zlog_debug ("%s: Intervening routers, adding parent(s)", __func__);
694
pauleb3da6d2005-10-18 04:20:33 +0000695 for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000696 {
697 added = 1;
Paul Jakmabd34fb32007-02-26 17:14:48 +0000698 ospf_spf_add_parent (v, w, vp->nexthop, distance);
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000699 }
Paul Jakma9c27ef92006-05-04 07:32:57 +0000700
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000701 return added;
paul718e3742002-12-13 20:15:29 +0000702}
703
gdt630e4802004-08-31 17:28:41 +0000704/* RFC2328 Section 16.1 (2).
705 * v is on the SPF tree. Examine the links in v's LSA. Update the list
706 * of candidates with any vertices not already on the list. If a lower-cost
707 * path is found to a vertex already on the candidate list, store the new cost.
708 */
paul4dadc292005-05-06 21:37:42 +0000709static void
paul718e3742002-12-13 20:15:29 +0000710ospf_spf_next (struct vertex *v, struct ospf_area *area,
hasso462f20d2005-02-23 11:29:02 +0000711 struct pqueue * candidate)
paul718e3742002-12-13 20:15:29 +0000712{
713 struct ospf_lsa *w_lsa = NULL;
paul718e3742002-12-13 20:15:29 +0000714 u_char *p;
715 u_char *lim;
716 struct router_lsa_link *l = NULL;
717 struct in_addr *r;
paul718e3742002-12-13 20:15:29 +0000718 int type = 0;
719
720 /* If this is a router-LSA, and bit V of the router-LSA (see Section
721 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
722 if (v->type == OSPF_VERTEX_ROUTER)
723 {
724 if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa))
725 area->transit = OSPF_TRANSIT_TRUE;
726 }
Paul Jakmab75ae992007-03-23 11:17:28 +0000727
728 if (IS_DEBUG_OSPF_EVENT)
729 zlog_debug ("%s: Next vertex of %s vertex %s",
730 __func__,
731 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
732 inet_ntoa(v->lsa->id));
733
paul718e3742002-12-13 20:15:29 +0000734 p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
paul0c0f9cd2003-06-06 23:27:04 +0000735 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
736
paul718e3742002-12-13 20:15:29 +0000737 while (p < lim)
738 {
pauleb3da6d2005-10-18 04:20:33 +0000739 struct vertex *w;
740 unsigned int distance;
pauld355bfa2004-04-08 07:43:45 +0000741
paul718e3742002-12-13 20:15:29 +0000742 /* In case of V is Router-LSA. */
743 if (v->lsa->type == OSPF_ROUTER_LSA)
744 {
745 l = (struct router_lsa_link *) p;
746
paul0c0f9cd2003-06-06 23:27:04 +0000747 p += (ROUTER_LSA_MIN_SIZE +
paul718e3742002-12-13 20:15:29 +0000748 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
749
750 /* (a) If this is a link to a stub network, examine the next
751 link in V's LSA. Links to stub networks will be
752 considered in the second stage of the shortest path
753 calculation. */
754 if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
755 continue;
Paul Jakma08d3d5b2007-05-07 16:38:35 +0000756
757 /* Infinite distance links shouldn't be followed, except
758 * for local links (a stub-routed router still wants to
759 * calculate tree, so must follow its own links).
760 */
761 if ((v != area->spf) && l->m[0].metric >= OSPF_OUTPUT_COST_INFINITE)
762 continue;
paul718e3742002-12-13 20:15:29 +0000763
764 /* (b) Otherwise, W is a transit vertex (router or transit
765 network). Look up the vertex W's LSA (router-LSA or
766 network-LSA) in Area A's link state database. */
767 switch (type)
768 {
769 case LSA_LINK_TYPE_POINTOPOINT:
770 case LSA_LINK_TYPE_VIRTUALLINK:
771 if (type == LSA_LINK_TYPE_VIRTUALLINK)
paul0c0f9cd2003-06-06 23:27:04 +0000772 {
773 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +0000774 zlog_debug ("looking up LSA through VL: %s",
paul0c0f9cd2003-06-06 23:27:04 +0000775 inet_ntoa (l->link_id));
776 }
paul718e3742002-12-13 20:15:29 +0000777
778 w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id,
779 l->link_id);
780 if (w_lsa)
paul0c0f9cd2003-06-06 23:27:04 +0000781 {
782 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +0000783 zlog_debug ("found Router LSA %s", inet_ntoa (l->link_id));
paul0c0f9cd2003-06-06 23:27:04 +0000784 }
paul718e3742002-12-13 20:15:29 +0000785 break;
786 case LSA_LINK_TYPE_TRANSIT:
paul0c0f9cd2003-06-06 23:27:04 +0000787 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +0000788 zlog_debug ("Looking up Network LSA, ID: %s",
paul0c0f9cd2003-06-06 23:27:04 +0000789 inet_ntoa (l->link_id));
paul718e3742002-12-13 20:15:29 +0000790 w_lsa = ospf_lsa_lookup_by_id (area, OSPF_NETWORK_LSA,
paul0c0f9cd2003-06-06 23:27:04 +0000791 l->link_id);
paul718e3742002-12-13 20:15:29 +0000792 if (w_lsa)
paul0c0f9cd2003-06-06 23:27:04 +0000793 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +0000794 zlog_debug ("found the LSA");
paul718e3742002-12-13 20:15:29 +0000795 break;
796 default:
paul0c0f9cd2003-06-06 23:27:04 +0000797 zlog_warn ("Invalid LSA link type %d", type);
paul718e3742002-12-13 20:15:29 +0000798 continue;
799 }
800 }
801 else
802 {
803 /* In case of V is Network-LSA. */
paul0c0f9cd2003-06-06 23:27:04 +0000804 r = (struct in_addr *) p;
paul718e3742002-12-13 20:15:29 +0000805 p += sizeof (struct in_addr);
806
807 /* Lookup the vertex W's LSA. */
808 w_lsa = ospf_lsa_lookup_by_id (area, OSPF_ROUTER_LSA, *r);
Paul Jakmab75ae992007-03-23 11:17:28 +0000809 if (w_lsa)
810 {
811 if (IS_DEBUG_OSPF_EVENT)
812 zlog_debug ("found Router LSA %s", inet_ntoa (w_lsa->data->id));
813 }
paul718e3742002-12-13 20:15:29 +0000814 }
815
816 /* (b cont.) If the LSA does not exist, or its LS age is equal
817 to MaxAge, or it does not have a link back to vertex V,
818 examine the next link in V's LSA.[23] */
819 if (w_lsa == NULL)
Paul Jakmab75ae992007-03-23 11:17:28 +0000820 {
821 if (IS_DEBUG_OSPF_EVENT)
822 zlog_debug ("No LSA found");
823 continue;
824 }
paul718e3742002-12-13 20:15:29 +0000825
826 if (IS_LSA_MAXAGE (w_lsa))
Paul Jakmab75ae992007-03-23 11:17:28 +0000827 {
828 if (IS_DEBUG_OSPF_EVENT)
829 zlog_debug ("LSA is MaxAge");
830 continue;
831 }
paul718e3742002-12-13 20:15:29 +0000832
pauleb3da6d2005-10-18 04:20:33 +0000833 if (ospf_lsa_has_link (w_lsa->data, v->lsa) < 0 )
paul718e3742002-12-13 20:15:29 +0000834 {
paul0c0f9cd2003-06-06 23:27:04 +0000835 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +0000836 zlog_debug ("The LSA doesn't have a link back");
paul718e3742002-12-13 20:15:29 +0000837 continue;
838 }
839
840 /* (c) If vertex W is already on the shortest-path tree, examine
841 the next link in the LSA. */
hasso462f20d2005-02-23 11:29:02 +0000842 if (w_lsa->stat == LSA_SPF_IN_SPFTREE)
843 {
844 if (IS_DEBUG_OSPF_EVENT)
845 zlog_debug ("The LSA is already in SPF");
846 continue;
847 }
paul718e3742002-12-13 20:15:29 +0000848
849 /* (d) Calculate the link state cost D of the resulting path
850 from the root to vertex W. D is equal to the sum of the link
851 state cost of the (already calculated) shortest path to
852 vertex V and the advertised cost of the link between vertices
853 V and W. If D is: */
854
paul718e3742002-12-13 20:15:29 +0000855 /* calculate link cost D. */
856 if (v->lsa->type == OSPF_ROUTER_LSA)
pauleb3da6d2005-10-18 04:20:33 +0000857 distance = v->distance + ntohs (l->m[0].metric);
gdt630e4802004-08-31 17:28:41 +0000858 else /* v is not a Router-LSA */
pauleb3da6d2005-10-18 04:20:33 +0000859 distance = v->distance;
paul718e3742002-12-13 20:15:29 +0000860
861 /* Is there already vertex W in candidate list? */
hasso462f20d2005-02-23 11:29:02 +0000862 if (w_lsa->stat == LSA_SPF_NOT_EXPLORED)
863 {
pauleb3da6d2005-10-18 04:20:33 +0000864 /* prepare vertex W. */
865 w = ospf_vertex_new (w_lsa);
866
hasso462f20d2005-02-23 11:29:02 +0000867 /* Calculate nexthop to W. */
Paul Jakmabd34fb32007-02-26 17:14:48 +0000868 if (ospf_nexthop_calculation (area, v, w, l, distance))
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000869 pqueue_enqueue (w, candidate);
Paul Jakmab75ae992007-03-23 11:17:28 +0000870 else if (IS_DEBUG_OSPF_EVENT)
871 zlog_debug ("Nexthop Calc failed");
hasso462f20d2005-02-23 11:29:02 +0000872 }
873 else if (w_lsa->stat >= 0)
874 {
875 /* Get the vertex from candidates. */
pauleb3da6d2005-10-18 04:20:33 +0000876 w = candidate->array[w_lsa->stat];
paul718e3742002-12-13 20:15:29 +0000877
hasso462f20d2005-02-23 11:29:02 +0000878 /* if D is greater than. */
pauleb3da6d2005-10-18 04:20:33 +0000879 if (w->distance < distance)
paul718e3742002-12-13 20:15:29 +0000880 {
paul718e3742002-12-13 20:15:29 +0000881 continue;
882 }
hasso462f20d2005-02-23 11:29:02 +0000883 /* equal to. */
pauleb3da6d2005-10-18 04:20:33 +0000884 else if (w->distance == distance)
paul718e3742002-12-13 20:15:29 +0000885 {
pauleb3da6d2005-10-18 04:20:33 +0000886 /* Found an equal-cost path to W.
887 * Calculate nexthop of to W from V. */
Paul Jakmabd34fb32007-02-26 17:14:48 +0000888 ospf_nexthop_calculation (area, v, w, l, distance);
paul718e3742002-12-13 20:15:29 +0000889 }
hasso462f20d2005-02-23 11:29:02 +0000890 /* less than. */
891 else
paul718e3742002-12-13 20:15:29 +0000892 {
Paul Jakmabc20c1a2007-01-24 14:51:51 +0000893 /* Found a lower-cost path to W.
894 * nexthop_calculation is conditional, if it finds
895 * valid nexthop it will call spf_add_parents, which
896 * will flush the old parents
897 */
Paul Jakmabd34fb32007-02-26 17:14:48 +0000898 if (ospf_nexthop_calculation (area, v, w, l, distance))
Paul Jakma7591d8b2007-08-06 18:52:45 +0000899 /* Decrease the key of the node in the heap.
900 * trickle-sort it up towards root, just in case this
901 * node should now be the new root due the cost change.
Paul Jakmae95537f2007-08-07 16:22:05 +0000902 * (next pqueu_{de,en}queue will fully re-heap the queue).
Paul Jakma7591d8b2007-08-06 18:52:45 +0000903 */
904 trickle_up (w_lsa->stat, candidate);
paul718e3742002-12-13 20:15:29 +0000905 }
gdt630e4802004-08-31 17:28:41 +0000906 } /* end W is already on the candidate list */
907 } /* end loop over the links in V's LSA */
paul718e3742002-12-13 20:15:29 +0000908}
909
paul4dadc292005-05-06 21:37:42 +0000910static void
paul718e3742002-12-13 20:15:29 +0000911ospf_spf_dump (struct vertex *v, int i)
912{
hasso52dc7ee2004-09-23 19:18:23 +0000913 struct listnode *cnode;
914 struct listnode *nnode;
pauleb3da6d2005-10-18 04:20:33 +0000915 struct vertex_parent *parent;
paul718e3742002-12-13 20:15:29 +0000916
917 if (v->type == OSPF_VERTEX_ROUTER)
918 {
919 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +0000920 zlog_debug ("SPF Result: %d [R] %s", i, inet_ntoa (v->lsa->id));
paul718e3742002-12-13 20:15:29 +0000921 }
922 else
923 {
924 struct network_lsa *lsa = (struct network_lsa *) v->lsa;
925 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +0000926 zlog_debug ("SPF Result: %d [N] %s/%d", i, inet_ntoa (v->lsa->id),
paul0c0f9cd2003-06-06 23:27:04 +0000927 ip_masklen (lsa->mask));
gdt630e4802004-08-31 17:28:41 +0000928 }
paul718e3742002-12-13 20:15:29 +0000929
paul1eb8ef22005-04-07 07:30:20 +0000930 if (IS_DEBUG_OSPF_EVENT)
pauleb3da6d2005-10-18 04:20:33 +0000931 for (ALL_LIST_ELEMENTS_RO (v->parents, nnode, parent))
932 {
933 zlog_debug (" nexthop %p %s %s",
934 parent->nexthop,
935 inet_ntoa (parent->nexthop->router),
936 parent->nexthop->oi ? IF_NAME(parent->nexthop->oi)
937 : "NULL");
938 }
paul718e3742002-12-13 20:15:29 +0000939
940 i++;
941
pauleb3da6d2005-10-18 04:20:33 +0000942 for (ALL_LIST_ELEMENTS_RO (v->children, cnode, v))
paul1eb8ef22005-04-07 07:30:20 +0000943 ospf_spf_dump (v, i);
paul718e3742002-12-13 20:15:29 +0000944}
945
946/* Second stage of SPF calculation. */
paul4dadc292005-05-06 21:37:42 +0000947static void
paul0c0f9cd2003-06-06 23:27:04 +0000948ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v,
paul718e3742002-12-13 20:15:29 +0000949 struct route_table *rt)
950{
paul1eb8ef22005-04-07 07:30:20 +0000951 struct listnode *cnode, *cnnode;
paul718e3742002-12-13 20:15:29 +0000952 struct vertex *child;
953
954 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +0000955 zlog_debug ("ospf_process_stub():processing stubs for area %s",
paul0c0f9cd2003-06-06 23:27:04 +0000956 inet_ntoa (area->area_id));
paul718e3742002-12-13 20:15:29 +0000957 if (v->type == OSPF_VERTEX_ROUTER)
958 {
959 u_char *p;
960 u_char *lim;
961 struct router_lsa_link *l;
962 struct router_lsa *rlsa;
963
paul0c0f9cd2003-06-06 23:27:04 +0000964 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +0000965 zlog_debug ("ospf_process_stubs():processing router LSA, id: %s",
paul0c0f9cd2003-06-06 23:27:04 +0000966 inet_ntoa (v->lsa->id));
paul718e3742002-12-13 20:15:29 +0000967 rlsa = (struct router_lsa *) v->lsa;
968
969
paul0c0f9cd2003-06-06 23:27:04 +0000970 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +0000971 zlog_debug ("ospf_process_stubs(): we have %d links to process",
paul0c0f9cd2003-06-06 23:27:04 +0000972 ntohs (rlsa->links));
gdt630e4802004-08-31 17:28:41 +0000973 p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
paul718e3742002-12-13 20:15:29 +0000974 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
975
976 while (p < lim)
977 {
978 l = (struct router_lsa_link *) p;
979
980 p += (ROUTER_LSA_MIN_SIZE +
981 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
982
983 if (l->m[0].type == LSA_LINK_TYPE_STUB)
Joakim Tjernlund910e2702008-08-20 14:24:39 +0200984 {
985 /* PtP links with /32 masks adds host routes to the remote host,
986 see RFC 2328, 12.4.1.1, Option 1.
987 Make sure that such routes are ignored */
988 /* XXX: Change to breadth-first and avoid the lookup */
989 if (l->link_data.s_addr == 0xffffffff &&
990 ospf_if_lookup_by_local_addr (area->ospf, NULL, l->link_id))
991 {
992 if (IS_DEBUG_OSPF_EVENT)
993 zlog_debug ("ospf_spf_process_stubs(): ignoring host route "
994 "%s/32 to self.", inet_ntoa (l->link_id));
995 continue;
996 }
997 ospf_intra_add_stub (rt, l, v, area);
998 }
paul718e3742002-12-13 20:15:29 +0000999 }
1000 }
1001
gdt630e4802004-08-31 17:28:41 +00001002 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1, 1);
paul718e3742002-12-13 20:15:29 +00001003
pauleb3da6d2005-10-18 04:20:33 +00001004 for (ALL_LIST_ELEMENTS (v->children, cnode, cnnode, child))
paul718e3742002-12-13 20:15:29 +00001005 {
paul718e3742002-12-13 20:15:29 +00001006 if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED))
paul0c0f9cd2003-06-06 23:27:04 +00001007 continue;
paul718e3742002-12-13 20:15:29 +00001008
1009 ospf_spf_process_stubs (area, child, rt);
1010
1011 SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED);
1012 }
1013}
1014
1015void
1016ospf_rtrs_free (struct route_table *rtrs)
1017{
1018 struct route_node *rn;
hasso52dc7ee2004-09-23 19:18:23 +00001019 struct list *or_list;
paul1eb8ef22005-04-07 07:30:20 +00001020 struct ospf_route *or;
1021 struct listnode *node, *nnode;
paul718e3742002-12-13 20:15:29 +00001022
1023 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +00001024 zlog_debug ("Route: Router Routing Table free");
paul718e3742002-12-13 20:15:29 +00001025
1026 for (rn = route_top (rtrs); rn; rn = route_next (rn))
1027 if ((or_list = rn->info) != NULL)
1028 {
paul1eb8ef22005-04-07 07:30:20 +00001029 for (ALL_LIST_ELEMENTS (or_list, node, nnode, or))
1030 ospf_route_free (or);
paul718e3742002-12-13 20:15:29 +00001031
paul0c0f9cd2003-06-06 23:27:04 +00001032 list_delete (or_list);
paul718e3742002-12-13 20:15:29 +00001033
paul0c0f9cd2003-06-06 23:27:04 +00001034 /* Unlock the node. */
1035 rn->info = NULL;
1036 route_unlock_node (rn);
paul718e3742002-12-13 20:15:29 +00001037 }
1038 route_table_finish (rtrs);
1039}
1040
paul4dadc292005-05-06 21:37:42 +00001041static void
paul718e3742002-12-13 20:15:29 +00001042ospf_rtrs_print (struct route_table *rtrs)
1043{
1044 struct route_node *rn;
hasso52dc7ee2004-09-23 19:18:23 +00001045 struct list *or_list;
1046 struct listnode *ln;
1047 struct listnode *pnode;
paul718e3742002-12-13 20:15:29 +00001048 struct ospf_route *or;
1049 struct ospf_path *path;
1050 char buf1[BUFSIZ];
1051 char buf2[BUFSIZ];
1052
1053 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +00001054 zlog_debug ("ospf_rtrs_print() start");
paul718e3742002-12-13 20:15:29 +00001055
1056 for (rn = route_top (rtrs); rn; rn = route_next (rn))
1057 if ((or_list = rn->info) != NULL)
paul1eb8ef22005-04-07 07:30:20 +00001058 for (ALL_LIST_ELEMENTS_RO (or_list, ln, or))
paul718e3742002-12-13 20:15:29 +00001059 {
paul718e3742002-12-13 20:15:29 +00001060 switch (or->path_type)
1061 {
1062 case OSPF_PATH_INTRA_AREA:
paul0c0f9cd2003-06-06 23:27:04 +00001063 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +00001064 zlog_debug ("%s [%d] area: %s",
paul0c0f9cd2003-06-06 23:27:04 +00001065 inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
1066 or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
1067 buf2, BUFSIZ));
paul718e3742002-12-13 20:15:29 +00001068 break;
1069 case OSPF_PATH_INTER_AREA:
paul0c0f9cd2003-06-06 23:27:04 +00001070 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +00001071 zlog_debug ("%s IA [%d] area: %s",
paul0c0f9cd2003-06-06 23:27:04 +00001072 inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
1073 or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
1074 buf2, BUFSIZ));
paul718e3742002-12-13 20:15:29 +00001075 break;
1076 default:
1077 break;
1078 }
1079
paul1eb8ef22005-04-07 07:30:20 +00001080 for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path))
paul718e3742002-12-13 20:15:29 +00001081 {
paul718e3742002-12-13 20:15:29 +00001082 if (path->nexthop.s_addr == 0)
paul0c0f9cd2003-06-06 23:27:04 +00001083 {
1084 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +00001085 zlog_debug (" directly attached to %s\r\n",
paul0c0f9cd2003-06-06 23:27:04 +00001086 IF_NAME (path->oi));
1087 }
1088 else
1089 {
1090 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +00001091 zlog_debug (" via %s, %s\r\n",
paul0c0f9cd2003-06-06 23:27:04 +00001092 inet_ntoa (path->nexthop), IF_NAME (path->oi));
1093 }
paul718e3742002-12-13 20:15:29 +00001094 }
1095 }
1096
ajs2a42e282004-12-08 18:43:03 +00001097 zlog_debug ("ospf_rtrs_print() end");
paul718e3742002-12-13 20:15:29 +00001098}
1099
1100/* Calculating the shortest-path tree for an area. */
paul4dadc292005-05-06 21:37:42 +00001101static void
paul0c0f9cd2003-06-06 23:27:04 +00001102ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table,
paul718e3742002-12-13 20:15:29 +00001103 struct route_table *new_rtrs)
1104{
hasso462f20d2005-02-23 11:29:02 +00001105 struct pqueue *candidate;
paul718e3742002-12-13 20:15:29 +00001106 struct vertex *v;
pauleb3da6d2005-10-18 04:20:33 +00001107
paul718e3742002-12-13 20:15:29 +00001108 if (IS_DEBUG_OSPF_EVENT)
1109 {
ajs2a42e282004-12-08 18:43:03 +00001110 zlog_debug ("ospf_spf_calculate: Start");
1111 zlog_debug ("ospf_spf_calculate: running Dijkstra for area %s",
paul0c0f9cd2003-06-06 23:27:04 +00001112 inet_ntoa (area->area_id));
paul718e3742002-12-13 20:15:29 +00001113 }
1114
1115 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1116 return this area's calculation. */
paul0c0f9cd2003-06-06 23:27:04 +00001117 if (!area->router_lsa_self)
paul718e3742002-12-13 20:15:29 +00001118 {
1119 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +00001120 zlog_debug ("ospf_spf_calculate: "
paul0c0f9cd2003-06-06 23:27:04 +00001121 "Skip area %s's calculation due to empty router_lsa_self",
1122 inet_ntoa (area->area_id));
paul718e3742002-12-13 20:15:29 +00001123 return;
1124 }
1125
1126 /* RFC2328 16.1. (1). */
paul0c0f9cd2003-06-06 23:27:04 +00001127 /* Initialize the algorithm's data structures. */
hasso462f20d2005-02-23 11:29:02 +00001128
1129 /* This function scans all the LSA database and set the stat field to
1130 * LSA_SPF_NOT_EXPLORED. */
1131 ospf_lsdb_clean_stat (area->lsdb);
1132 /* Create a new heap for the candidates. */
1133 candidate = pqueue_create();
1134 candidate->cmp = cmp;
1135 candidate->update = update_stat;
paul718e3742002-12-13 20:15:29 +00001136
1137 /* Initialize the shortest-path tree to only the root (which is the
1138 router doing the calculation). */
1139 ospf_spf_init (area);
1140 v = area->spf;
hasso462f20d2005-02-23 11:29:02 +00001141 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the
1142 * spanning tree. */
1143 *(v->stat) = LSA_SPF_IN_SPFTREE;
paul718e3742002-12-13 20:15:29 +00001144
1145 /* Set Area A's TransitCapability to FALSE. */
1146 area->transit = OSPF_TRANSIT_FALSE;
1147 area->shortcut_capability = 1;
pauleb3da6d2005-10-18 04:20:33 +00001148
paul718e3742002-12-13 20:15:29 +00001149 for (;;)
1150 {
1151 /* RFC2328 16.1. (2). */
hasso462f20d2005-02-23 11:29:02 +00001152 ospf_spf_next (v, area, candidate);
paul718e3742002-12-13 20:15:29 +00001153
1154 /* RFC2328 16.1. (3). */
1155 /* If at this step the candidate list is empty, the shortest-
1156 path tree (of transit vertices) has been completely built and
1157 this stage of the procedure terminates. */
hasso462f20d2005-02-23 11:29:02 +00001158 if (candidate->size == 0)
paul718e3742002-12-13 20:15:29 +00001159 break;
1160
1161 /* Otherwise, choose the vertex belonging to the candidate list
1162 that is closest to the root, and add it to the shortest-path
1163 tree (removing it from the candidate list in the
paul0c0f9cd2003-06-06 23:27:04 +00001164 process). */
hasso462f20d2005-02-23 11:29:02 +00001165 /* Extract from the candidates the node with the lower key. */
1166 v = (struct vertex *) pqueue_dequeue (candidate);
1167 /* Update stat field in vertex. */
1168 *(v->stat) = LSA_SPF_IN_SPFTREE;
pauleb3da6d2005-10-18 04:20:33 +00001169
paul718e3742002-12-13 20:15:29 +00001170 ospf_vertex_add_parent (v);
1171
paul718e3742002-12-13 20:15:29 +00001172 /* Note that when there is a choice of vertices closest to the
1173 root, network vertices must be chosen before router vertices
1174 in order to necessarily find all equal-cost paths. */
1175 /* We don't do this at this moment, we should add the treatment
1176 above codes. -- kunihiro. */
1177
1178 /* RFC2328 16.1. (4). */
1179 if (v->type == OSPF_VERTEX_ROUTER)
1180 ospf_intra_add_router (new_rtrs, v, area);
paul0c0f9cd2003-06-06 23:27:04 +00001181 else
paul718e3742002-12-13 20:15:29 +00001182 ospf_intra_add_transit (new_table, v, area);
1183
1184 /* RFC2328 16.1. (5). */
1185 /* Iterate the algorithm by returning to Step 2. */
gdt630e4802004-08-31 17:28:41 +00001186
1187 } /* end loop until no more candidate vertices */
paul718e3742002-12-13 20:15:29 +00001188
1189 if (IS_DEBUG_OSPF_EVENT)
1190 {
1191 ospf_spf_dump (area->spf, 0);
1192 ospf_route_table_dump (new_table);
1193 }
1194
1195 /* Second stage of SPF calculation procedure's */
1196 ospf_spf_process_stubs (area, area->spf, new_table);
1197
pauleb3da6d2005-10-18 04:20:33 +00001198 /* Free candidate queue. */
hasso462f20d2005-02-23 11:29:02 +00001199 pqueue_delete (candidate);
pauleb3da6d2005-10-18 04:20:33 +00001200
1201 ospf_vertex_dump (__func__, area->spf, 0, 1);
1202 /* Free nexthop information, canonical versions of which are attached
1203 * the first level of router vertices attached to the root vertex, see
1204 * ospf_nexthop_calculation.
1205 */
1206 ospf_canonical_nexthops_free (area->spf);
1207
Paul Jakma9c27ef92006-05-04 07:32:57 +00001208 /* Free SPF vertices, but not the list. List has ospf_vertex_free
1209 * as deconstructor.
1210 */
1211 list_delete_all_node (&vertex_list);
pauleb3da6d2005-10-18 04:20:33 +00001212
paul718e3742002-12-13 20:15:29 +00001213 /* Increment SPF Calculation Counter. */
1214 area->spf_calculation++;
1215
Paul Jakma2518efd2006-08-27 06:49:29 +00001216 quagga_gettime (QUAGGA_CLK_MONOTONIC, &area->ospf->ts_spf);
paul718e3742002-12-13 20:15:29 +00001217
1218 if (IS_DEBUG_OSPF_EVENT)
Paul Jakma9c27ef92006-05-04 07:32:57 +00001219 zlog_debug ("ospf_spf_calculate: Stop. %ld vertices",
1220 mtype_stats_alloc(MTYPE_OSPF_VERTEX));
paul718e3742002-12-13 20:15:29 +00001221}
1222
1223/* Timer for SPF calculation. */
paul4dadc292005-05-06 21:37:42 +00001224static int
paul68980082003-03-25 05:07:42 +00001225ospf_spf_calculate_timer (struct thread *thread)
paul718e3742002-12-13 20:15:29 +00001226{
paul68980082003-03-25 05:07:42 +00001227 struct ospf *ospf = THREAD_ARG (thread);
paul718e3742002-12-13 20:15:29 +00001228 struct route_table *new_table, *new_rtrs;
paul1eb8ef22005-04-07 07:30:20 +00001229 struct ospf_area *area;
1230 struct listnode *node, *nnode;
paul718e3742002-12-13 20:15:29 +00001231
1232 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +00001233 zlog_debug ("SPF: Timer (SPF calculation expire)");
paul0c0f9cd2003-06-06 23:27:04 +00001234
paul718e3742002-12-13 20:15:29 +00001235 ospf->t_spf_calc = NULL;
1236
1237 /* Allocate new table tree. */
1238 new_table = route_table_init ();
paul0c0f9cd2003-06-06 23:27:04 +00001239 new_rtrs = route_table_init ();
paul718e3742002-12-13 20:15:29 +00001240
paul68980082003-03-25 05:07:42 +00001241 ospf_vl_unapprove (ospf);
paul718e3742002-12-13 20:15:29 +00001242
1243 /* Calculate SPF for each area. */
paul1eb8ef22005-04-07 07:30:20 +00001244 for (ALL_LIST_ELEMENTS (ospf->areas, node, nnode, area))
Paul Jakma9c27ef92006-05-04 07:32:57 +00001245 {
1246 /* Do backbone last, so as to first discover intra-area paths
1247 * for any back-bone virtual-links
1248 */
1249 if (ospf->backbone && ospf->backbone == area)
1250 continue;
1251
1252 ospf_spf_calculate (area, new_table, new_rtrs);
1253 }
1254
1255 /* SPF for backbone, if required */
1256 if (ospf->backbone)
1257 ospf_spf_calculate (ospf->backbone, new_table, new_rtrs);
1258
paul68980082003-03-25 05:07:42 +00001259 ospf_vl_shut_unapproved (ospf);
paul718e3742002-12-13 20:15:29 +00001260
paul68980082003-03-25 05:07:42 +00001261 ospf_ia_routing (ospf, new_table, new_rtrs);
paul718e3742002-12-13 20:15:29 +00001262
1263 ospf_prune_unreachable_networks (new_table);
1264 ospf_prune_unreachable_routers (new_rtrs);
1265
1266 /* AS-external-LSA calculation should not be performed here. */
1267
1268 /* If new Router Route is installed,
1269 then schedule re-calculate External routes. */
1270 if (1)
paul68980082003-03-25 05:07:42 +00001271 ospf_ase_calculate_schedule (ospf);
paul718e3742002-12-13 20:15:29 +00001272
paul68980082003-03-25 05:07:42 +00001273 ospf_ase_calculate_timer_add (ospf);
paul718e3742002-12-13 20:15:29 +00001274
1275 /* Update routing table. */
paul68980082003-03-25 05:07:42 +00001276 ospf_route_install (ospf, new_table);
paul718e3742002-12-13 20:15:29 +00001277
1278 /* Update ABR/ASBR routing table */
paul68980082003-03-25 05:07:42 +00001279 if (ospf->old_rtrs)
paul718e3742002-12-13 20:15:29 +00001280 {
1281 /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
paul68980082003-03-25 05:07:42 +00001282 /* ospf_route_delete (ospf->old_rtrs); */
1283 ospf_rtrs_free (ospf->old_rtrs);
paul718e3742002-12-13 20:15:29 +00001284 }
1285
paul68980082003-03-25 05:07:42 +00001286 ospf->old_rtrs = ospf->new_rtrs;
1287 ospf->new_rtrs = new_rtrs;
paul718e3742002-12-13 20:15:29 +00001288
paul0c0f9cd2003-06-06 23:27:04 +00001289 if (IS_OSPF_ABR (ospf))
paul68980082003-03-25 05:07:42 +00001290 ospf_abr_task (ospf);
paul718e3742002-12-13 20:15:29 +00001291
1292 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +00001293 zlog_debug ("SPF: calculation complete");
paul718e3742002-12-13 20:15:29 +00001294
1295 return 0;
1296}
1297
1298/* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1299 set timer for SPF calc. */
1300void
paul68980082003-03-25 05:07:42 +00001301ospf_spf_calculate_schedule (struct ospf *ospf)
paul718e3742002-12-13 20:15:29 +00001302{
pauld24f6e22005-10-21 09:23:12 +00001303 unsigned long delay, elapsed, ht;
1304 struct timeval result;
paul718e3742002-12-13 20:15:29 +00001305
1306 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +00001307 zlog_debug ("SPF: calculation timer scheduled");
paul718e3742002-12-13 20:15:29 +00001308
1309 /* OSPF instance does not exist. */
paul68980082003-03-25 05:07:42 +00001310 if (ospf == NULL)
paul718e3742002-12-13 20:15:29 +00001311 return;
pauld24f6e22005-10-21 09:23:12 +00001312
paul718e3742002-12-13 20:15:29 +00001313 /* SPF calculation timer is already scheduled. */
paul68980082003-03-25 05:07:42 +00001314 if (ospf->t_spf_calc)
paul718e3742002-12-13 20:15:29 +00001315 {
1316 if (IS_DEBUG_OSPF_EVENT)
ajs2a42e282004-12-08 18:43:03 +00001317 zlog_debug ("SPF: calculation timer is already scheduled: %p",
paul0c0f9cd2003-06-06 23:27:04 +00001318 ospf->t_spf_calc);
paul718e3742002-12-13 20:15:29 +00001319 return;
1320 }
pauld24f6e22005-10-21 09:23:12 +00001321
1322 /* XXX Monotic timers: we only care about relative time here. */
Paul Jakma2518efd2006-08-27 06:49:29 +00001323 result = tv_sub (recent_relative_time (), ospf->ts_spf);
pauld24f6e22005-10-21 09:23:12 +00001324
1325 elapsed = (result.tv_sec * 1000) + (result.tv_usec / 1000);
1326 ht = ospf->spf_holdtime * ospf->spf_hold_multiplier;
1327
1328 if (ht > ospf->spf_max_holdtime)
1329 ht = ospf->spf_max_holdtime;
1330
paul718e3742002-12-13 20:15:29 +00001331 /* Get SPF calculation delay time. */
pauld24f6e22005-10-21 09:23:12 +00001332 if (elapsed < ht)
paul718e3742002-12-13 20:15:29 +00001333 {
pauld24f6e22005-10-21 09:23:12 +00001334 /* Got an event within the hold time of last SPF. We need to
1335 * increase the hold_multiplier, if it's not already at/past
1336 * maximum value, and wasn't already increased..
1337 */
1338 if (ht < ospf->spf_max_holdtime)
1339 ospf->spf_hold_multiplier++;
1340
1341 /* always honour the SPF initial delay */
1342 if ( (ht - elapsed) < ospf->spf_delay)
paul0c0f9cd2003-06-06 23:27:04 +00001343 delay = ospf->spf_delay;
paul718e3742002-12-13 20:15:29 +00001344 else
pauld24f6e22005-10-21 09:23:12 +00001345 delay = ht - elapsed;
paul718e3742002-12-13 20:15:29 +00001346 }
1347 else
pauld24f6e22005-10-21 09:23:12 +00001348 {
1349 /* Event is past required hold-time of last SPF */
1350 delay = ospf->spf_delay;
1351 ospf->spf_hold_multiplier = 1;
1352 }
1353
paul718e3742002-12-13 20:15:29 +00001354 if (IS_DEBUG_OSPF_EVENT)
pauld24f6e22005-10-21 09:23:12 +00001355 zlog_debug ("SPF: calculation timer delay = %ld", delay);
1356
paul68980082003-03-25 05:07:42 +00001357 ospf->t_spf_calc =
pauld24f6e22005-10-21 09:23:12 +00001358 thread_add_timer_msec (master, ospf_spf_calculate_timer, ospf, delay);
paul718e3742002-12-13 20:15:29 +00001359}