Annotation of embedaddon/quagga/ospf6d/ospf6_spf.c, revision 1.1.1.1

1.1       misho       1: /*
                      2:  * Copyright (C) 2003 Yasuhiro Ohara
                      3:  *
                      4:  * This file is part of GNU Zebra.
                      5:  *
                      6:  * GNU Zebra is free software; you can redistribute it and/or modify it
                      7:  * under the terms of the GNU General Public License as published by the
                      8:  * Free Software Foundation; either version 2, or (at your option) any
                      9:  * later version.
                     10:  *
                     11:  * GNU Zebra is distributed in the hope that it will be useful, but
                     12:  * WITHOUT ANY WARRANTY; without even the implied warranty of
                     13:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
                     14:  * General Public License for more details.
                     15:  *
                     16:  * You should have received a copy of the GNU General Public License
                     17:  * along with GNU Zebra; see the file COPYING.  If not, write to the 
                     18:  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 
                     19:  * Boston, MA 02111-1307, USA.  
                     20:  */
                     21: 
                     22: /* Shortest Path First calculation for OSPFv3 */
                     23: 
                     24: #include <zebra.h>
                     25: 
                     26: #include "log.h"
                     27: #include "memory.h"
                     28: #include "command.h"
                     29: #include "vty.h"
                     30: #include "prefix.h"
                     31: #include "pqueue.h"
                     32: #include "linklist.h"
                     33: #include "thread.h"
                     34: 
                     35: #include "ospf6_lsa.h"
                     36: #include "ospf6_lsdb.h"
                     37: #include "ospf6_route.h"
                     38: #include "ospf6_area.h"
                     39: #include "ospf6_spf.h"
                     40: #include "ospf6_intra.h"
                     41: #include "ospf6_interface.h"
                     42: #include "ospf6d.h"
                     43: 
                     44: unsigned char conf_debug_ospf6_spf = 0;
                     45: 
                     46: static int
                     47: ospf6_vertex_cmp (void *a, void *b)
                     48: {
                     49:   struct ospf6_vertex *va = (struct ospf6_vertex *) a;
                     50:   struct ospf6_vertex *vb = (struct ospf6_vertex *) b;
                     51: 
                     52:   /* ascending order */
                     53:   if (va->cost != vb->cost)
                     54:     return (va->cost - vb->cost);
                     55:   return (va->hops - vb->hops);
                     56: }
                     57: 
                     58: static int
                     59: ospf6_vertex_id_cmp (void *a, void *b)
                     60: {
                     61:   struct ospf6_vertex *va = (struct ospf6_vertex *) a;
                     62:   struct ospf6_vertex *vb = (struct ospf6_vertex *) b;
                     63:   int ret = 0;
                     64: 
                     65:   ret = ntohl (ospf6_linkstate_prefix_adv_router (&va->vertex_id)) -
                     66:         ntohl (ospf6_linkstate_prefix_adv_router (&vb->vertex_id));
                     67:   if (ret)
                     68:     return ret;
                     69: 
                     70:   ret = ntohl (ospf6_linkstate_prefix_id (&va->vertex_id)) -
                     71:         ntohl (ospf6_linkstate_prefix_id (&vb->vertex_id));
                     72:   return ret;
                     73: }
                     74: 
                     75: static struct ospf6_vertex *
                     76: ospf6_vertex_create (struct ospf6_lsa *lsa)
                     77: {
                     78:   struct ospf6_vertex *v;
                     79:   int i;
                     80: 
                     81:   v = (struct ospf6_vertex *)
                     82:     XMALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_vertex));
                     83: 
                     84:   /* type */
                     85:   if (ntohs (lsa->header->type) == OSPF6_LSTYPE_ROUTER)
                     86:     v->type = OSPF6_VERTEX_TYPE_ROUTER;
                     87:   else if (ntohs (lsa->header->type) == OSPF6_LSTYPE_NETWORK)
                     88:     v->type = OSPF6_VERTEX_TYPE_NETWORK;
                     89:   else
                     90:     assert (0);
                     91: 
                     92:   /* vertex_id */
                     93:   ospf6_linkstate_prefix (lsa->header->adv_router, lsa->header->id,
                     94:                           &v->vertex_id);
                     95: 
                     96:   /* name */
                     97:   ospf6_linkstate_prefix2str (&v->vertex_id, v->name, sizeof (v->name));
                     98: 
                     99:   /* Associated LSA */
                    100:   v->lsa = lsa;
                    101: 
                    102:   /* capability bits + options */
                    103:   v->capability = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header));
                    104:   v->options[0] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 1);
                    105:   v->options[1] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 2);
                    106:   v->options[2] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 3);
                    107: 
                    108:   for (i = 0; i < OSPF6_MULTI_PATH_LIMIT; i++)
                    109:     ospf6_nexthop_clear (&v->nexthop[i]);
                    110: 
                    111:   v->parent = NULL;
                    112:   v->child_list = list_new ();
                    113:   v->child_list->cmp = ospf6_vertex_id_cmp;
                    114: 
                    115:   return v;
                    116: }
                    117: 
                    118: static void
                    119: ospf6_vertex_delete (struct ospf6_vertex *v)
                    120: {
                    121:   list_delete (v->child_list);
                    122:   XFREE (MTYPE_OSPF6_VERTEX, v);
                    123: }
                    124: 
                    125: static struct ospf6_lsa *
                    126: ospf6_lsdesc_lsa (caddr_t lsdesc, struct ospf6_vertex *v)
                    127: {
                    128:   struct ospf6_lsa *lsa;
                    129:   u_int16_t type = 0;
                    130:   u_int32_t id = 0, adv_router = 0;
                    131: 
                    132:   if (VERTEX_IS_TYPE (NETWORK, v))
                    133:     {
                    134:       type = htons (OSPF6_LSTYPE_ROUTER);
                    135:       id = htonl (0);
                    136:       adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc);
                    137:     }
                    138:   else
                    139:     {
                    140:       if (ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc))
                    141:         {
                    142:           type = htons (OSPF6_LSTYPE_ROUTER);
                    143:           id = htonl (0);
                    144:           adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc);
                    145:         }
                    146:       else if (ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, lsdesc))
                    147:         {
                    148:           type = htons (OSPF6_LSTYPE_NETWORK);
                    149:           id = htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc));
                    150:           adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc);
                    151:         }
                    152:     }
                    153: 
                    154:   lsa = ospf6_lsdb_lookup (type, id, adv_router, v->area->lsdb);
                    155: 
                    156:   if (IS_OSPF6_DEBUG_SPF (PROCESS))
                    157:     {
                    158:       char ibuf[16], abuf[16];
                    159:       inet_ntop (AF_INET, &id, ibuf, sizeof (ibuf));
                    160:       inet_ntop (AF_INET, &adv_router, abuf, sizeof (abuf));
                    161:       if (lsa)
                    162:         zlog_debug ("  Link to: %s", lsa->name);
                    163:       else
                    164:         zlog_debug ("  Link to: [%s Id:%s Adv:%s] No LSA",
                    165:                    ospf6_lstype_name (type), ibuf, abuf);
                    166:     }
                    167: 
                    168:   return lsa;
                    169: }
                    170: 
                    171: static char *
                    172: ospf6_lsdesc_backlink (struct ospf6_lsa *lsa,
                    173:                        caddr_t lsdesc, struct ospf6_vertex *v)
                    174: {
                    175:   caddr_t backlink, found = NULL;
                    176:   int size;
                    177: 
                    178:   size = (OSPF6_LSA_IS_TYPE (ROUTER, lsa) ?
                    179:           sizeof (struct ospf6_router_lsdesc) :
                    180:           sizeof (struct ospf6_network_lsdesc));
                    181:   for (backlink = OSPF6_LSA_HEADER_END (lsa->header) + 4;
                    182:        backlink + size <= OSPF6_LSA_END (lsa->header); backlink += size)
                    183:     {
                    184:       assert (! (OSPF6_LSA_IS_TYPE (NETWORK, lsa) &&
                    185:                  VERTEX_IS_TYPE (NETWORK, v)));
                    186: 
                    187:       if (OSPF6_LSA_IS_TYPE (NETWORK, lsa) &&
                    188:           NETWORK_LSDESC_GET_NBR_ROUTERID (backlink)
                    189:             == v->lsa->header->adv_router)
                    190:         found = backlink;
                    191:       else if (VERTEX_IS_TYPE (NETWORK, v) &&
                    192:           ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, backlink) &&
                    193:           ROUTER_LSDESC_GET_NBR_ROUTERID (backlink)
                    194:             == v->lsa->header->adv_router &&
                    195:           ROUTER_LSDESC_GET_NBR_IFID (backlink)
                    196:             == ntohl (v->lsa->header->id))
                    197:         found = backlink;
                    198:       else
                    199:         {
                    200:           if (! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, backlink) ||
                    201:               ! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc))
                    202:             continue;
                    203:           if (ROUTER_LSDESC_GET_NBR_IFID (backlink) !=
                    204:               ROUTER_LSDESC_GET_IFID (lsdesc) ||
                    205:               ROUTER_LSDESC_GET_NBR_IFID (lsdesc) !=
                    206:               ROUTER_LSDESC_GET_IFID (backlink))
                    207:             continue;
                    208:           if (ROUTER_LSDESC_GET_NBR_ROUTERID (backlink) !=
                    209:               v->lsa->header->adv_router ||
                    210:               ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc) !=
                    211:               lsa->header->adv_router)
                    212:             continue;
                    213:           found = backlink;
                    214:         }
                    215:     }
                    216: 
                    217:   if (IS_OSPF6_DEBUG_SPF (PROCESS))
                    218:     zlog_debug ("  Backlink %s", (found ? "OK" : "FAIL"));
                    219: 
                    220:   return found;
                    221: }
                    222: 
                    223: static void
                    224: ospf6_nexthop_calc (struct ospf6_vertex *w, struct ospf6_vertex *v,
                    225:                     caddr_t lsdesc)
                    226: {
                    227:   int i, ifindex;
                    228:   struct ospf6_interface *oi;
                    229:   u_int16_t type;
                    230:   u_int32_t adv_router;
                    231:   struct ospf6_lsa *lsa;
                    232:   struct ospf6_link_lsa *link_lsa;
                    233:   char buf[64];
                    234: 
                    235:   assert (VERTEX_IS_TYPE (ROUTER, w));
                    236:   ifindex = (VERTEX_IS_TYPE (NETWORK, v) ? v->nexthop[0].ifindex :
                    237:              ROUTER_LSDESC_GET_IFID (lsdesc));
                    238:   oi = ospf6_interface_lookup_by_ifindex (ifindex);
                    239:   if (oi == NULL)
                    240:     {
                    241:       if (IS_OSPF6_DEBUG_SPF (PROCESS))
                    242:         zlog_debug ("Can't find interface in SPF: ifindex %d", ifindex);
                    243:       return;
                    244:     }
                    245: 
                    246:   type = htons (OSPF6_LSTYPE_LINK);
                    247:   adv_router = (VERTEX_IS_TYPE (NETWORK, v) ?
                    248:                 NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc) :
                    249:                 ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc));
                    250: 
                    251:   i = 0;
                    252:   for (lsa = ospf6_lsdb_type_router_head (type, adv_router, oi->lsdb); lsa;
                    253:        lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa))
                    254:     {
                    255:       if (VERTEX_IS_TYPE (ROUTER, v) &&
                    256:           htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc)) != lsa->header->id)
                    257:         continue;
                    258: 
                    259:       link_lsa = (struct ospf6_link_lsa *) OSPF6_LSA_HEADER_END (lsa->header);
                    260:       if (IS_OSPF6_DEBUG_SPF (PROCESS))
                    261:         {
                    262:           inet_ntop (AF_INET6, &link_lsa->linklocal_addr, buf, sizeof (buf));
                    263:           zlog_debug ("  nexthop %s from %s", buf, lsa->name);
                    264:         }
                    265: 
                    266:       if (i < OSPF6_MULTI_PATH_LIMIT)
                    267:         {
                    268:           memcpy (&w->nexthop[i].address, &link_lsa->linklocal_addr,
                    269:                   sizeof (struct in6_addr));
                    270:           w->nexthop[i].ifindex = ifindex;
                    271:           i++;
                    272:         }
                    273:     }
                    274: 
                    275:   if (i == 0 && IS_OSPF6_DEBUG_SPF (PROCESS))
                    276:     zlog_debug ("No nexthop for %s found", w->name);
                    277: }
                    278: 
                    279: static int
                    280: ospf6_spf_install (struct ospf6_vertex *v,
                    281:                    struct ospf6_route_table *result_table)
                    282: {
                    283:   struct ospf6_route *route;
                    284:   int i, j;
                    285:   struct ospf6_vertex *prev;
                    286: 
                    287:   if (IS_OSPF6_DEBUG_SPF (PROCESS))
                    288:     zlog_debug ("SPF install %s hops %d cost %d",
                    289:                v->name, v->hops, v->cost);
                    290: 
                    291:   route = ospf6_route_lookup (&v->vertex_id, result_table);
                    292:   if (route && route->path.cost < v->cost)
                    293:     {
                    294:       if (IS_OSPF6_DEBUG_SPF (PROCESS))
                    295:         zlog_debug ("  already installed with lower cost (%d), ignore",
                    296:                    route->path.cost);
                    297:       ospf6_vertex_delete (v);
                    298:       return -1;
                    299:     }
                    300:   else if (route && route->path.cost == v->cost)
                    301:     {
                    302:       if (IS_OSPF6_DEBUG_SPF (PROCESS))
                    303:         zlog_debug ("  another path found, merge");
                    304: 
                    305:       for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) &&
                    306:            i < OSPF6_MULTI_PATH_LIMIT; i++)
                    307:         {
                    308:           for (j = 0; j < OSPF6_MULTI_PATH_LIMIT; j++)
                    309:             {
                    310:               if (ospf6_nexthop_is_set (&route->nexthop[j]))
                    311:                 {
                    312:                   if (ospf6_nexthop_is_same (&route->nexthop[j],
                    313:                                              &v->nexthop[i]))
                    314:                     break;
                    315:                   else
                    316:                     continue;
                    317:                 }
                    318:               ospf6_nexthop_copy (&route->nexthop[j], &v->nexthop[i]);
                    319:               break;
                    320:             }
                    321:         }
                    322: 
                    323:       prev = (struct ospf6_vertex *) route->route_option;
                    324:       assert (prev->hops <= v->hops);
                    325:       ospf6_vertex_delete (v);
                    326: 
                    327:       return -1;
                    328:     }
                    329: 
                    330:   /* There should be no case where candidate being installed (variable
                    331:      "v") is closer than the one in the SPF tree (variable "route").
                    332:      In the case something has gone wrong with the behavior of
                    333:      Priority-Queue. */
                    334: 
                    335:   /* the case where the route exists already is handled and returned
                    336:      up to here. */
                    337:   assert (route == NULL);
                    338: 
                    339:   route = ospf6_route_create ();
                    340:   memcpy (&route->prefix, &v->vertex_id, sizeof (struct prefix));
                    341:   route->type = OSPF6_DEST_TYPE_LINKSTATE;
                    342:   route->path.type = OSPF6_PATH_TYPE_INTRA;
                    343:   route->path.origin.type = v->lsa->header->type;
                    344:   route->path.origin.id = v->lsa->header->id;
                    345:   route->path.origin.adv_router = v->lsa->header->adv_router;
                    346:   route->path.metric_type = 1;
                    347:   route->path.cost = v->cost;
                    348:   route->path.cost_e2 = v->hops;
                    349:   route->path.router_bits = v->capability;
                    350:   route->path.options[0] = v->options[0];
                    351:   route->path.options[1] = v->options[1];
                    352:   route->path.options[2] = v->options[2];
                    353: 
                    354:   for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) &&
                    355:        i < OSPF6_MULTI_PATH_LIMIT; i++)
                    356:     ospf6_nexthop_copy (&route->nexthop[i], &v->nexthop[i]);
                    357: 
                    358:   if (v->parent)
                    359:     listnode_add_sort (v->parent->child_list, v);
                    360:   route->route_option = v;
                    361: 
                    362:   ospf6_route_add (route, result_table);
                    363:   return 0;
                    364: }
                    365: 
                    366: void
                    367: ospf6_spf_table_finish (struct ospf6_route_table *result_table)
                    368: {
                    369:   struct ospf6_route *route;
                    370:   struct ospf6_vertex *v;
                    371:   for (route = ospf6_route_head (result_table); route;
                    372:        route = ospf6_route_next (route))
                    373:     {
                    374:       v = (struct ospf6_vertex *) route->route_option;
                    375:       ospf6_vertex_delete (v);
                    376:       ospf6_route_remove (route, result_table);
                    377:     }
                    378: }
                    379: 
                    380: /* RFC2328 16.1.  Calculating the shortest-path tree for an area */
                    381: /* RFC2740 3.8.1.  Calculating the shortest path tree for an area */
                    382: void
                    383: ospf6_spf_calculation (u_int32_t router_id,
                    384:                        struct ospf6_route_table *result_table,
                    385:                        struct ospf6_area *oa)
                    386: {
                    387:   struct pqueue *candidate_list;
                    388:   struct ospf6_vertex *root, *v, *w;
                    389:   int i;
                    390:   int size;
                    391:   caddr_t lsdesc;
                    392:   struct ospf6_lsa *lsa;
                    393: 
                    394:   /* Install the calculating router itself as the root of the SPF tree */
                    395:   /* construct root vertex */
                    396:   lsa = ospf6_lsdb_lookup (htons (OSPF6_LSTYPE_ROUTER), htonl (0),
                    397:                            router_id, oa->lsdb);
                    398:   if (lsa == NULL)
                    399:     return;
                    400: 
                    401:   /* initialize */
                    402:   candidate_list = pqueue_create ();
                    403:   candidate_list->cmp = ospf6_vertex_cmp;
                    404: 
                    405:   ospf6_spf_table_finish (result_table);
                    406: 
                    407:   root = ospf6_vertex_create (lsa);
                    408:   root->area = oa;
                    409:   root->cost = 0;
                    410:   root->hops = 0;
                    411:   root->nexthop[0].ifindex = 0; /* loopbak I/F is better ... */
                    412:   inet_pton (AF_INET6, "::1", &root->nexthop[0].address);
                    413: 
                    414:   /* Actually insert root to the candidate-list as the only candidate */
                    415:   pqueue_enqueue (root, candidate_list);
                    416: 
                    417:   /* Iterate until candidate-list becomes empty */
                    418:   while (candidate_list->size)
                    419:     {
                    420:       /* get closest candidate from priority queue */
                    421:       v = pqueue_dequeue (candidate_list);
                    422: 
                    423:       /* installing may result in merging or rejecting of the vertex */
                    424:       if (ospf6_spf_install (v, result_table) < 0)
                    425:         continue;
                    426: 
                    427:       /* For each LS description in the just-added vertex V's LSA */
                    428:       size = (VERTEX_IS_TYPE (ROUTER, v) ?
                    429:               sizeof (struct ospf6_router_lsdesc) :
                    430:               sizeof (struct ospf6_network_lsdesc));
                    431:       for (lsdesc = OSPF6_LSA_HEADER_END (v->lsa->header) + 4;
                    432:            lsdesc + size <= OSPF6_LSA_END (v->lsa->header); lsdesc += size)
                    433:         {
                    434:           lsa = ospf6_lsdesc_lsa (lsdesc, v);
                    435:           if (lsa == NULL)
                    436:             continue;
                    437: 
                    438:           if (! ospf6_lsdesc_backlink (lsa, lsdesc, v))
                    439:             continue;
                    440: 
                    441:           w = ospf6_vertex_create (lsa);
                    442:           w->area = oa;
                    443:           w->parent = v;
                    444:           if (VERTEX_IS_TYPE (ROUTER, v))
                    445:             {
                    446:               w->cost = v->cost + ROUTER_LSDESC_GET_METRIC (lsdesc);
                    447:               w->hops = v->hops + (VERTEX_IS_TYPE (NETWORK, w) ? 0 : 1);
                    448:             }
                    449:           else /* NETWORK */
                    450:             {
                    451:               w->cost = v->cost;
                    452:               w->hops = v->hops + 1;
                    453:             }
                    454: 
                    455:           /* nexthop calculation */
                    456:           if (w->hops == 0)
                    457:             w->nexthop[0].ifindex = ROUTER_LSDESC_GET_IFID (lsdesc);
                    458:           else if (w->hops == 1 && v->hops == 0)
                    459:             ospf6_nexthop_calc (w, v, lsdesc);
                    460:           else
                    461:             {
                    462:               for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) &&
                    463:                    i < OSPF6_MULTI_PATH_LIMIT; i++)
                    464:                 ospf6_nexthop_copy (&w->nexthop[i], &v->nexthop[i]);
                    465:             }
                    466: 
                    467:           /* add new candidate to the candidate_list */
                    468:           if (IS_OSPF6_DEBUG_SPF (PROCESS))
                    469:             zlog_debug ("  New candidate: %s hops %d cost %d",
                    470:                        w->name, w->hops, w->cost);
                    471:           pqueue_enqueue (w, candidate_list);
                    472:         }
                    473:     }
                    474: 
                    475:   pqueue_delete (candidate_list);
                    476: }
                    477: 
                    478: static void
                    479: ospf6_spf_log_database (struct ospf6_area *oa)
                    480: {
                    481:   char *p, *end, buffer[256];
                    482:   struct listnode *node;
                    483:   struct ospf6_interface *oi;
                    484: 
                    485:   p = buffer;
                    486:   end = buffer + sizeof (buffer);
                    487: 
                    488:   snprintf (p, end - p, "SPF on DB (#LSAs):");
                    489:   p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
                    490:   snprintf (p, end - p, " Area %s: %d", oa->name, oa->lsdb->count);
                    491:   p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
                    492: 
                    493:   for (ALL_LIST_ELEMENTS_RO (oa->if_list, node, oi))
                    494:     {
                    495:       snprintf (p, end - p, " I/F %s: %d",
                    496:                 oi->interface->name, oi->lsdb->count);
                    497:       p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
                    498:     }
                    499: 
                    500:   zlog_debug ("%s", buffer);
                    501: }
                    502: 
                    503: static int
                    504: ospf6_spf_calculation_thread (struct thread *t)
                    505: {
                    506:   struct ospf6_area *oa;
                    507:   struct timeval start, end, runtime;
                    508: 
                    509:   oa = (struct ospf6_area *) THREAD_ARG (t);
                    510:   oa->thread_spf_calculation = NULL;
                    511: 
                    512:   if (IS_OSPF6_DEBUG_SPF (PROCESS))
                    513:     zlog_debug ("SPF calculation for Area %s", oa->name);
                    514:   if (IS_OSPF6_DEBUG_SPF (DATABASE))
                    515:     ospf6_spf_log_database (oa);
                    516: 
                    517:   /* execute SPF calculation */
                    518:   quagga_gettime (QUAGGA_CLK_MONOTONIC, &start);
                    519:   ospf6_spf_calculation (oa->ospf6->router_id, oa->spf_table, oa);
                    520:   quagga_gettime (QUAGGA_CLK_MONOTONIC, &end);
                    521:   timersub (&end, &start, &runtime);
                    522: 
                    523:   if (IS_OSPF6_DEBUG_SPF (PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
                    524:     zlog_debug ("SPF runtime: %ld sec %ld usec",
                    525:                runtime.tv_sec, runtime.tv_usec);
                    526: 
                    527:   ospf6_intra_route_calculation (oa);
                    528:   ospf6_intra_brouter_calculation (oa);
                    529: 
                    530:   return 0;
                    531: }
                    532: 
                    533: void
                    534: ospf6_spf_schedule (struct ospf6_area *oa)
                    535: {
                    536:   if (oa->thread_spf_calculation)
                    537:     return;
                    538:   oa->thread_spf_calculation =
                    539:     thread_add_event (master, ospf6_spf_calculation_thread, oa, 0);
                    540: }
                    541: 
                    542: void
                    543: ospf6_spf_display_subtree (struct vty *vty, const char *prefix, int rest,
                    544:                            struct ospf6_vertex *v)
                    545: {
                    546:   struct listnode *node, *nnode;
                    547:   struct ospf6_vertex *c;
                    548:   char *next_prefix;
                    549:   int len;
                    550:   int restnum;
                    551: 
                    552:   /* "prefix" is the space prefix of the display line */
                    553:   vty_out (vty, "%s+-%s [%d]%s", prefix, v->name, v->cost, VNL);
                    554: 
                    555:   len = strlen (prefix) + 4;
                    556:   next_prefix = (char *) malloc (len);
                    557:   if (next_prefix == NULL)
                    558:     {
                    559:       vty_out (vty, "malloc failed%s", VNL);
                    560:       return;
                    561:     }
                    562:   snprintf (next_prefix, len, "%s%s", prefix, (rest ? "|  " : "   "));
                    563: 
                    564:   restnum = listcount (v->child_list);
                    565:   for (ALL_LIST_ELEMENTS (v->child_list, node, nnode, c))
                    566:     {
                    567:       restnum--;
                    568:       ospf6_spf_display_subtree (vty, next_prefix, restnum, c);
                    569:     }
                    570: 
                    571:   free (next_prefix);
                    572: }
                    573: 
                    574: DEFUN (debug_ospf6_spf_process,
                    575:        debug_ospf6_spf_process_cmd,
                    576:        "debug ospf6 spf process",
                    577:        DEBUG_STR
                    578:        OSPF6_STR
                    579:        "Debug SPF Calculation\n"
                    580:        "Debug Detailed SPF Process\n"
                    581:       )
                    582: {
                    583:   unsigned char level = 0;
                    584:   level = OSPF6_DEBUG_SPF_PROCESS;
                    585:   OSPF6_DEBUG_SPF_ON (level);
                    586:   return CMD_SUCCESS;
                    587: }
                    588: 
                    589: DEFUN (debug_ospf6_spf_time,
                    590:        debug_ospf6_spf_time_cmd,
                    591:        "debug ospf6 spf time",
                    592:        DEBUG_STR
                    593:        OSPF6_STR
                    594:        "Debug SPF Calculation\n"
                    595:        "Measure time taken by SPF Calculation\n"
                    596:       )
                    597: {
                    598:   unsigned char level = 0;
                    599:   level = OSPF6_DEBUG_SPF_TIME;
                    600:   OSPF6_DEBUG_SPF_ON (level);
                    601:   return CMD_SUCCESS;
                    602: }
                    603: 
                    604: DEFUN (debug_ospf6_spf_database,
                    605:        debug_ospf6_spf_database_cmd,
                    606:        "debug ospf6 spf database",
                    607:        DEBUG_STR
                    608:        OSPF6_STR
                    609:        "Debug SPF Calculation\n"
                    610:        "Log number of LSAs at SPF Calculation time\n"
                    611:       )
                    612: {
                    613:   unsigned char level = 0;
                    614:   level = OSPF6_DEBUG_SPF_DATABASE;
                    615:   OSPF6_DEBUG_SPF_ON (level);
                    616:   return CMD_SUCCESS;
                    617: }
                    618: 
                    619: DEFUN (no_debug_ospf6_spf_process,
                    620:        no_debug_ospf6_spf_process_cmd,
                    621:        "no debug ospf6 spf process",
                    622:        NO_STR
                    623:        DEBUG_STR
                    624:        OSPF6_STR
                    625:        "Quit Debugging SPF Calculation\n"
                    626:        "Quit Debugging Detailed SPF Process\n"
                    627:       )
                    628: {
                    629:   unsigned char level = 0;
                    630:   level = OSPF6_DEBUG_SPF_PROCESS;
                    631:   OSPF6_DEBUG_SPF_OFF (level);
                    632:   return CMD_SUCCESS;
                    633: }
                    634: 
                    635: DEFUN (no_debug_ospf6_spf_time,
                    636:        no_debug_ospf6_spf_time_cmd,
                    637:        "no debug ospf6 spf time",
                    638:        NO_STR
                    639:        DEBUG_STR
                    640:        OSPF6_STR
                    641:        "Quit Debugging SPF Calculation\n"
                    642:        "Quit Measuring time taken by SPF Calculation\n"
                    643:       )
                    644: {
                    645:   unsigned char level = 0;
                    646:   level = OSPF6_DEBUG_SPF_TIME;
                    647:   OSPF6_DEBUG_SPF_OFF (level);
                    648:   return CMD_SUCCESS;
                    649: }
                    650: 
                    651: DEFUN (no_debug_ospf6_spf_database,
                    652:        no_debug_ospf6_spf_database_cmd,
                    653:        "no debug ospf6 spf database",
                    654:        NO_STR
                    655:        DEBUG_STR
                    656:        OSPF6_STR
                    657:        "Debug SPF Calculation\n"
                    658:        "Quit Logging number of LSAs at SPF Calculation time\n"
                    659:       )
                    660: {
                    661:   unsigned char level = 0;
                    662:   level = OSPF6_DEBUG_SPF_DATABASE;
                    663:   OSPF6_DEBUG_SPF_OFF (level);
                    664:   return CMD_SUCCESS;
                    665: }
                    666: 
                    667: int
                    668: config_write_ospf6_debug_spf (struct vty *vty)
                    669: {
                    670:   if (IS_OSPF6_DEBUG_SPF (PROCESS))
                    671:     vty_out (vty, "debug ospf6 spf process%s", VNL);
                    672:   if (IS_OSPF6_DEBUG_SPF (TIME))
                    673:     vty_out (vty, "debug ospf6 spf time%s", VNL);
                    674:   if (IS_OSPF6_DEBUG_SPF (DATABASE))
                    675:     vty_out (vty, "debug ospf6 spf database%s", VNL);
                    676:   return 0;
                    677: }
                    678: 
                    679: void
                    680: install_element_ospf6_debug_spf (void)
                    681: {
                    682:   install_element (ENABLE_NODE, &debug_ospf6_spf_process_cmd);
                    683:   install_element (ENABLE_NODE, &debug_ospf6_spf_time_cmd);
                    684:   install_element (ENABLE_NODE, &debug_ospf6_spf_database_cmd);
                    685:   install_element (ENABLE_NODE, &no_debug_ospf6_spf_process_cmd);
                    686:   install_element (ENABLE_NODE, &no_debug_ospf6_spf_time_cmd);
                    687:   install_element (ENABLE_NODE, &no_debug_ospf6_spf_database_cmd);
                    688:   install_element (CONFIG_NODE, &debug_ospf6_spf_process_cmd);
                    689:   install_element (CONFIG_NODE, &debug_ospf6_spf_time_cmd);
                    690:   install_element (CONFIG_NODE, &debug_ospf6_spf_database_cmd);
                    691:   install_element (CONFIG_NODE, &no_debug_ospf6_spf_process_cmd);
                    692:   install_element (CONFIG_NODE, &no_debug_ospf6_spf_time_cmd);
                    693:   install_element (CONFIG_NODE, &no_debug_ospf6_spf_database_cmd);
                    694: }
                    695: 
                    696: void
                    697: ospf6_spf_init (void)
                    698: {
                    699: }
                    700: 
                    701: 

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>