]> git.proxmox.com Git - mirror_frr.git/blame - ospfd/ospf_spf.c
projects / mirror_frr.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
2003-06-07 Paul Jakma <paul@dishone.st>
[mirror_frr.git] / ospfd / ospf_spf.c
CommitLineData
718e3744 1/* 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 () */
32
33#include "ospfd/ospfd.h"
34#include "ospfd/ospf_interface.h"
35#include "ospfd/ospf_ism.h"
36#include "ospfd/ospf_asbr.h"
37#include "ospfd/ospf_lsa.h"
38#include "ospfd/ospf_lsdb.h"
39#include "ospfd/ospf_neighbor.h"
40#include "ospfd/ospf_nsm.h"
41#include "ospfd/ospf_spf.h"
42#include "ospfd/ospf_route.h"
43#include "ospfd/ospf_ia.h"
44#include "ospfd/ospf_ase.h"
45#include "ospfd/ospf_abr.h"
46#include "ospfd/ospf_dump.h"
47
48#define DEBUG
49
50struct vertex_nexthop *
51vertex_nexthop_new (struct vertex *parent)
52{
53 struct vertex_nexthop *new;
54
55 new = XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop));
56 new->parent = parent;
57
58 return new;
59}
60
61void
62vertex_nexthop_free (struct vertex_nexthop *nh)
63{
64 XFREE (MTYPE_OSPF_NEXTHOP, nh);
65}
66
67struct vertex_nexthop *
68vertex_nexthop_dup (struct vertex_nexthop *nh)
69{
70 struct vertex_nexthop *new;
71
72 new = vertex_nexthop_new (nh->parent);
73
74 new->oi = nh->oi;
75 new->router = nh->router;
76
77 return new;
78}
79
80\f
81struct vertex *
82ospf_vertex_new (struct ospf_lsa *lsa)
83{
84 struct vertex *new;
85
86 new = XMALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex));
87 memset (new, 0, sizeof (struct vertex));
88
89 new->flags = 0;
90 new->type = lsa->data->type;
91 new->id = lsa->data->id;
92 new->lsa = lsa->data;
93 new->distance = 0;
94 new->child = list_new ();
95 new->nexthop = list_new ();
96
97 return new;
98}
99
100void
101ospf_vertex_free (struct vertex *v)
102{
103 listnode node;
104
105 list_delete (v->child);
106
107 if (listcount (v->nexthop) > 0)
108 for (node = listhead (v->nexthop); node; nextnode (node))
109 vertex_nexthop_free (node->data);
110
111 list_delete (v->nexthop);
112
113 XFREE (MTYPE_OSPF_VERTEX, v);
114}
115
116void
117ospf_vertex_add_parent (struct vertex *v)
118{
119 struct vertex_nexthop *nh;
120 listnode node;
121
122 for (node = listhead (v->nexthop); node; nextnode (node))
123 {
124 nh = (struct vertex_nexthop *) getdata (node);
125
126 /* No need to add two links from the same parent. */
127 if (listnode_lookup (nh->parent->child, v) == NULL)
128 listnode_add (nh->parent->child, v);
129 }
130}
131\f
132void
133ospf_spf_init (struct ospf_area *area)
134{
135 struct vertex *v;
136
137 /* Create root node. */
138 v = ospf_vertex_new (area->router_lsa_self);
139
140 area->spf = v;
141
142 /* Reset ABR and ASBR router counts. */
143 area->abr_count = 0;
144 area->asbr_count = 0;
145}
146
147int
148ospf_spf_has_vertex (struct route_table *rv, struct route_table *nv,
149 struct lsa_header *lsa)
150{
151 struct prefix p;
152 struct route_node *rn;
153
154 p.family = AF_INET;
155 p.prefixlen = IPV4_MAX_BITLEN;
156 p.u.prefix4 = lsa->id;
157
158 if (lsa->type == OSPF_ROUTER_LSA)
159 rn = route_node_get (rv, &p);
160 else
161 rn = route_node_get (nv, &p);
162
163 if (rn->info != NULL)
164 {
165 route_unlock_node (rn);
166 return 1;
167 }
168 return 0;
169}
170
171listnode
172ospf_vertex_lookup (list vlist, struct in_addr id, int type)
173{
174 listnode node;
175 struct vertex *v;
176
177 for (node = listhead (vlist); node; nextnode (node))
178 {
179 v = (struct vertex *) getdata (node);
180 if (IPV4_ADDR_SAME (&id, &v->id) && type == v->type)
181 return node;
182 }
183
184 return NULL;
185}
186
187int
188ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v)
189{
190 int i;
191 int length;
192 struct router_lsa *rl;
193 struct network_lsa *nl;
194
195 /* In case of W is Network LSA. */
196 if (w->type == OSPF_NETWORK_LSA)
197 {
198 if (v->type == OSPF_NETWORK_LSA)
199 return 0;
200
201 nl = (struct network_lsa *) w;
202 length = (ntohs (w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;
203
204 for (i = 0; i < length; i++)
205 if (IPV4_ADDR_SAME (&nl->routers[i], &v->id))
206 return 1;
207 return 0;
208 }
209
210 /* In case of W is Router LSA. */
211 if (w->type == OSPF_ROUTER_LSA)
212 {
213 rl = (struct router_lsa *) w;
214
215 length = ntohs (w->length);
216
217 for (i = 0;
218 i < ntohs (rl->links) && length >= sizeof (struct router_lsa);
219 i++, length -= 12)
220 {
221 switch (rl->link[i].type)
222 {
223 case LSA_LINK_TYPE_POINTOPOINT:
224 case LSA_LINK_TYPE_VIRTUALLINK:
225 /* Router LSA ID. */
226 if (v->type == OSPF_ROUTER_LSA &&
227 IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
228 {
229 return 1;
230 }
231 break;
232 case LSA_LINK_TYPE_TRANSIT:
233 /* Network LSA ID. */
234 if (v->type == OSPF_NETWORK_LSA &&
235 IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
236 {
237 return 1;
238 }
239 break;
240 case LSA_LINK_TYPE_STUB:
241 /* Not take into count? */
242 continue;
243 default:
244 break;
245 }
246 }
247 }
248 return 0;
249}
250
251/* Add the nexthop to the list, only if it is unique.
252 * If it's not unique, free the nexthop entry.
253 */
254void
255ospf_nexthop_add_unique (struct vertex_nexthop *new, list nexthop)
256{
257 struct vertex_nexthop *nh;
258 listnode node;
259 int match;
260
261 match = 0;
262 for (node = listhead (nexthop); node; nextnode (node))
263 {
264 nh = node->data;
265
266 /* Compare the two entries. */
267 /* XXX
268 * Comparing the parent preserves the shortest path tree
269 * structure even when the nexthops are identical.
270 */
271 if (nh->oi == new->oi &&
272 IPV4_ADDR_SAME (&nh->router, &new->router) &&
273 nh->parent == new->parent)
274 {
275 match = 1;
276 break;
277 }
278 }
279
280 if (!match)
281 listnode_add (nexthop, new);
282 else
283 vertex_nexthop_free (new);
284}
285
286/* Merge entries in list b into list a. */
287void
288ospf_nexthop_merge (list a, list b)
289{
290 struct listnode *n;
291
292 for (n = listhead (b); n; nextnode (n))
293 {
294 ospf_nexthop_add_unique (n->data, a);
295 }
296}
297
298#define ROUTER_LSA_MIN_SIZE 12
299#define ROUTER_LSA_TOS_SIZE 4
300
301struct router_lsa_link *
302ospf_get_next_link (struct vertex *v, struct vertex *w,
303 struct router_lsa_link *prev_link)
304{
305 u_char *p;
306 u_char *lim;
307 struct router_lsa_link *l;
308
309 if (prev_link == NULL)
310 p = ((u_char *) v->lsa) + 24;
311 else
312 {
313 p = (u_char *)prev_link;
314 p += (ROUTER_LSA_MIN_SIZE +
315 (prev_link->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
316 }
317
318 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
319
320 while (p < lim)
321 {
322 l = (struct router_lsa_link *) p;
323
324 p += (ROUTER_LSA_MIN_SIZE +
325 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
326
327 if (l->m[0].type == LSA_LINK_TYPE_STUB)
328 continue;
329
330 /* Defer NH calculation via VLs until summaries from
331 transit areas area confidered */
332
333 if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
334 continue;
335
336 if (IPV4_ADDR_SAME (&l->link_id, &w->id))
337 return l;
338 }
339
340 return NULL;
341}
342
bf9392c6 343/* Consider supplied next-hop for inclusion to the supplied list
344 * of next-hops, adjust list as neccessary
345 */
346void
347ospf_spf_consider_nexthop (struct list *nexthops, struct vertex_nexthop *newhop)
348{
349 struct listnode *nnode;
350 struct vertex_nexthop *hop;
351
352 LIST_LOOP (nexthops, hop, nnode)
353 {
354 assert (hop->oi);
355 /* weed out hops with higher cost than the newhop */
356 if (hop->oi->output_cost > newhop->oi->output_cost)
357 {
358 /* delete the existing nexthop */
359 listnode_delete (nexthops, hop);
360 vertex_nexthop_free (hop);
361 }
362 else if ( hop->oi->output_cost < newhop->oi->output_cost)
363 {
364 return;
365 }
366 }
367
368 /* new hop is <= existing hops, add it */
369 listnode_add (nexthops, newhop);
370
371 return;
372}
373
718e3744 374/* Calculate nexthop from root to vertex W. */
375void
376ospf_nexthop_calculation (struct ospf_area *area,
377 struct vertex *v, struct vertex *w)
378{
379 listnode node;
380 struct vertex_nexthop *nh, *x;
381 struct ospf_interface *oi = NULL;
382 struct router_lsa_link *l = NULL;
383
384
385 if (IS_DEBUG_OSPF_EVENT)
386 zlog_info ("ospf_nexthop_calculation(): Start");
387
388 /* W's parent is root. */
389 if (v == area->spf)
390 {
391 if (w->type == OSPF_VERTEX_ROUTER)
392 {
393 while ((l = ospf_get_next_link (v, w, l)))
394 {
395 struct router_lsa_link *l2 = NULL;
396
397 if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
398 {
68980084 399 /* Check for PtMP, signified by PtP link V->W
400 with link_data our PtMP interface. */
401 oi = ospf_if_is_configured (area->ospf, &l->link_data);
7afa08da 402 if (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
718e3744 403 {
68980084 404 struct prefix_ipv4 la;
405 la.prefixlen = oi->address->prefixlen;
406 /* We link to them on PtMP interface
407 - find the interface on w */
7afa08da 408 while ((l2 = ospf_get_next_link (w, v, l2)))
409 {
68980084 410 la.prefix = l2->link_data;
7afa08da 411
68980084 412 if (prefix_cmp ((struct prefix *)&la,
413 oi->address) == 0)
7afa08da 414 /* link_data is on our PtMP network */
415 break;
7afa08da 416 }
417 }
418 else
419 {
420 while ((l2 = ospf_get_next_link (w, v, l2)))
421 {
68980084 422 oi = ospf_if_is_configured (area->ospf,
423 &(l2->link_data));
7afa08da 424
425 if (oi == NULL)
426 continue;
427
68980084 428 if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
429 &l->link_data))
7afa08da 430 continue;
431
432 break;
68980084 433 }
718e3744 434 }
435
436 if (oi && l2)
437 {
438 nh = vertex_nexthop_new (v);
439 nh->oi = oi;
440 nh->router = l2->link_data;
bf9392c6 441 ospf_spf_consider_nexthop (w->nexthop, nh);
718e3744 442 }
443 }
444 }
445 }
446 else
447 {
448 while ((l = ospf_get_next_link (v, w, l)))
449 {
68980084 450 oi = ospf_if_is_configured (area->ospf, &(l->link_data));
718e3744 451 if (oi)
452 {
453 nh = vertex_nexthop_new (v);
454 nh->oi = oi;
455 nh->router.s_addr = 0;
456 listnode_add (w->nexthop, nh);
457 }
458 }
459 }
460 return;
461 }
462 /* In case of W's parent is network connected to root. */
463 else if (v->type == OSPF_VERTEX_NETWORK)
464 {
465 for (node = listhead (v->nexthop); node; nextnode (node))
466 {
467 x = (struct vertex_nexthop *) getdata (node);
468 if (x->parent == area->spf)
469 {
470 while ((l = ospf_get_next_link (w, v, l)))
471 {
472 nh = vertex_nexthop_new (v);
473 nh->oi = x->oi;
474 nh->router = l->link_data;
475 listnode_add (w->nexthop, nh);
476 }
477 return;
478 }
479 }
480 }
481
482 /* Inherit V's nexthop. */
483 for (node = listhead (v->nexthop); node; nextnode (node))
484 {
485 nh = vertex_nexthop_dup (node->data);
486 nh->parent = v;
487 ospf_nexthop_add_unique (nh, w->nexthop);
488 }
489}
490
491void
492ospf_install_candidate (list candidate, struct vertex *w)
493{
494 listnode node;
495 struct vertex *cw;
496
497 if (list_isempty (candidate))
498 {
499 listnode_add (candidate, w);
500 return;
501 }
502
503 /* Install vertex with sorting by distance. */
504 for (node = listhead (candidate); node; nextnode (node))
505 {
506 cw = (struct vertex *) getdata (node);
507 if (cw->distance > w->distance)
508 {
509 list_add_node_prev (candidate, node, w);
510 break;
511 }
512 else if (node->next == NULL)
513 {
514 list_add_node_next (candidate, node, w);
515 break;
516 }
517 }
518}
519
520/* RFC2328 Section 16.1 (2). */
521void
522ospf_spf_next (struct vertex *v, struct ospf_area *area,
523 list candidate, struct route_table *rv,
524 struct route_table *nv)
525{
526 struct ospf_lsa *w_lsa = NULL;
527 struct vertex *w, *cw;
528 u_char *p;
529 u_char *lim;
530 struct router_lsa_link *l = NULL;
531 struct in_addr *r;
532 listnode node;
533 int type = 0;
534
535 /* If this is a router-LSA, and bit V of the router-LSA (see Section
536 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
537 if (v->type == OSPF_VERTEX_ROUTER)
538 {
539 if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa))
540 area->transit = OSPF_TRANSIT_TRUE;
541 }
542
543 p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
544 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
545
546 while (p < lim)
547 {
548 /* In case of V is Router-LSA. */
549 if (v->lsa->type == OSPF_ROUTER_LSA)
550 {
551 l = (struct router_lsa_link *) p;
552
553 p += (ROUTER_LSA_MIN_SIZE +
554 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
555
556 /* (a) If this is a link to a stub network, examine the next
557 link in V's LSA. Links to stub networks will be
558 considered in the second stage of the shortest path
559 calculation. */
560 if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
561 continue;
562
563 /* (b) Otherwise, W is a transit vertex (router or transit
564 network). Look up the vertex W's LSA (router-LSA or
565 network-LSA) in Area A's link state database. */
566 switch (type)
567 {
568 case LSA_LINK_TYPE_POINTOPOINT:
569 case LSA_LINK_TYPE_VIRTUALLINK:
570 if (type == LSA_LINK_TYPE_VIRTUALLINK)
571 {
572 if (IS_DEBUG_OSPF_EVENT)
573 zlog_info ("looking up LSA through VL: %s",
574 inet_ntoa (l->link_id));
575 }
576
577 w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id,
578 l->link_id);
579 if (w_lsa)
580 {
581 if (IS_DEBUG_OSPF_EVENT)
582 zlog_info("found the LSA");
583 }
584 break;
585 case LSA_LINK_TYPE_TRANSIT:
586 if (IS_DEBUG_OSPF_EVENT)
587
588 zlog_info ("Looking up Network LSA, ID: %s",
589 inet_ntoa(l->link_id));
590 w_lsa = ospf_lsa_lookup_by_id (area, OSPF_NETWORK_LSA,
591 l->link_id);
592 if (w_lsa)
593 if (IS_DEBUG_OSPF_EVENT)
594 zlog_info("found the LSA");
595 break;
596 default:
597 zlog_warn ("Invalid LSA link type %d", type);
598 continue;
599 }
600 }
601 else
602 {
603 /* In case of V is Network-LSA. */
604 r = (struct in_addr *) p ;
605 p += sizeof (struct in_addr);
606
607 /* Lookup the vertex W's LSA. */
608 w_lsa = ospf_lsa_lookup_by_id (area, OSPF_ROUTER_LSA, *r);
609 }
610
611 /* (b cont.) If the LSA does not exist, or its LS age is equal
612 to MaxAge, or it does not have a link back to vertex V,
613 examine the next link in V's LSA.[23] */
614 if (w_lsa == NULL)
615 continue;
616
617 if (IS_LSA_MAXAGE (w_lsa))
618 continue;
619
620 if (! ospf_lsa_has_link (w_lsa->data, v->lsa))
621 {
622 if (IS_DEBUG_OSPF_EVENT)
623 zlog_info ("The LSA doesn't have a link back");
624 continue;
625 }
626
627 /* (c) If vertex W is already on the shortest-path tree, examine
628 the next link in the LSA. */
629 if (ospf_spf_has_vertex (rv, nv, w_lsa->data))
630 {
631 if (IS_DEBUG_OSPF_EVENT)
632 zlog_info ("The LSA is already in SPF");
633 continue;
634 }
635
636 /* (d) Calculate the link state cost D of the resulting path
637 from the root to vertex W. D is equal to the sum of the link
638 state cost of the (already calculated) shortest path to
639 vertex V and the advertised cost of the link between vertices
640 V and W. If D is: */
641
642 /* prepare vertex W. */
643 w = ospf_vertex_new (w_lsa);
644
645 /* calculate link cost D. */
646 if (v->lsa->type == OSPF_ROUTER_LSA)
647 w->distance = v->distance + ntohs (l->m[0].metric);
648 else
649 w->distance = v->distance;
650
651 /* Is there already vertex W in candidate list? */
652 node = ospf_vertex_lookup (candidate, w->id, w->type);
653 if (node == NULL)
654 {
655 /* Calculate nexthop to W. */
656 ospf_nexthop_calculation (area, v, w);
657
658 ospf_install_candidate (candidate, w);
659 }
660 else
661 {
662 cw = (struct vertex *) getdata (node);
663
664 /* if D is greater than. */
665 if (cw->distance < w->distance)
666 {
667 ospf_vertex_free (w);
668 continue;
669 }
670 /* equal to. */
671 else if (cw->distance == w->distance)
672 {
673 /* Calculate nexthop to W. */
674 ospf_nexthop_calculation (area, v, w);
675 ospf_nexthop_merge (cw->nexthop, w->nexthop);
676 list_delete_all_node (w->nexthop);
677 ospf_vertex_free (w);
678 }
679 /* less than. */
680 else
681 {
682 /* Calculate nexthop. */
683 ospf_nexthop_calculation (area, v, w);
684
685 /* Remove old vertex from candidate list. */
686 ospf_vertex_free (cw);
687 listnode_delete (candidate, cw);
688
689 /* Install new to candidate. */
690 ospf_install_candidate (candidate, w);
691 }
692 }
693 }
694}
695
696/* Add vertex V to SPF tree. */
697void
698ospf_spf_register (struct vertex *v, struct route_table *rv,
699 struct route_table *nv)
700{
701 struct prefix p;
702 struct route_node *rn;
703
704 p.family = AF_INET;
705 p.prefixlen = IPV4_MAX_BITLEN;
706 p.u.prefix4 = v->id;
707
708 if (v->type == OSPF_VERTEX_ROUTER)
709 rn = route_node_get (rv, &p);
710 else
711 rn = route_node_get (nv, &p);
712
713 rn->info = v;
714}
715
716void
717ospf_spf_route_free (struct route_table *table)
718{
719 struct route_node *rn;
720 struct vertex *v;
721
722 for (rn = route_top (table); rn; rn = route_next (rn))
723 {
724 if ((v = rn->info))
725 {
726 ospf_vertex_free (v);
727 rn->info = NULL;
728 }
729
730 route_unlock_node (rn);
731 }
732
733 route_table_finish (table);
734}
735
736void
737ospf_spf_dump (struct vertex *v, int i)
738{
739 listnode cnode;
740 listnode nnode;
741 struct vertex_nexthop *nexthop;
742
743 if (v->type == OSPF_VERTEX_ROUTER)
744 {
745 if (IS_DEBUG_OSPF_EVENT)
746 zlog_info ("SPF Result: %d [R] %s", i, inet_ntoa (v->lsa->id));
747 }
748 else
749 {
750 struct network_lsa *lsa = (struct network_lsa *) v->lsa;
751 if (IS_DEBUG_OSPF_EVENT)
752 zlog_info ("SPF Result: %d [N] %s/%d", i, inet_ntoa (v->lsa->id),
753 ip_masklen (lsa->mask));
754
755 for (nnode = listhead (v->nexthop); nnode; nextnode (nnode))
756 {
757 nexthop = getdata (nnode);
758 if (IS_DEBUG_OSPF_EVENT)
759 zlog_info (" nexthop %s", inet_ntoa (nexthop->router));
760 }
761 }
762
763 i++;
764
765 for (cnode = listhead (v->child); cnode; nextnode (cnode))
766 {
767 v = getdata (cnode);
768 ospf_spf_dump (v, i);
769 }
770}
771
772/* Second stage of SPF calculation. */
773void
774ospf_spf_process_stubs (struct ospf_area *area, struct vertex * v,
775 struct route_table *rt)
776{
777 listnode cnode;
778 struct vertex *child;
779
780 if (IS_DEBUG_OSPF_EVENT)
781 zlog_info ("ospf_process_stub():processing stubs for area %s",
782 inet_ntoa (area->area_id));
783 if (v->type == OSPF_VERTEX_ROUTER)
784 {
785 u_char *p;
786 u_char *lim;
787 struct router_lsa_link *l;
788 struct router_lsa *rlsa;
789
790 if (IS_DEBUG_OSPF_EVENT)
791 zlog_info ("ospf_process_stub():processing router LSA, id: %s",
792 inet_ntoa (v->lsa->id));
793 rlsa = (struct router_lsa *) v->lsa;
794
795
796 if (IS_DEBUG_OSPF_EVENT)
797 zlog_info ("ospf_process_stub(): we have %d links to process",
798 ntohs (rlsa->links));
799 p = ((u_char *) v->lsa) + 24;
800 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
801
802 while (p < lim)
803 {
804 l = (struct router_lsa_link *) p;
805
806 p += (ROUTER_LSA_MIN_SIZE +
807 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
808
809 if (l->m[0].type == LSA_LINK_TYPE_STUB)
810 ospf_intra_add_stub (rt, l, v, area);
811 }
812 }
813
814 if (IS_DEBUG_OSPF_EVENT)
815 zlog_info ("children of V:");
816 for (cnode = listhead (v->child); cnode; nextnode (cnode))
817 {
818 child = getdata (cnode);
819 if (IS_DEBUG_OSPF_EVENT)
820 zlog_info (" child : %s", inet_ntoa (child->id));
821 }
822
823 for (cnode = listhead (v->child); cnode; nextnode (cnode))
824 {
825 child = getdata (cnode);
826
827 if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED))
828 continue;
829
830 ospf_spf_process_stubs (area, child, rt);
831
832 SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED);
833 }
834}
835
836void
837ospf_rtrs_free (struct route_table *rtrs)
838{
839 struct route_node *rn;
840 list or_list;
841 listnode node;
842
843 if (IS_DEBUG_OSPF_EVENT)
844 zlog_info ("Route: Router Routing Table free");
845
846 for (rn = route_top (rtrs); rn; rn = route_next (rn))
847 if ((or_list = rn->info) != NULL)
848 {
849 for (node = listhead (or_list); node; nextnode (node))
850 ospf_route_free (node->data);
851
852 list_delete (or_list);
853
854 /* Unlock the node. */
855 rn->info = NULL;
856 route_unlock_node (rn);
857 }
858 route_table_finish (rtrs);
859}
860
861void
862ospf_rtrs_print (struct route_table *rtrs)
863{
864 struct route_node *rn;
865 list or_list;
866 listnode ln;
867 listnode pnode;
868 struct ospf_route *or;
869 struct ospf_path *path;
870 char buf1[BUFSIZ];
871 char buf2[BUFSIZ];
872
873 if (IS_DEBUG_OSPF_EVENT)
874 zlog_info ("ospf_rtrs_print() start");
875
876 for (rn = route_top (rtrs); rn; rn = route_next (rn))
877 if ((or_list = rn->info) != NULL)
878 for (ln = listhead (or_list); ln; nextnode (ln))
879 {
880 or = getdata (ln);
881
882 switch (or->path_type)
883 {
884 case OSPF_PATH_INTRA_AREA:
885 if (IS_DEBUG_OSPF_EVENT)
886 zlog_info ("%s [%d] area: %s",
887 inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), or->cost,
888 inet_ntop (AF_INET, &or->u.std.area_id,
889 buf2, BUFSIZ));
890 break;
891 case OSPF_PATH_INTER_AREA:
892 if (IS_DEBUG_OSPF_EVENT)
893 zlog_info ("%s IA [%d] area: %s",
894 inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), or->cost,
895 inet_ntop (AF_INET, &or->u.std.area_id,
896 buf2, BUFSIZ));
897 break;
898 default:
899 break;
900 }
901
902 for (pnode = listhead (or->path); pnode; nextnode (pnode))
903 {
904 path = getdata (pnode);
905 if (path->nexthop.s_addr == 0)
906 {
907 if (IS_DEBUG_OSPF_EVENT)
908 zlog_info (" directly attached to %s\r\n",
909 IF_NAME (path->oi));
910 }
911 else
912 {
913 if (IS_DEBUG_OSPF_EVENT)
914 zlog_info (" via %s, %s\r\n",
915 inet_ntoa (path->nexthop), IF_NAME (path->oi));
916 }
917 }
918 }
919
920 zlog_info ("ospf_rtrs_print() end");
921}
922
923/* Calculating the shortest-path tree for an area. */
924void
925ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table,
926 struct route_table *new_rtrs)
927{
928 list candidate;
929 listnode node;
930 struct vertex *v;
931 struct route_table *rv;
932 struct route_table *nv;
933
934 if (IS_DEBUG_OSPF_EVENT)
935 {
936 zlog_info ("ospf_spf_calculate: Start");
937 zlog_info ("ospf_spf_calculate: running Dijkstra for area %s",
938 inet_ntoa (area->area_id));
939 }
940
941 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
942 return this area's calculation. */
943 if (! area->router_lsa_self)
944 {
945 if (IS_DEBUG_OSPF_EVENT)
946 zlog_info ("ospf_spf_calculate: "
947 "Skip area %s's calculation due to empty router_lsa_self",
948 inet_ntoa (area->area_id));
949 return;
950 }
951
952 /* RFC2328 16.1. (1). */
953 /* Initialize the algorithm's data structures. */
954 rv = route_table_init ();
955 nv = route_table_init ();
956
957 /* Clear the list of candidate vertices. */
958 candidate = list_new ();
959
960 /* Initialize the shortest-path tree to only the root (which is the
961 router doing the calculation). */
962 ospf_spf_init (area);
963 v = area->spf;
964 ospf_spf_register (v, rv, nv);
965
966 /* Set Area A's TransitCapability to FALSE. */
967 area->transit = OSPF_TRANSIT_FALSE;
968 area->shortcut_capability = 1;
969
970 for (;;)
971 {
972 /* RFC2328 16.1. (2). */
973 ospf_spf_next (v, area, candidate, rv, nv);
974
975 /* RFC2328 16.1. (3). */
976 /* If at this step the candidate list is empty, the shortest-
977 path tree (of transit vertices) has been completely built and
978 this stage of the procedure terminates. */
979 if (listcount (candidate) == 0)
980 break;
981
982 /* Otherwise, choose the vertex belonging to the candidate list
983 that is closest to the root, and add it to the shortest-path
984 tree (removing it from the candidate list in the
985 process). */
986 node = listhead (candidate);
987 v = getdata (node);
988 ospf_vertex_add_parent (v);
989
990 /* Reveve from the candidate list. */
991 listnode_delete (candidate, v);
992
993 /* Add to SPF tree. */
994 ospf_spf_register (v, rv, nv);
995
996 /* Note that when there is a choice of vertices closest to the
997 root, network vertices must be chosen before router vertices
998 in order to necessarily find all equal-cost paths. */
999 /* We don't do this at this moment, we should add the treatment
1000 above codes. -- kunihiro. */
1001
1002 /* RFC2328 16.1. (4). */
1003 if (v->type == OSPF_VERTEX_ROUTER)
1004 ospf_intra_add_router (new_rtrs, v, area);
1005 else
1006 ospf_intra_add_transit (new_table, v, area);
1007
1008 /* RFC2328 16.1. (5). */
1009 /* Iterate the algorithm by returning to Step 2. */
1010 }
1011
1012 if (IS_DEBUG_OSPF_EVENT)
1013 {
1014 ospf_spf_dump (area->spf, 0);
1015 ospf_route_table_dump (new_table);
1016 }
1017
1018 /* Second stage of SPF calculation procedure's */
1019 ospf_spf_process_stubs (area, area->spf, new_table);
1020
1021 /* Free all vertices which allocated for SPF calculation */
1022 ospf_spf_route_free (rv);
1023 ospf_spf_route_free (nv);
1024
1025 /* Free candidate list */
1026 list_free (candidate);
1027
1028 /* Increment SPF Calculation Counter. */
1029 area->spf_calculation++;
1030
68980084 1031 area->ospf->ts_spf = time (NULL);
718e3744 1032
1033 if (IS_DEBUG_OSPF_EVENT)
1034 zlog_info ("ospf_spf_calculate: Stop");
1035}
1036\f
1037/* Timer for SPF calculation. */
1038int
68980084 1039ospf_spf_calculate_timer (struct thread *thread)
718e3744 1040{
68980084 1041 struct ospf *ospf = THREAD_ARG (thread);
718e3744 1042 struct route_table *new_table, *new_rtrs;
718e3744 1043 listnode node;
1044
1045 if (IS_DEBUG_OSPF_EVENT)
1046 zlog_info ("SPF: Timer (SPF calculation expire)");
1047
718e3744 1048 ospf->t_spf_calc = NULL;
1049
1050 /* Allocate new table tree. */
1051 new_table = route_table_init ();
1052 new_rtrs = route_table_init ();
1053
68980084 1054 ospf_vl_unapprove (ospf);
718e3744 1055
1056 /* Calculate SPF for each area. */
1057 for (node = listhead (ospf->areas); node; node = nextnode (node))
1058 ospf_spf_calculate (node->data, new_table, new_rtrs);
1059
68980084 1060 ospf_vl_shut_unapproved (ospf);
718e3744 1061
68980084 1062 ospf_ia_routing (ospf, new_table, new_rtrs);
718e3744 1063
1064 ospf_prune_unreachable_networks (new_table);
1065 ospf_prune_unreachable_routers (new_rtrs);
1066
1067 /* AS-external-LSA calculation should not be performed here. */
1068
1069 /* If new Router Route is installed,
1070 then schedule re-calculate External routes. */
1071 if (1)
68980084 1072 ospf_ase_calculate_schedule (ospf);
718e3744 1073
68980084 1074 ospf_ase_calculate_timer_add (ospf);
718e3744 1075
1076 /* Update routing table. */
68980084 1077 ospf_route_install (ospf, new_table);
718e3744 1078
1079 /* Update ABR/ASBR routing table */
68980084 1080 if (ospf->old_rtrs)
718e3744 1081 {
1082 /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
68980084 1083 /* ospf_route_delete (ospf->old_rtrs); */
1084 ospf_rtrs_free (ospf->old_rtrs);
718e3744 1085 }
1086
68980084 1087 ospf->old_rtrs = ospf->new_rtrs;
1088 ospf->new_rtrs = new_rtrs;
718e3744 1089
020709f9 1090 if (IS_OSPF_ABR (ospf))
68980084 1091 ospf_abr_task (ospf);
718e3744 1092
1093 if (IS_DEBUG_OSPF_EVENT)
1094 zlog_info ("SPF: calculation complete");
1095
1096 return 0;
1097}
1098
1099/* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1100 set timer for SPF calc. */
1101void
68980084 1102ospf_spf_calculate_schedule (struct ospf *ospf)
718e3744 1103{
1104 time_t ht, delay;
1105
1106 if (IS_DEBUG_OSPF_EVENT)
1107 zlog_info ("SPF: calculation timer scheduled");
1108
1109 /* OSPF instance does not exist. */
68980084 1110 if (ospf == NULL)
718e3744 1111 return;
1112
1113 /* SPF calculation timer is already scheduled. */
68980084 1114 if (ospf->t_spf_calc)
718e3744 1115 {
1116 if (IS_DEBUG_OSPF_EVENT)
1117 zlog_info ("SPF: calculation timer is already scheduled: %p",
68980084 1118 ospf->t_spf_calc);
718e3744 1119 return;
1120 }
1121
68980084 1122 ht = time (NULL) - ospf->ts_spf;
718e3744 1123
1124 /* Get SPF calculation delay time. */
68980084 1125 if (ht < ospf->spf_holdtime)
718e3744 1126 {
68980084 1127 if (ospf->spf_holdtime - ht < ospf->spf_delay)
1128 delay = ospf->spf_delay;
718e3744 1129 else
68980084 1130 delay = ospf->spf_holdtime - ht;
718e3744 1131 }
1132 else
68980084 1133 delay = ospf->spf_delay;
718e3744 1134
1135 if (IS_DEBUG_OSPF_EVENT)
1136 zlog_info ("SPF: calculation timer delay = %ld", delay);
68980084 1137 ospf->t_spf_calc =
1138 thread_add_timer (master, ospf_spf_calculate_timer, ospf, delay);
718e3744 1139}
1140
FRRouting mirror