1/*
2 * Copyright (C) 1999 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/* Shortest Path First calculation for OSPFv3 */
22
23#include "ospf6d.h"
24
25#include "linklist.h"
26#include "prefix.h"
27#include "table.h"
28
29#include "ospf6_proto.h"
30#include "ospf6_lsa.h"
31#include "ospf6_lsdb.h"
32#include "ospf6_route.h"
33#include "ospf6_spf.h"
34#include "ospf6_neighbor.h"
35#include "ospf6_interface.h"
36#include "ospf6_area.h"
37
38#include "ospf6_bintree.h"
39#include "ospf6_linklist.h"
40
41struct bintree *_candidate_list;
42struct linklist *nexthop_list;
43
44struct ospf6_spf_candidate_node
45{
46  u_int32_t cost;
47  struct linklist *list;
48};
49
50int
51ospf6_spf_candidate_node_cmp (void *a, void *b)
52{
53  struct ospf6_spf_candidate_node *ca = a;
54  struct ospf6_spf_candidate_node *cb = b;
55  return ca->cost - cb->cost;
56}
57
58int
59ospf6_spf_vertex_cmp (void *a, void *b)
60{
61  return 1;
62}
63
64void
65ospf6_spf_candidate_node_print (int indent_num, void *node)
66{
67  struct ospf6_spf_candidate_node *cn = node;
68  char format[256];
69
70  snprintf (format, sizeof (format), "%%%ds %%d (num: %%d)",
71            indent_num * 2 + 1);
72  zlog_info (format, " ", cn->cost, cn->list->count);
73}
74
75void
76ospf6_spf_candidate_init ()
77{
78  _candidate_list = bintree_create ();
79  _candidate_list->cmp = ospf6_spf_candidate_node_cmp;
80}
81
82u_int32_t
83ospf6_spf_candidate_count ()
84{
85  u_int32_t count = 0;
86  struct bintree_node node;
87  struct ospf6_spf_candidate_node *cnode;
88
89  for (bintree_head (_candidate_list, &node); ! bintree_end (&node);
90       bintree_next (&node))
91    {
92      cnode = node.data;
93      count += cnode->list->count;
94    }
95
96  return count;
97}
98
99void
100ospf6_spf_candidate_print ()
101{
102  zlog_info ("---------------------------");
103  bintree_print (ospf6_spf_candidate_node_print, _candidate_list);
104  zlog_info ("---------------------------");
105}
106
107void
108ospf6_spf_candidate_enqueue (struct ospf6_vertex *v)
109{
110  struct ospf6_spf_candidate_node req, *node;
111
112  memset (&req, 0, sizeof (req));
113  req.cost = v->distance;
114  node = bintree_lookup (&req, _candidate_list);
115
116  if (node == NULL)
117    {
118      node = malloc (sizeof (struct ospf6_spf_candidate_node));
119      node->cost = v->distance;
120      node->list = linklist_create ();
121      node->list->cmp = ospf6_spf_vertex_cmp;
122      bintree_add (node, _candidate_list);
123    }
124
125  linklist_add (v, node->list);
126
127#if 0
128  if (IS_OSPF6_DUMP_SPF)
129    ospf6_spf_candidate_print ();
130#endif
131}
132
133struct ospf6_vertex *
134ospf6_spf_candidate_dequeue ()
135{
136  struct ospf6_spf_candidate_node *node;
137  struct linklist_node lnode;
138  struct ospf6_vertex *ret;
139
140  node = bintree_lookup_min (_candidate_list);
141  if (node == NULL)
142    return NULL;
143
144  linklist_head (node->list, &lnode);
145  ret = lnode.data;
146
147  linklist_remove (ret, node->list);
148  if (node->list->count == 0)
149    {
150      linklist_delete (node->list);
151      bintree_remove (node, _candidate_list);
152    }
153
154#if 0
155  if (IS_OSPF6_DUMP_SPF)
156    ospf6_spf_candidate_print ();
157#endif
158
159  return ret;
160}
161
162void
163ospf6_spf_candidate_remove (struct ospf6_vertex *v)
164{
165  struct bintree_node node;
166  struct ospf6_spf_candidate_node *cnode = NULL;
167
168  for (bintree_head (_candidate_list, &node); ! bintree_end (&node);
169       bintree_next (&node))
170    {
171      cnode = node.data;
172      if (linklist_lookup (v, cnode->list))
173        {
174          linklist_remove (v, cnode->list);
175          break;
176        }
177    }
178
179  if (cnode->list->count == 0)
180    {
181      linklist_delete (cnode->list);
182      bintree_remove (cnode, _candidate_list);
183    }
184}
185
186
187#define TIMER_SEC_MICRO 1000000
188
189/* timeval calculation */
190static void
191ospf6_timeval_add (const struct timeval *t1, const struct timeval *t2,
192                   struct timeval *result)
193{
194  long moveup = 0;
195
196  result->tv_usec = t1->tv_usec + t2->tv_usec;
197  while (result->tv_usec > TIMER_SEC_MICRO)
198    {
199      result->tv_usec -= TIMER_SEC_MICRO;
200      moveup ++;
201    }
202
203  result->tv_sec = t1->tv_sec + t2->tv_sec + moveup;
204}
205
206static void
207ospf6_timeval_add_equal (const struct timeval *t, struct timeval *result)
208{
209  struct timeval tmp;
210  ospf6_timeval_add (t, result, &tmp);
211  result->tv_sec = tmp.tv_sec;
212  result->tv_usec = tmp.tv_usec;
213}
214
215/* Compare timeval a and b.  It returns an integer less than, equal
216   to, or great than zero if a is found, respectively, to be less
217   than, to match, or be greater than b.  */
218static int
219ospf6_timeval_cmp (const struct timeval t1, const struct timeval t2)
220{
221  return (t1.tv_sec == t2.tv_sec
222	  ? t1.tv_usec - t2.tv_usec : t1.tv_sec - t2.tv_sec);
223}
224
225
226static int
227ospf6_spf_lsd_num (struct ospf6_vertex *V, struct ospf6_area *o6a)
228{
229  u_int16_t type;
230  u_int32_t id, adv_router;
231  struct ospf6_lsa *lsa;
232
233  if (V->vertex_id.id.s_addr)
234    type = htons (OSPF6_LSA_TYPE_NETWORK);
235  else
236    type = htons (OSPF6_LSA_TYPE_ROUTER);
237  id = V->vertex_id.id.s_addr;
238  adv_router = V->vertex_id.adv_router.s_addr;
239
240  lsa = ospf6_lsdb_lookup_lsdb (type, id, adv_router, o6a->lsdb);
241  if (! lsa)
242    {
243      zlog_err ("SPF: Can't find associated LSA for %s", V->string);
244      return 0;
245    }
246
247  return ospf6_lsa_lsd_num ((struct ospf6_lsa_header *) lsa->header);
248}
249
250/* RFC2328 section 16.1.1:
251   Check if there is at least one router in the path
252   from the root to this vertex. */
253static int
254ospf6_spf_is_router_to_root (struct ospf6_vertex *c,
255                             struct ospf6_spftree *spf_tree)
256{
257  listnode node;
258  struct ospf6_vertex *p;
259
260  if (spf_tree->root == c)
261    return 0;
262
263  for (node = listhead (c->parent_list); node; nextnode (node))
264    {
265      p = (struct ospf6_vertex *) getdata (node);
266
267      if (p == spf_tree->root)
268        return 0;
269
270      if (p->vertex_id.id.s_addr == 0) /* this is router */
271        continue;
272      else if (ospf6_spf_is_router_to_root (p, spf_tree))
273        continue;
274
275      return 0;
276    }
277
278  return 1;
279}
280
281static struct in6_addr *
282ospf6_spf_get_ipaddr (u_int32_t id, u_int32_t adv_router, u_int32_t ifindex)
283{
284  char buf[64];
285  struct ospf6_interface *o6i;
286  struct ospf6_neighbor *o6n;
287  struct ospf6_lsa *lsa;
288  struct ospf6_lsdb_node node;
289
290  o6i = ospf6_interface_lookup_by_index (ifindex);
291  if (! o6i)
292    {
293      zlog_err ("SPF: Can't find interface: index %d", ifindex);
294      return (struct in6_addr *) NULL;
295    }
296
297  /* Find Link-LSA of the vertex in question */
298  lsa = NULL;
299  for (ospf6_lsdb_type_router (&node, htons (OSPF6_LSA_TYPE_LINK),
300                               adv_router, o6i->lsdb);
301       ! ospf6_lsdb_is_end (&node);
302       ospf6_lsdb_next (&node))
303    lsa = node.lsa;
304
305  /* return Linklocal Address field if the Link-LSA exists */
306  if (lsa)
307    {
308      struct ospf6_link_lsa *link_lsa;
309      link_lsa = (struct ospf6_link_lsa *) (lsa->header + 1);
310      return &link_lsa->llsa_linklocal;
311    }
312
313  zlog_warn ("SPF: Can't find Link-LSA for %s, "
314             "use source address from his packet",
315             inet_ntop (AF_INET, &adv_router, buf, sizeof (buf)));
316
317  o6n = ospf6_neighbor_lookup (adv_router, o6i);
318  if (! o6n)
319    {
320      inet_ntop (AF_INET, &adv_router, buf, sizeof (buf));
321      zlog_err ("SPF: Can't find neighbor %s in %s",
322                buf, o6i->interface->name);
323      return (struct in6_addr *) NULL;
324    }
325
326  return &o6n->hisaddr;
327}
328
329static int
330ospf6_spf_nexthop_calculation (struct ospf6_vertex *W,
331                               u_int32_t ifindex,
332                               struct ospf6_vertex *V,
333                               struct ospf6_spftree *spf_tree)
334{
335  struct ospf6_nexthop *nexthop, *n;
336  u_int32_t adv_router, id;
337  struct in6_addr nexthop_ipaddr, *ipaddr;
338  unsigned int nexthop_ifindex;
339  struct linklist_node node;
340
341  /* until this, nexthop_list should be untouched */
342  assert (list_isempty (W->nexthop_list));
343
344  /* If ther is at least one intervening router from root to W */
345  if (ospf6_spf_is_router_to_root (W, spf_tree))
346    {
347      /* Create no new nexthop, Inherit from the intervening router */
348      for (linklist_head (V->nexthop_list, &node); ! linklist_end (&node);
349           linklist_next (&node))
350        linklist_add (node.data, W->nexthop_list);
351      return 0;
352    }
353
354  /* Create new nexthop */
355
356  adv_router = W->vertex_id.adv_router.s_addr;
357  id = W->vertex_id.id.s_addr;
358
359  nexthop_ifindex = 0;
360  memset (&nexthop_ipaddr, 0, sizeof (struct in6_addr));
361  if (spf_tree->root && V == spf_tree->root)
362    {
363      nexthop_ifindex = ifindex;
364      if (! id) /* xxx, if V is router */
365        {
366          ipaddr = ospf6_spf_get_ipaddr (id, adv_router, ifindex);
367          if (! ipaddr)
368            {
369              /* xxx, should trigger error and quit SPF calculation... */
370              memset (&nexthop_ipaddr, 0xff, sizeof (struct in6_addr));
371              return -1;
372            }
373          else
374            memcpy (&nexthop_ipaddr, ipaddr, sizeof (struct in6_addr));
375        }
376    }
377  else
378    {
379      /* V is broadcast network, W is router */
380      assert (V->vertex_id.id.s_addr != 0);
381      assert (W->vertex_id.id.s_addr == 0);
382
383      /* there should be the only one nexthop in V */
384      assert (V->nexthop_list->count == 1);
385
386      linklist_head (V->nexthop_list, &node);
387      n = (struct ospf6_nexthop *) node.data;
388      nexthop_ifindex = n->ifindex;
389      ipaddr = ospf6_spf_get_ipaddr (id, adv_router, n->ifindex);
390      if (! ipaddr)
391        {
392          /* xxx, should trigger error and quit SPF calculation... */
393          memset (&nexthop_ipaddr, 0xff, sizeof (struct in6_addr));
394          return -1;
395        }
396      else
397        memcpy (&nexthop_ipaddr, ipaddr, sizeof (struct in6_addr));
398    }
399
400  nexthop = XCALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_nexthop));
401  nexthop->ifindex = nexthop_ifindex;
402  memcpy (&nexthop->address, &nexthop_ipaddr, sizeof (nexthop->address));
403
404  linklist_add (nexthop, W->nexthop_list);
405
406  /* to hold malloced memory */
407  linklist_add (nexthop, nexthop_list);
408
409  return 0;
410}
411
412static struct ospf6_vertex *
413ospf6_spf_vertex_create (int index, struct ospf6_vertex *V,
414                         struct ospf6_area *o6a)
415{
416  struct ospf6_lsa *lsa;
417  struct ospf6_router_lsa *router_lsa;
418  struct ospf6_router_lsd *router_lsd;
419  struct ospf6_network_lsa *network_lsa;
420  struct ospf6_network_lsd *network_lsd;
421  u_int32_t id, adv_router;
422  u_int16_t type;
423  void *lsd;
424  struct ospf6_vertex *W;
425  u_int16_t distance;
426  u_int32_t ifindex;
427  int backreference, lsdnum, i;
428  char buf_router[16], buf_id[16];
429
430  type = id = adv_router = 0;
431
432  /* Get Linkstate description */
433  lsd = ospf6_lsa_lsd_get (index, (struct ospf6_lsa_header *) V->lsa->header);
434  if (! lsd)
435    {
436      zlog_err ("SPF: Can't find %dth Link description from %s",
437                index, V->lsa->str);
438      return (struct ospf6_vertex *) NULL;
439    }
440
441  /* Check Link state description */
442  distance = 0;
443  ifindex = 0;
444  if (V->lsa->header->type == htons (OSPF6_LSA_TYPE_ROUTER))
445    {
446      router_lsd = lsd;
447      if (router_lsd->type == OSPF6_ROUTER_LSD_TYPE_POINTTOPOINT)
448        {
449          type = htons (OSPF6_LSA_TYPE_ROUTER);
450          id = htonl (0);
451        }
452      else if (router_lsd->type == OSPF6_ROUTER_LSD_TYPE_TRANSIT_NETWORK)
453        {
454          type = htons (OSPF6_LSA_TYPE_NETWORK);
455          id = router_lsd->neighbor_interface_id;
456        }
457      adv_router = router_lsd->neighbor_router_id;
458      distance = ntohs (router_lsd->metric);
459      ifindex = ntohl (router_lsd->interface_id);
460    }
461  else if (V->lsa->header->type == htons (OSPF6_LSA_TYPE_NETWORK))
462    {
463      network_lsd = lsd;
464      type = htons (OSPF6_LSA_TYPE_ROUTER);
465      id = htonl (0);
466      adv_router = network_lsd->adv_router;
467    }
468
469  /* Avoid creating candidate of myself */
470  if (adv_router == o6a->ospf6->router_id &&
471      type == htons (OSPF6_LSA_TYPE_ROUTER))
472    {
473      return (struct ospf6_vertex *) NULL;
474    }
475
476  /* Find Associated LSA for W */
477  lsa = ospf6_lsdb_lookup_lsdb (type, id, adv_router, o6a->lsdb);
478
479  if (! lsa)
480    {
481      inet_ntop (AF_INET, &adv_router, buf_router, sizeof (buf_router));
482      inet_ntop (AF_INET, &id, buf_id, sizeof (buf_id));
483
484      if (type == htons (OSPF6_LSA_TYPE_ROUTER))
485        zlog_err ("SPF: Can't find LSA for W (%s *): not found",
486                  buf_router);
487      else
488        zlog_err ("SPF: Can't find LSA for W (%s %s): not found",
489                  buf_router, buf_id);
490      return (struct ospf6_vertex *) NULL;
491    }
492
493  if (IS_LSA_MAXAGE (lsa))
494    {
495      zlog_err ("SPF: Associated LSA for W is MaxAge: %s", lsa->str);
496      return (struct ospf6_vertex *) NULL;
497    }
498
499  /* Check back reference from W's lsa to V's lsa */
500  backreference = 0;
501  lsdnum = ospf6_lsa_lsd_num ((struct ospf6_lsa_header *) lsa->header);
502  for (i = 0; i < lsdnum; i++)
503    {
504      if (ospf6_lsa_lsd_is_refer_ok (i, (struct ospf6_lsa_header *) lsa->header,
505                                     index, (struct ospf6_lsa_header *) V->lsa->header))
506        backreference++;
507    }
508  if (! backreference)
509    {
510      zlog_err ("SPF: Back reference failed: V: %s, W: %s",
511                V->lsa->str, lsa->str);
512      return (struct ospf6_vertex *) NULL;
513    }
514
515  /* Allocate new ospf6_vertex for W */
516  W = (struct ospf6_vertex *) XMALLOC (MTYPE_OSPF6_VERTEX,
517                                       sizeof (struct ospf6_vertex));
518  if (! W)
519    {
520      zlog_err ("SPF: Can't allocate memory for Vertex");
521      return (struct ospf6_vertex *) NULL;
522    }
523  memset (W, 0, sizeof (struct ospf6_vertex));
524
525  /* Initialize */
526  W->vertex_id.family = AF_UNSPEC;
527  W->vertex_id.prefixlen = 64; /* xxx */
528  W->lsa = lsa;
529  if (type == htons (OSPF6_LSA_TYPE_ROUTER))
530    W->vertex_id.id.s_addr = htonl (0); /* XXX */
531  else
532    W->vertex_id.id.s_addr = W->lsa->header->id;
533  W->vertex_id.adv_router.s_addr = W->lsa->header->adv_router;
534  W->nexthop_list = linklist_create ();
535  W->path_list = list_new ();
536  W->parent_list = list_new ();
537  W->distance = V->distance + distance;
538  W->depth = V->depth + 1;
539
540  inet_ntop (AF_INET, &W->vertex_id.adv_router.s_addr,
541             buf_router, sizeof (buf_router));
542  inet_ntop (AF_INET, &W->vertex_id.id.s_addr, buf_id, sizeof (buf_id));
543  snprintf (W->string, sizeof (W->string), "[%s-%s (%d)]",
544            buf_router, buf_id, W->distance);
545
546  /* capability bits and optional capabilities */
547  if (W->vertex_id.id.s_addr == 0)
548    {
549      router_lsa = (struct ospf6_router_lsa *) (W->lsa->header + 1);
550      W->capability_bits = router_lsa->bits;
551      memcpy (W->opt_capability, router_lsa->options,
552              sizeof (W->opt_capability));
553    }
554  else
555    {
556      network_lsa = (struct ospf6_network_lsa *) (W->lsa->header + 1);
557      W->capability_bits = network_lsa->reserved;
558      memcpy (W->opt_capability, network_lsa->options,
559              sizeof (W->opt_capability));
560    }
561
562  /* Link to Parent node */
563  listnode_add (W->parent_list, V);
564
565  /* Nexthop Calculation */
566  if (ospf6_spf_nexthop_calculation (W, ifindex, V, o6a->spf_tree) < 0)
567    return NULL;
568
569  return W;
570}
571
572static void
573ospf6_spf_vertex_delete (struct ospf6_vertex *v)
574{
575  linklist_delete (v->nexthop_list);
576  list_delete (v->path_list);
577  list_delete (v->parent_list);
578  XFREE (MTYPE_OSPF6_VERTEX, v);
579}
580
581static void
582ospf6_spf_vertex_merge (struct ospf6_vertex *w, struct ospf6_vertex *x)
583{
584  listnode node;
585  struct linklist_node lnode;
586
587  /* merge should be done on two nodes which are
588     almost the same */
589
590  /* these w and x should be both candidate.
591     candidate should not have any children */
592  assert (list_isempty (w->path_list));
593  assert (list_isempty (x->path_list));
594
595  /* merge parent list */
596  for (node = listhead (w->parent_list); node; nextnode (node))
597    {
598      if (listnode_lookup (x->parent_list, getdata (node)))
599        continue;
600      listnode_add (x->parent_list, getdata (node));
601    }
602
603  /* merge nexthop list */
604  for (linklist_head (w->nexthop_list, &lnode); ! linklist_end (&lnode);
605       linklist_next (&lnode))
606    linklist_add (lnode.data, x->nexthop_list);
607}
608
609static void
610ospf6_spf_initialize (list candidate_list, struct ospf6_area *o6a)
611{
612  listnode node;
613  struct ospf6_vertex *v;
614  struct ospf6_lsa *lsa;
615  u_int16_t type;
616  u_int32_t id, adv_router;
617  struct linklist_node lnode;
618
619  struct ospf6_nexthop *nexthop;
620  struct interface *ifp;
621  char buf_router[64], buf_id[64];
622
623  /* delete topology routing table for this area */
624  ospf6_route_remove_all (o6a->table_topology);
625
626  /* Delete previous spf tree */
627  for (node = listhead (o6a->spf_tree->list); node; nextnode (node))
628    {
629      v = (struct ospf6_vertex *) getdata (node);
630      ospf6_spf_vertex_delete (v);
631    }
632  list_delete_all_node (o6a->spf_tree->list);
633
634  for (linklist_head (nexthop_list, &lnode); ! linklist_end (&lnode);
635       linklist_next (&lnode))
636    XFREE (MTYPE_OSPF6_VERTEX, lnode.data);
637  linklist_remove_all (nexthop_list);
638
639  /* Find self originated Router-LSA */
640  type = htons (OSPF6_LSA_TYPE_ROUTER);
641  id = htonl (0);
642  adv_router = ospf6->router_id;
643
644  lsa = ospf6_lsdb_lookup_lsdb (type, id, adv_router, o6a->lsdb);
645
646  if (! lsa)
647    {
648      if (IS_OSPF6_DUMP_SPF)
649        zlog_info ("SPF: Can't find self originated Router-LSA");
650      return;
651    }
652  if (IS_LSA_MAXAGE (lsa))
653    {
654      zlog_err ("SPF: MaxAge self originated Router-LSA");
655      return;
656    }
657
658  /* Create root vertex */
659  v = (struct ospf6_vertex *) XMALLOC (MTYPE_OSPF6_VERTEX,
660                                       sizeof (struct ospf6_vertex));
661  if (! v)
662    {
663      zlog_err ("SPF: Can't allocate memory for root vertex");
664      return;
665    }
666  memset (v, 0, sizeof (struct ospf6_vertex));
667
668  v->vertex_id.family = AF_UNSPEC; /* XXX */
669  v->vertex_id.prefixlen = 64; /* XXX */
670  v->vertex_id.id.s_addr = htonl (0);
671  v->vertex_id.adv_router.s_addr = ospf6->router_id;
672  if (ospf6_is_asbr (ospf6))
673    OSPF6_OPT_SET (v->opt_capability, OSPF6_OPT_E);
674  OSPF6_OPT_SET (v->opt_capability, OSPF6_OPT_V6);
675  OSPF6_OPT_SET (v->opt_capability, OSPF6_OPT_R);
676  v->nexthop_list = linklist_create ();
677  v->path_list = list_new ();
678  v->parent_list = list_new ();
679  v->distance = 0;
680  v->depth = 0;
681  v->lsa = lsa;
682
683  inet_ntop (AF_INET, &v->vertex_id.adv_router.s_addr,
684             buf_router, sizeof (buf_router));
685  inet_ntop (AF_INET, &v->vertex_id.id.s_addr, buf_id, sizeof (buf_id));
686  snprintf (v->string, sizeof (v->string), "[%s-%s (%d)]",
687            buf_router, buf_id, v->distance);
688
689  nexthop = XCALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_nexthop));
690  ifp = if_lookup_by_name ("lo0");
691  if (ifp)
692    nexthop->ifindex = ifp->ifindex;
693  inet_pton (AF_INET6, "::1", &nexthop->address);
694  linklist_add (nexthop, v->nexthop_list);
695  linklist_add (nexthop, nexthop_list);
696
697  o6a->spf_tree->root = v;
698  listnode_add (candidate_list, v);
699
700  ospf6_spf_candidate_enqueue (v);
701}
702
703static struct ospf6_vertex *
704ospf6_spf_get_closest_candidate (list candidate_list)
705{
706  listnode node;
707  struct ospf6_vertex *candidate, *closest;
708
709  closest = (struct ospf6_vertex *) NULL;
710  for (node = listhead (candidate_list); node; nextnode (node))
711    {
712      candidate = (struct ospf6_vertex *) getdata (node);
713
714      if (closest && candidate->distance > closest->distance)
715        continue;
716
717      /* always choose network vertices if those're the same cost */
718      if (closest && candidate->distance == closest->distance
719          && closest->vertex_id.id.s_addr != 0)
720        continue;
721
722      closest = candidate;
723    }
724
725  return closest;
726}
727
728static struct ospf6_vertex *
729ospf6_spf_get_same_candidate (struct ospf6_vertex *w, list candidate_list)
730{
731  listnode node;
732  struct ospf6_vertex *c, *same;
733
734  same = (struct ospf6_vertex *) NULL;
735  for (node = listhead (candidate_list); node; nextnode (node))
736    {
737      c = (struct ospf6_vertex *) getdata (node);
738      if (w->vertex_id.adv_router.s_addr != c->vertex_id.adv_router.s_addr)
739        continue;
740      if (w->vertex_id.id.s_addr != c->vertex_id.id.s_addr)
741        continue;
742
743      if (same)
744        zlog_warn ("SPF: duplicate candidates in candidate_list");
745
746      same = c;
747    }
748
749  return same;
750}
751
752static void
753ospf6_spf_install (struct ospf6_vertex *vertex, struct ospf6_area *o6a)
754{
755  listnode node;
756  struct ospf6_vertex *parent;
757  struct ospf6_nexthop *nexthop;
758  struct ospf6_route_req request;
759  struct linklist_node lnode;
760
761  struct ospf6_router_lsa *router_lsa;
762  struct ospf6_network_lsa *network_lsa;
763
764  router_lsa = OSPF6_LSA_HEADER_END (vertex->lsa->header);
765  network_lsa = OSPF6_LSA_HEADER_END (vertex->lsa->header);
766
767  if (IS_OSPF6_DUMP_SPF)
768    {
769      zlog_info ("SPF: Install: %s", vertex->string);
770    }
771
772  listnode_add (o6a->spf_tree->list, vertex);
773
774  for (node = listhead (vertex->parent_list); node; nextnode (node))
775    {
776      parent = (struct ospf6_vertex *) getdata (node);
777      listnode_add (parent->path_list, vertex);
778      vertex->depth = parent->depth + 1;
779    }
780
781#if 0
782  if (vertex == o6a->spf_tree->root)
783    return;
784#endif /*0*/
785
786  /* install route to topology table */
787  memset (&request, 0, sizeof (request));
788  if (vertex->vertex_id.id.s_addr) /* xxx */
789    request.route.type = OSPF6_DEST_TYPE_NETWORK;
790  else
791    request.route.type = OSPF6_DEST_TYPE_ROUTER;
792  memcpy (&request.route.prefix, &vertex->vertex_id,
793          sizeof (struct prefix));
794
795  request.path.area_id = o6a->area_id;
796  request.path.type = OSPF6_PATH_TYPE_INTRA;
797  request.path.cost = vertex->distance;
798  request.path.cost_e2 = 0;
799  request.path.origin.type = vertex->lsa->header->type;
800  request.path.origin.id = vertex->lsa->header->id;
801  request.path.origin.adv_router = vertex->lsa->header->adv_router;
802  if (vertex->lsa->header->type == htons (OSPF6_LSA_TYPE_ROUTER))
803    request.path.router_bits = router_lsa->bits;
804  memcpy (&request.path.capability, vertex->opt_capability,
805          sizeof (request.path.capability));
806
807#if 0
808  if (IS_OSPF6_DUMP_SPF)
809    zlog_info ("SPF:   install %d nexthops for %s",
810               listcount (vertex->nexthop_list), vertex->string);
811#endif
812
813  for (linklist_head (vertex->nexthop_list, &lnode); ! linklist_end (&lnode);
814       linklist_next (&lnode))
815    {
816      nexthop = lnode.data;
817
818      request.nexthop.ifindex = nexthop->ifindex;
819      memcpy (&request.nexthop.address, &nexthop->address,
820              sizeof (request.nexthop.address));
821
822      ospf6_route_add (&request, o6a->table_topology);
823    }
824}
825
826struct ospf6_vertex *
827ospf6_spf_lookup (struct ospf6_vertex *w, struct ospf6_area *o6a)
828{
829  listnode node;
830  struct ospf6_vertex *v;
831
832  for (node = listhead (o6a->spf_tree->list); node; nextnode (node))
833    {
834      v = (struct ospf6_vertex *) getdata (node);
835
836      if (w->vertex_id.adv_router.s_addr != v->vertex_id.adv_router.s_addr)
837        continue;
838      if (w->vertex_id.id.s_addr != v->vertex_id.id.s_addr)
839        continue;
840
841      return v;
842    }
843
844  return (struct ospf6_vertex *) NULL;
845}
846
847u_int32_t stat_node = 0;
848u_int32_t stat_candidate = 0;
849u_int32_t stat_candidate_max = 0;
850u_int32_t stat_spf = 0;
851
852
853/* RFC2328 section 16.1 , RFC2740 section 3.8.1 */
854static int
855ospf6_spf_calculation (struct ospf6_area *o6a)
856{
857  list candidate_list;
858  struct ospf6_vertex *V, *W, *X;
859  int ldnum, i;
860
861  if (! o6a || ! o6a->spf_tree)
862    {
863      zlog_err ("SPF: Can't calculate SPF tree: malformed area");
864      return -1;
865    }
866
867  stat_spf ++;
868  stat_node = 0;
869  stat_candidate = 0;
870  stat_candidate_max = 0;
871
872  if (IS_OSPF6_DUMP_SPF)
873    zlog_info ("SPF: Calculation for area %s", o6a->str);
874
875  ospf6_route_table_freeze (o6a->table_topology);
876  ospf6_route_remove_all (o6a->table_topology);
877
878  /* (1): Initialize the algorithm's data structures */
879  candidate_list = list_new ();
880  ospf6_spf_initialize (candidate_list, o6a);
881  stat_candidate ++;
882
883  /* (3): Install closest from candidate list; if empty, break */
884  while (listcount (candidate_list))
885    {
886      V = ospf6_spf_get_closest_candidate (candidate_list);
887      listnode_delete (candidate_list, V);
888
889      {
890        struct ospf6_vertex *V_;
891
892        if (stat_candidate_max < ospf6_spf_candidate_count ())
893          stat_candidate_max = ospf6_spf_candidate_count ();
894
895        V_ = ospf6_spf_candidate_dequeue ();
896
897#if 0
898        if (IS_OSPF6_DUMP_SPF)
899          {
900            zlog_info ("Candidate list count: %lu",
901                       (u_long)ospf6_spf_candidate_count ());
902            zlog_info ("*** Candidate %s: %p <-> %p",
903                       (V == V_ ? "same" : "*** differ ***"), V, V_);
904            zlog_info ("  %p: %s", V, V->string);
905            zlog_info ("  %p: %s", V_, V_->string);
906          }
907#endif
908
909      }
910
911      stat_node++;
912      ospf6_spf_install (V, o6a);
913
914      /* (2): Examin LSA of just added vertex */
915      ldnum = ospf6_spf_lsd_num (V, o6a);
916      for (i = 0; i < ldnum; i++)
917        {
918          /* (b): If no LSA, or MaxAge, or LinkBack fail, examin next */
919          W = ospf6_spf_vertex_create (i, V, o6a);
920          if (! W)
921            continue;
922
923          stat_candidate ++;
924
925          /* (c) */
926          if (ospf6_spf_lookup (W, o6a))
927            {
928              if (IS_OSPF6_DUMP_SPF)
929                zlog_info ("SPF:   %s: Already in SPF tree", W->string);
930              ospf6_spf_vertex_delete (W);
931              continue;
932            }
933
934          /* (d) */
935          X = ospf6_spf_get_same_candidate (W, candidate_list);
936          if (X && X->distance < W->distance)
937            {
938              if (IS_OSPF6_DUMP_SPF)
939                zlog_info ("SPF:   %s: More closer found", W->string);
940              ospf6_spf_vertex_delete (W);
941              continue;
942            }
943          if (X && X->distance == W->distance)
944            {
945              if (IS_OSPF6_DUMP_SPF)
946                zlog_info ("SPF:   %s: new ECMP candidate", W->string);
947              ospf6_spf_vertex_merge (W, X);
948              ospf6_spf_vertex_delete (W);
949              continue;
950            }
951
952          if (X)
953            {
954              if (IS_OSPF6_DUMP_SPF)
955                zlog_info ("SPF:   %s: Swap with old candidate", W->string);
956              listnode_delete (candidate_list, X);
957              ospf6_spf_candidate_remove (X);
958              ospf6_spf_vertex_delete (X);
959            }
960          else
961            {
962              if (IS_OSPF6_DUMP_SPF)
963                zlog_info ("SPF:   %s: New Candidate", W->string);
964            }
965
966          if (stat_candidate_max < ospf6_spf_candidate_count ())
967            stat_candidate_max = ospf6_spf_candidate_count ();
968
969          listnode_add (candidate_list, W);
970          ospf6_spf_candidate_enqueue (W);
971        }
972    }
973
974  assert (listcount (candidate_list) == 0);
975  list_free (candidate_list);
976  assert (ospf6_spf_candidate_count () == 0);
977
978  /* Clear thread timer */
979  o6a->spf_tree->t_spf_calculation = (struct thread *) NULL;
980
981  if (IS_OSPF6_DUMP_SPF)
982    {
983      zlog_info ("SPF: Calculation for area %s done", o6a->str);
984      zlog_info ("SPF:   Statistics: %luth", (u_long)stat_spf);
985      zlog_info ("SPF:   Node Number: %lu", (u_long)stat_node);
986      zlog_info ("SPF:   Candidate Number: %lu Max: %lu",
987                 (u_long) stat_candidate, (u_long) stat_candidate_max);
988    }
989
990  ospf6_route_table_thaw (o6a->table_topology);
991  return 0;
992}
993
994int
995ospf6_spf_calculation_thread (struct thread *t)
996{
997  struct ospf6_area *o6a;
998  struct timeval start, end, runtime, interval;
999
1000  o6a = (struct ospf6_area *) THREAD_ARG (t);
1001  if (! o6a)
1002    {
1003      zlog_err ("SPF: Thread error");
1004      return -1;
1005    }
1006
1007  if (! o6a->spf_tree)
1008    {
1009      zlog_err ("SPF: Can't find SPF Tree for area: %s", o6a->str);
1010      return -1;
1011    }
1012
1013  /* execute SPF calculation */
1014  gettimeofday (&start, (struct timezone *) NULL);
1015  ospf6_spf_calculation (o6a);
1016  gettimeofday (&end, (struct timezone *) NULL);
1017
1018  /* update statistics */
1019  o6a->spf_tree->timerun ++;
1020  ospf6_timeval_sub (&end, &start, &runtime);
1021  ospf6_timeval_add_equal (&runtime, &o6a->spf_tree->runtime_total);
1022
1023  if (o6a->spf_tree->timerun == 1)
1024    {
1025      o6a->spf_tree->runtime_min.tv_sec = runtime.tv_sec;
1026      o6a->spf_tree->runtime_min.tv_usec = runtime.tv_usec;
1027      o6a->spf_tree->runtime_max.tv_sec = runtime.tv_sec;
1028      o6a->spf_tree->runtime_max.tv_usec = runtime.tv_usec;
1029    }
1030  if (ospf6_timeval_cmp (o6a->spf_tree->runtime_min, runtime) > 0)
1031    {
1032      o6a->spf_tree->runtime_min.tv_sec = runtime.tv_sec;
1033      o6a->spf_tree->runtime_min.tv_usec = runtime.tv_usec;
1034    }
1035  if (ospf6_timeval_cmp (runtime, o6a->spf_tree->runtime_max) > 0)
1036    {
1037      o6a->spf_tree->runtime_max.tv_sec = runtime.tv_sec;
1038      o6a->spf_tree->runtime_max.tv_usec = runtime.tv_usec;
1039    }
1040
1041  if (o6a->spf_tree->timerun == 1)
1042    {
1043      ospf6_timeval_sub (&start, &ospf6->starttime, &interval);
1044      ospf6_timeval_add_equal (&interval, &o6a->spf_tree->interval_total);
1045      o6a->spf_tree->interval_min.tv_sec = interval.tv_sec;
1046      o6a->spf_tree->interval_min.tv_usec = interval.tv_usec;
1047      o6a->spf_tree->interval_max.tv_sec = interval.tv_sec;
1048      o6a->spf_tree->interval_max.tv_usec = interval.tv_usec;
1049    }
1050  else
1051    {
1052      ospf6_timeval_sub (&start, &o6a->spf_tree->updated_time, &interval);
1053      ospf6_timeval_add_equal (&interval, &o6a->spf_tree->interval_total);
1054      if (ospf6_timeval_cmp (o6a->spf_tree->interval_min, interval) > 0)
1055        {
1056          o6a->spf_tree->interval_min.tv_sec = interval.tv_sec;
1057          o6a->spf_tree->interval_min.tv_usec = interval.tv_usec;
1058        }
1059      if (ospf6_timeval_cmp (interval, o6a->spf_tree->interval_max) > 0)
1060        {
1061          o6a->spf_tree->interval_max.tv_sec = interval.tv_sec;
1062          o6a->spf_tree->interval_max.tv_usec = interval.tv_usec;
1063        }
1064    }
1065  o6a->spf_tree->updated_time.tv_sec = end.tv_sec;
1066  o6a->spf_tree->updated_time.tv_usec = end.tv_usec;
1067
1068  /* clear thread */
1069  o6a->spf_tree->t_spf_calculation = (struct thread *) NULL;
1070
1071  return 0;
1072}
1073
1074void
1075ospf6_spf_database_hook (struct ospf6_lsa *old, struct ospf6_lsa *new)
1076{
1077  struct ospf6_area *o6a = NULL;
1078  struct ospf6_interface *o6i = NULL;
1079
1080  if (new->header->type == htons (OSPF6_LSA_TYPE_ROUTER) ||
1081      new->header->type == htons (OSPF6_LSA_TYPE_NETWORK))
1082    o6a = new->scope;
1083  else if (new->header->type == htons (OSPF6_LSA_TYPE_LINK))
1084    {
1085      o6i = new->scope;
1086      o6a = o6i->area;
1087    }
1088
1089  if (o6a)
1090    ospf6_spf_calculation_schedule (o6a->area_id);
1091}
1092
1093void
1094ospf6_spf_calculation_schedule (u_int32_t area_id)
1095{
1096  struct ospf6_area *o6a;
1097  char buf[64];
1098
1099  o6a = ospf6_area_lookup (area_id, ospf6);
1100  if (! o6a)
1101    {
1102      inet_ntop (AF_INET, &area_id, buf, sizeof (buf));
1103      zlog_err ("SPF: Can't find area: %s", buf);
1104      return;
1105    }
1106
1107  if (! o6a->spf_tree)
1108    {
1109      zlog_err ("SPF: Can't find SPF Tree for area: %s", o6a->str);
1110      return;
1111    }
1112
1113  if (o6a->spf_tree->t_spf_calculation)
1114    return;
1115
1116  o6a->spf_tree->t_spf_calculation =
1117    thread_add_event (master, ospf6_spf_calculation_thread, o6a, 0);
1118}
1119
1120struct ospf6_spftree *
1121ospf6_spftree_create ()
1122{
1123  struct ospf6_spftree *spf_tree;
1124  spf_tree = (struct ospf6_spftree *) XMALLOC (MTYPE_OSPF6_SPFTREE,
1125                                               sizeof (struct ospf6_spftree));
1126  if (! spf_tree)
1127    {
1128      zlog_err ("SPF: Can't allocate memory for SPF tree");
1129      return (struct ospf6_spftree *) NULL;
1130    }
1131  memset (spf_tree, 0, sizeof (spf_tree));
1132
1133  spf_tree->list = list_new ();
1134
1135  return spf_tree;
1136}
1137
1138void
1139ospf6_spftree_delete (struct ospf6_spftree *spf_tree)
1140{
1141  listnode node;
1142  struct ospf6_vertex *v;
1143
1144  /* Delete spf tree */
1145  for (node = listhead (spf_tree->list); node; nextnode (node))
1146    {
1147      v = (struct ospf6_vertex *) getdata (node);
1148      ospf6_spf_vertex_delete (v);
1149    }
1150  list_delete_all_node (spf_tree->list);
1151
1152  XFREE (MTYPE_OSPF6_SPFTREE, spf_tree);
1153}
1154
1155void
1156ospf6_nexthop_show (struct vty *vty, struct ospf6_nexthop *nexthop)
1157{
1158  char buf[128], *ifname;
1159  struct ospf6_interface *o6i;
1160
1161  ifname = NULL;
1162
1163  o6i = ospf6_interface_lookup_by_index (nexthop->ifindex);
1164  if (! o6i)
1165    {
1166      zlog_err ("Spf: invalid ifindex %d in nexthop", nexthop->ifindex);
1167    }
1168  else
1169    ifname = o6i->interface->name;
1170
1171  inet_ntop (AF_INET6, &nexthop->address, buf, sizeof (buf));
1172  vty_out (vty, "    %s%%%s(%d)%s", buf, ifname,
1173           nexthop->ifindex, VTY_NEWLINE);
1174}
1175
1176void
1177ospf6_vertex_show (struct vty *vty, struct ospf6_vertex *vertex)
1178{
1179  listnode node;
1180  struct ospf6_vertex *v;
1181  struct linklist_node lnode;
1182
1183  vty_out (vty, "SPF node %s%s", vertex->string, VTY_NEWLINE);
1184  vty_out (vty, "  cost to this node: %d%s", vertex->distance, VTY_NEWLINE);
1185  vty_out (vty, "  hops to this node: %d%s", vertex->depth, VTY_NEWLINE);
1186
1187  vty_out (vty, "  nexthops reachable to this node:%s", VTY_NEWLINE);
1188  for (linklist_head (vertex->nexthop_list, &lnode);
1189       ! linklist_end (&lnode);
1190       linklist_next (&lnode))
1191    ospf6_nexthop_show (vty, (struct ospf6_nexthop *) lnode.data);
1192
1193  vty_out (vty, "  parent nodes to this node:%s", VTY_NEWLINE);
1194  if (! list_isempty (vertex->parent_list))
1195    vty_out (vty, "    ");
1196  for (node = listhead (vertex->parent_list); node; nextnode (node))
1197    {
1198      v = (struct ospf6_vertex *) getdata (node);
1199      vty_out (vty, "%s ", v->string);
1200    }
1201  if (! list_isempty (vertex->parent_list))
1202    vty_out (vty, "%s", VTY_NEWLINE);
1203
1204  vty_out (vty, "  child nodes to this node:%s", VTY_NEWLINE);
1205  if (! list_isempty (vertex->path_list))
1206    vty_out (vty, "    ");
1207  for (node = listhead (vertex->path_list); node; nextnode (node))
1208    {
1209      v = (struct ospf6_vertex *) getdata (node);
1210      vty_out (vty, "%s ", v->string);
1211    }
1212  if (! list_isempty (vertex->path_list))
1213    vty_out (vty, "%s", VTY_NEWLINE);
1214
1215  vty_out (vty, "%s", VTY_NEWLINE);
1216}
1217
1218void
1219ospf6_spf_statistics_show (struct vty *vty, struct ospf6_spftree *spf_tree)
1220{
1221  listnode node;
1222  struct ospf6_vertex *vertex;
1223  u_int router_count, network_count, maxdepth;
1224  struct timeval runtime_avg, interval_avg, last_updated, now;
1225  char rmin[64], rmax[64], ravg[64];
1226  char imin[64], imax[64], iavg[64];
1227  char last_updated_string[64];
1228
1229  maxdepth = router_count = network_count = 0;
1230  for (node = listhead (spf_tree->list); node; nextnode (node))
1231    {
1232      vertex = (struct ospf6_vertex *) getdata (node);
1233      if (vertex->vertex_id.id.s_addr)
1234        network_count++;
1235      else
1236        router_count++;
1237      if (maxdepth < vertex->depth)
1238        maxdepth = vertex->depth;
1239    }
1240
1241  ospf6_timeval_div (&spf_tree->runtime_total, spf_tree->timerun,
1242                     &runtime_avg);
1243  ospf6_timeval_string (&spf_tree->runtime_min, rmin, sizeof (rmin));
1244  ospf6_timeval_string (&spf_tree->runtime_max, rmax, sizeof (rmax));
1245  ospf6_timeval_string (&runtime_avg, ravg, sizeof (ravg));
1246
1247  ospf6_timeval_div (&spf_tree->interval_total, spf_tree->timerun,
1248                     &interval_avg);
1249  ospf6_timeval_string (&spf_tree->interval_min, imin, sizeof (imin));
1250  ospf6_timeval_string (&spf_tree->interval_max, imax, sizeof (imax));
1251  ospf6_timeval_string (&interval_avg, iavg, sizeof (iavg));
1252
1253  gettimeofday (&now, (struct timezone *) NULL);
1254  ospf6_timeval_sub (&now, &spf_tree->updated_time, &last_updated);
1255  ospf6_timeval_string (&last_updated, last_updated_string,
1256                        sizeof (last_updated_string));
1257
1258  vty_out (vty, "     SPF algorithm executed %d times%s",
1259           spf_tree->timerun, VTY_NEWLINE);
1260  vty_out (vty, "     Average time to run SPF: %s%s",
1261           ravg, VTY_NEWLINE);
1262  vty_out (vty, "     Maximum time to run SPF: %s%s",
1263           rmax, VTY_NEWLINE);
1264  vty_out (vty, "     Average interval of SPF: %s%s",
1265           iavg, VTY_NEWLINE);
1266  vty_out (vty, "     SPF last updated: %s ago%s",
1267           last_updated_string, VTY_NEWLINE);
1268  vty_out (vty, "     Current SPF node count: %d%s",
1269           listcount (spf_tree->list), VTY_NEWLINE);
1270  vty_out (vty, "       Router: %d Network: %d%s",
1271           router_count, network_count, VTY_NEWLINE);
1272  vty_out (vty, "       Maximum of Hop count to nodes: %d%s",
1273           maxdepth, VTY_NEWLINE);
1274}
1275
1276DEFUN (show_ipv6_ospf6_area_spf_node,
1277       show_ipv6_ospf6_area_spf_node_cmd,
1278       "show ipv6 ospf6 area A.B.C.D spf node",
1279       SHOW_STR
1280       IP6_STR
1281       OSPF6_STR
1282       OSPF6_AREA_STR
1283       OSPF6_AREA_ID_STR
1284       "Shortest Path First caculation\n"
1285       "vertex infomation\n"
1286       )
1287{
1288  listnode i;
1289  u_int32_t area_id;
1290  struct ospf6_area *o6a;
1291  struct ospf6_vertex *vertex;
1292
1293  OSPF6_CMD_CHECK_RUNNING ();
1294
1295  inet_pton (AF_INET, argv[0], &area_id);
1296  o6a = ospf6_area_lookup (area_id, ospf6);
1297  if (! o6a)
1298    return CMD_SUCCESS;
1299
1300  for (i = listhead (o6a->spf_tree->list); i; nextnode (i))
1301    {
1302      vertex = (struct ospf6_vertex *) getdata (i);
1303      ospf6_vertex_show (vty, vertex);
1304    }
1305
1306  return CMD_SUCCESS;
1307}
1308
1309static void
1310ospf6_spftree_show (struct vty *vty, char *prefix, int current_rest,
1311                    struct ospf6_vertex *v)
1312{
1313  char *p;
1314  int psize;
1315  int restnum;
1316  listnode node;
1317
1318  vty_out (vty, "%s+-%s%s", prefix, v->string, VTY_NEWLINE);
1319
1320  if (listcount (v->path_list) == 0)
1321    return;
1322
1323  psize = strlen (prefix) + 3;
1324  p = malloc (psize);
1325  if (!p)
1326    {
1327      vty_out (vty, "depth too long ...%s", VTY_NEWLINE);
1328      return;
1329    }
1330
1331  restnum = listcount (v->path_list);
1332  for (node = listhead (v->path_list); node; nextnode (node))
1333    {
1334      --restnum;
1335      snprintf (p, psize, "%s%s", prefix, (current_rest ? "| " : "  "));
1336      ospf6_spftree_show (vty, p, restnum,
1337                          (struct ospf6_vertex *) getdata (node));
1338    }
1339
1340  free (p);
1341}
1342
1343DEFUN (show_ipv6_ospf6_area_spf_tree,
1344       show_ipv6_ospf6_area_spf_tree_cmd,
1345       "show ipv6 ospf6 area A.B.C.D spf tree",
1346       SHOW_STR
1347       IP6_STR
1348       OSPF6_STR
1349       OSPF6_AREA_STR
1350       OSPF6_AREA_ID_STR
1351       "Shortest Path First caculation\n"
1352       "Displays spf tree\n")
1353{
1354  u_int32_t area_id;
1355  struct ospf6_area *o6a;
1356
1357  OSPF6_CMD_CHECK_RUNNING ();
1358
1359  inet_pton (AF_INET, argv[0], &area_id);
1360  o6a = ospf6_area_lookup (area_id, ospf6);
1361  if (! o6a)
1362    return CMD_SUCCESS;
1363
1364  vty_out (vty, "%s        SPF tree for Area %s%s%s",
1365           VTY_NEWLINE, o6a->str, VTY_NEWLINE, VTY_NEWLINE);
1366
1367  if (! o6a->spf_tree->root)
1368    return CMD_SUCCESS;
1369
1370  ospf6_spftree_show (vty, "", 0, o6a->spf_tree->root);
1371  return CMD_SUCCESS;
1372}
1373
1374DEFUN (show_ipv6_ospf6_area_topology,
1375       show_ipv6_ospf6_area_topology_cmd,
1376       "show ipv6 ospf6 area A.B.C.D topology",
1377       SHOW_STR
1378       IP6_STR
1379       OSPF6_STR
1380       OSPF6_AREA_STR
1381       OSPF6_AREA_ID_STR
1382       OSPF6_SPF_STR
1383       "Displays SPF topology table\n")
1384{
1385  struct ospf6_area *o6a;
1386  u_int32_t area_id;
1387
1388  OSPF6_CMD_CHECK_RUNNING ();
1389
1390  inet_pton (AF_INET, argv[0], &area_id);
1391  o6a = ospf6_area_lookup (area_id, ospf6);
1392
1393  if (! o6a)
1394    return CMD_SUCCESS;
1395
1396  argc -= 1;
1397  argv += 1;
1398
1399  return ospf6_route_table_show (vty, argc, argv, o6a->table_topology);
1400}
1401
1402ALIAS (show_ipv6_ospf6_area_topology,
1403       show_ipv6_ospf6_area_topology_router_cmd,
1404       "show ipv6 ospf6 area A.B.C.D topology (A.B.C.D|<0-4294967295>|detail)",
1405       SHOW_STR
1406       IP6_STR
1407       OSPF6_STR
1408       OSPF6_AREA_STR
1409       OSPF6_AREA_ID_STR
1410       OSPF6_SPF_STR
1411       "Displays SPF topology table\n"
1412       OSPF6_ROUTER_ID_STR
1413       OSPF6_ROUTER_ID_STR
1414       )
1415
1416ALIAS (show_ipv6_ospf6_area_topology,
1417       show_ipv6_ospf6_area_topology_router_lsid_cmd,
1418       "show ipv6 ospf6 area A.B.C.D topology (A.B.C.D|<0-4294967295>) (A.B.C.D|<0-4294967295>)",
1419       SHOW_STR
1420       IP6_STR
1421       OSPF6_STR
1422       OSPF6_AREA_STR
1423       OSPF6_AREA_ID_STR
1424       OSPF6_SPF_STR
1425       "Displays SPF topology table\n"
1426       OSPF6_ROUTER_ID_STR
1427       OSPF6_ROUTER_ID_STR
1428       OSPF6_LS_ID_STR
1429       OSPF6_LS_ID_STR
1430       )
1431
1432void
1433ospf6_spf_init ()
1434{
1435  nexthop_list = linklist_create ();
1436  ospf6_spf_candidate_init ();
1437  install_element (VIEW_NODE, &show_ipv6_ospf6_area_spf_node_cmd);
1438  install_element (VIEW_NODE, &show_ipv6_ospf6_area_spf_tree_cmd);
1439  install_element (VIEW_NODE, &show_ipv6_ospf6_area_topology_cmd);
1440  install_element (VIEW_NODE, &show_ipv6_ospf6_area_topology_router_cmd);
1441  install_element (VIEW_NODE, &show_ipv6_ospf6_area_topology_router_lsid_cmd);
1442  install_element (ENABLE_NODE, &show_ipv6_ospf6_area_spf_node_cmd);
1443  install_element (ENABLE_NODE, &show_ipv6_ospf6_area_spf_tree_cmd);
1444  install_element (ENABLE_NODE, &show_ipv6_ospf6_area_topology_cmd);
1445  install_element (ENABLE_NODE, &show_ipv6_ospf6_area_topology_router_cmd);
1446  install_element (ENABLE_NODE, &show_ipv6_ospf6_area_topology_router_lsid_cmd);
1447}
1448
1449