Annotation of embedaddon/quagga/ospfd/ospf_spf.c, revision 1.1.1.1

1.1       misho       1: /* OSPF SPF calculation.
                      2:    Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
                      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 Free
                     18: Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
                     19: 02111-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: #include "pqueue.h"
                     33: 
                     34: #include "ospfd/ospfd.h"
                     35: #include "ospfd/ospf_interface.h"
                     36: #include "ospfd/ospf_ism.h"
                     37: #include "ospfd/ospf_asbr.h"
                     38: #include "ospfd/ospf_lsa.h"
                     39: #include "ospfd/ospf_lsdb.h"
                     40: #include "ospfd/ospf_neighbor.h"
                     41: #include "ospfd/ospf_nsm.h"
                     42: #include "ospfd/ospf_spf.h"
                     43: #include "ospfd/ospf_route.h"
                     44: #include "ospfd/ospf_ia.h"
                     45: #include "ospfd/ospf_ase.h"
                     46: #include "ospfd/ospf_abr.h"
                     47: #include "ospfd/ospf_dump.h"
                     48: 
                     49: static void ospf_vertex_free (void *);
                     50: /* List of allocated vertices, to simplify cleanup of SPF.
                     51:  * Not thread-safe obviously. If it ever needs to be, it'd have to be
                     52:  * dynamically allocated at begin of ospf_spf_calculate
                     53:  */
                     54: static struct list vertex_list = { .del = ospf_vertex_free };
                     55: 
                     56: /* Heap related functions, for the managment of the candidates, to
                     57:  * be used with pqueue. */
                     58: static int
                     59: cmp (void * node1 , void * node2)
                     60: {
                     61:   struct vertex * v1 = (struct vertex *) node1;
                     62:   struct vertex * v2 = (struct vertex *) node2;
                     63:   if (v1 != NULL && v2 != NULL )
                     64:     {
                     65:       /* network vertices must be chosen before router vertices of same
                     66:        * cost in order to find all shortest paths
                     67:        */
                     68:       if ( ((v1->distance - v2->distance) == 0)
                     69:           && (v1->type != v2->type))
                     70:         {
                     71:           switch (v1->type)
                     72:             {
                     73:               case OSPF_VERTEX_NETWORK:
                     74:                 return -1;
                     75:               case OSPF_VERTEX_ROUTER:
                     76:                 return 1;
                     77:             }
                     78:         }
                     79:       else
                     80:         return (v1->distance - v2->distance);
                     81:     }
                     82:   return 0;
                     83: }
                     84: 
                     85: static void
                     86: update_stat (void *node , int position)
                     87: {
                     88:   struct vertex *v = node;
                     89: 
                     90:   /* Set the status of the vertex, when its position changes. */
                     91:   *(v->stat) = position;
                     92: }
                     93: 
                     94: static struct vertex_nexthop *
                     95: vertex_nexthop_new (void)
                     96: {
                     97:   return XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop));
                     98: }
                     99: 
                    100: static void
                    101: vertex_nexthop_free (struct vertex_nexthop *nh)
                    102: {
                    103:   XFREE (MTYPE_OSPF_NEXTHOP, nh);
                    104: }
                    105: 
                    106: /* Free the canonical nexthop objects for an area, ie the nexthop objects
                    107:  * attached to the first-hop router vertices, and any intervening network
                    108:  * vertices.
                    109:  */
                    110: static void
                    111: ospf_canonical_nexthops_free (struct vertex *root)
                    112: {
                    113:   struct listnode *node, *nnode;
                    114:   struct vertex *child;
                    115:   
                    116:   for (ALL_LIST_ELEMENTS (root->children, node, nnode, child))
                    117:     {
                    118:       struct listnode *n2, *nn2;
                    119:       struct vertex_parent *vp;
                    120:       
                    121:       /* router vertices through an attached network each
                    122:        * have a distinct (canonical / not inherited) nexthop
                    123:        * which must be freed.
                    124:        *
                    125:        * A network vertex can only have router vertices as its
                    126:        * children, so only one level of recursion is possible.
                    127:        */
                    128:       if (child->type == OSPF_VERTEX_NETWORK)
                    129:         ospf_canonical_nexthops_free (child);
                    130:       
                    131:       /* Free child nexthops pointing back to this root vertex */
                    132:       for (ALL_LIST_ELEMENTS (child->parents, n2, nn2, vp))
                    133:         if (vp->parent == root && vp->nexthop)
                    134:           vertex_nexthop_free (vp->nexthop);
                    135:     }
                    136: }      
                    137: 
                    138: /* TODO: Parent list should be excised, in favour of maintaining only
                    139:  * vertex_nexthop, with refcounts.
                    140:  */
                    141: static struct vertex_parent *
                    142: vertex_parent_new (struct vertex *v, int backlink, struct vertex_nexthop *hop)
                    143: {
                    144:   struct vertex_parent *new;
                    145:   
                    146:   new = XMALLOC (MTYPE_OSPF_VERTEX_PARENT, sizeof (struct vertex_parent));
                    147:   
                    148:   if (new == NULL)
                    149:     return NULL;
                    150:   
                    151:   new->parent = v;
                    152:   new->backlink = backlink;
                    153:   new->nexthop = hop;
                    154:   return new;
                    155: }
                    156: 
                    157: static void
                    158: vertex_parent_free (void *p)
                    159: {
                    160:   XFREE (MTYPE_OSPF_VERTEX_PARENT, p);
                    161: }
                    162: 
                    163: static struct vertex *
                    164: ospf_vertex_new (struct ospf_lsa *lsa)
                    165: {
                    166:   struct vertex *new;
                    167: 
                    168:   new = XCALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex));
                    169: 
                    170:   new->flags = 0;
                    171:   new->stat = &(lsa->stat);
                    172:   new->type = lsa->data->type;
                    173:   new->id = lsa->data->id;
                    174:   new->lsa = lsa->data;
                    175:   new->children = list_new ();
                    176:   new->parents = list_new ();
                    177:   new->parents->del = vertex_parent_free;
                    178:   
                    179:   listnode_add (&vertex_list, new);
                    180:   
                    181:   if (IS_DEBUG_OSPF_EVENT)
                    182:     zlog_debug ("%s: Created %s vertex %s", __func__,
                    183:                 new->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
                    184:                 inet_ntoa (new->lsa->id));
                    185:   return new;
                    186: }
                    187: 
                    188: static void
                    189: ospf_vertex_free (void *data)
                    190: {
                    191:   struct vertex *v = data;
                    192:   
                    193:   if (IS_DEBUG_OSPF_EVENT)
                    194:     zlog_debug ("%s: Free %s vertex %s", __func__,
                    195:                 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
                    196:                 inet_ntoa (v->lsa->id));
                    197:   
                    198:   /* There should be no parents potentially holding references to this vertex
                    199:    * Children however may still be there, but presumably referenced by other
                    200:    * vertices
                    201:    */
                    202:   //assert (listcount (v->parents) == 0);
                    203:   
                    204:   if (v->children)
                    205:     list_delete (v->children);
                    206:   v->children = NULL;
                    207:   
                    208:   if (v->parents)
                    209:     list_delete (v->parents);
                    210:   v->parents = NULL;
                    211:   
                    212:   v->lsa = NULL;
                    213:   
                    214:   XFREE (MTYPE_OSPF_VERTEX, v);
                    215: }
                    216: 
                    217: static void
                    218: ospf_vertex_dump(const char *msg, struct vertex *v,
                    219:                 int print_parents, int print_children)
                    220: {
                    221:   if ( ! IS_DEBUG_OSPF_EVENT)
                    222:     return;
                    223: 
                    224:   zlog_debug("%s %s vertex %s  distance %u flags %u",
                    225:             msg,
                    226:            v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
                    227:            inet_ntoa(v->lsa->id),
                    228:            v->distance,
                    229:            (unsigned int)v->flags);
                    230: 
                    231:   if (print_parents)
                    232:     {
                    233:       struct listnode *node;
                    234:       struct vertex_parent *vp;
                    235:       
                    236:       for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
                    237:         {
                    238:          char buf1[BUFSIZ];
                    239:          
                    240:          if (vp)
                    241:            {
                    242:              zlog_debug ("parent %s backlink %d nexthop %s  interface %s",
                    243:                         inet_ntoa(vp->parent->lsa->id), vp->backlink,
                    244:                         inet_ntop(AF_INET, &vp->nexthop->router, buf1, BUFSIZ),
                    245:                         vp->nexthop->oi ? IF_NAME(vp->nexthop->oi) : "NULL");
                    246:            }
                    247:        }
                    248:     }
                    249: 
                    250:   if (print_children)
                    251:     {
                    252:       struct listnode *cnode;
                    253:       struct vertex *cv;
                    254:       
                    255:       for (ALL_LIST_ELEMENTS_RO (v->children, cnode, cv))
                    256:         ospf_vertex_dump(" child:", cv, 0, 0);
                    257:     }
                    258: }
                    259: 
                    260: 
                    261: /* Add a vertex to the list of children in each of its parents. */
                    262: static void
                    263: ospf_vertex_add_parent (struct vertex *v)
                    264: {
                    265:   struct vertex_parent *vp;
                    266:   struct listnode *node;
                    267:   
                    268:   assert (v && v->parents);
                    269:   
                    270:   for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
                    271:     {
                    272:       assert (vp->parent && vp->parent->children);
                    273:       
                    274:       /* No need to add two links from the same parent. */
                    275:       if (listnode_lookup (vp->parent->children, v) == NULL)
                    276:         listnode_add (vp->parent->children, v);
                    277:     }
                    278: }
                    279: 
                    280: static void
                    281: ospf_spf_init (struct ospf_area *area)
                    282: {
                    283:   struct vertex *v;
                    284:   
                    285:   /* Create root node. */
                    286:   v = ospf_vertex_new (area->router_lsa_self);
                    287:   
                    288:   area->spf = v;
                    289: 
                    290:   /* Reset ABR and ASBR router counts. */
                    291:   area->abr_count = 0;
                    292:   area->asbr_count = 0;
                    293: }
                    294: 
                    295: /* return index of link back to V from W, or -1 if no link found */
                    296: static int
                    297: ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v)
                    298: {
                    299:   unsigned int i, length;
                    300:   struct router_lsa *rl;
                    301:   struct network_lsa *nl;
                    302: 
                    303:   /* In case of W is Network LSA. */
                    304:   if (w->type == OSPF_NETWORK_LSA)
                    305:     {
                    306:       if (v->type == OSPF_NETWORK_LSA)
                    307:         return -1;
                    308: 
                    309:       nl = (struct network_lsa *) w;
                    310:       length = (ntohs (w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;
                    311: 
                    312:       for (i = 0; i < length; i++)
                    313:         if (IPV4_ADDR_SAME (&nl->routers[i], &v->id))
                    314:           return i;
                    315:       return -1;
                    316:     }
                    317: 
                    318:   /* In case of W is Router LSA. */
                    319:   if (w->type == OSPF_ROUTER_LSA)
                    320:     {
                    321:       rl = (struct router_lsa *) w;
                    322: 
                    323:       length = ntohs (w->length);
                    324: 
                    325:       for (i = 0;
                    326:            i < ntohs (rl->links) && length >= sizeof (struct router_lsa);
                    327:            i++, length -= 12)
                    328:         {
                    329:           switch (rl->link[i].type)
                    330:             {
                    331:             case LSA_LINK_TYPE_POINTOPOINT:
                    332:             case LSA_LINK_TYPE_VIRTUALLINK:
                    333:               /* Router LSA ID. */
                    334:               if (v->type == OSPF_ROUTER_LSA &&
                    335:                   IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
                    336:                 {
                    337:                   return i;
                    338:                 }
                    339:               break;
                    340:             case LSA_LINK_TYPE_TRANSIT:
                    341:               /* Network LSA ID. */
                    342:               if (v->type == OSPF_NETWORK_LSA &&
                    343:                   IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
                    344:                 {
                    345:                   return i;
                    346:                 }
                    347:               break;
                    348:             case LSA_LINK_TYPE_STUB:
                    349:               /* Stub can't lead anywhere, carry on */
                    350:               continue;
                    351:             default:
                    352:               break;
                    353:             }
                    354:         }
                    355:     }
                    356:   return -1;
                    357: }
                    358: 
                    359: /* Find the next link after prev_link from v to w.  If prev_link is
                    360:  * NULL, return the first link from v to w.  Ignore stub and virtual links;
                    361:  * these link types will never be returned.
                    362:  */
                    363: static struct router_lsa_link *
                    364: ospf_get_next_link (struct vertex *v, struct vertex *w,
                    365:                     struct router_lsa_link *prev_link)
                    366: {
                    367:   u_char *p;
                    368:   u_char *lim;
                    369:   u_char lsa_type =  LSA_LINK_TYPE_TRANSIT;
                    370:   struct router_lsa_link *l;
                    371: 
                    372:   if (w->type == OSPF_VERTEX_ROUTER)
                    373:     lsa_type = LSA_LINK_TYPE_POINTOPOINT;
                    374: 
                    375:   if (prev_link == NULL)
                    376:     p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
                    377:   else
                    378:     {
                    379:       p = (u_char *) prev_link;
                    380:       p += (OSPF_ROUTER_LSA_LINK_SIZE +
                    381:             (prev_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
                    382:     }
                    383: 
                    384:   lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
                    385: 
                    386:   while (p < lim)
                    387:     {
                    388:       l = (struct router_lsa_link *) p;
                    389: 
                    390:       p += (OSPF_ROUTER_LSA_LINK_SIZE + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
                    391: 
                    392:       if (l->m[0].type != lsa_type)
                    393:         continue;
                    394: 
                    395:       if (IPV4_ADDR_SAME (&l->link_id, &w->id))
                    396:         return l;
                    397:     }
                    398: 
                    399:   return NULL;
                    400: }
                    401: 
                    402: static void
                    403: ospf_spf_flush_parents (struct vertex *w)
                    404: {
                    405:   struct vertex_parent *vp;
                    406:   struct listnode *ln, *nn;
                    407:   
                    408:   /* delete the existing nexthops */
                    409:   for (ALL_LIST_ELEMENTS (w->parents, ln, nn, vp))
                    410:     {
                    411:       list_delete_node (w->parents, ln);
                    412:       vertex_parent_free (vp);
                    413:     }
                    414: }
                    415: 
                    416: /* 
                    417:  * Consider supplied next-hop for inclusion to the supplied list of
                    418:  * equal-cost next-hops, adjust list as neccessary.  
                    419:  */
                    420: static void
                    421: ospf_spf_add_parent (struct vertex *v, struct vertex *w,
                    422:                      struct vertex_nexthop *newhop,
                    423:                      unsigned int distance)
                    424: {
                    425:   struct vertex_parent *vp;
                    426:     
                    427:   /* we must have a newhop, and a distance */
                    428:   assert (v && w && newhop);
                    429:   assert (distance);
                    430:   
                    431:   /* IFF w has already been assigned a distance, then we shouldn't get here
                    432:    * unless callers have determined V(l)->W is shortest / equal-shortest
                    433:    * path (0 is a special case distance (no distance yet assigned)).
                    434:    */
                    435:   if (w->distance)
                    436:     assert (distance <= w->distance);
                    437:   else
                    438:     w->distance = distance;
                    439:   
                    440:   if (IS_DEBUG_OSPF_EVENT)
                    441:     {
                    442:       char buf[2][INET_ADDRSTRLEN];
                    443:       zlog_debug ("%s: Adding %s as parent of %s",
                    444:                 __func__,
                    445:                 inet_ntop(AF_INET, &v->lsa->id, buf[0], sizeof(buf[0])),
                    446:                 inet_ntop(AF_INET, &w->lsa->id, buf[1], sizeof(buf[1])));
                    447:     }           
                    448: 
                    449:   /* Adding parent for a new, better path: flush existing parents from W. */
                    450:   if (distance < w->distance)
                    451:     {
                    452:       if (IS_DEBUG_OSPF_EVENT)
                    453:         zlog_debug ("%s: distance %d better than %d, flushing existing parents",
                    454:                     __func__, distance, w->distance);
                    455:       ospf_spf_flush_parents (w);
                    456:       w->distance = distance;
                    457:     }
                    458:   
                    459:   /* new parent is <= existing parents, add it to parent list */  
                    460:   vp = vertex_parent_new (v, ospf_lsa_has_link (w->lsa, v->lsa), newhop);
                    461:   listnode_add (w->parents, vp);
                    462: 
                    463:   return;
                    464: }
                    465: 
                    466: /* 16.1.1.  Calculate nexthop from root through V (parent) to
                    467:  * vertex W (destination), with given distance from root->W.
                    468:  *
                    469:  * The link must be supplied if V is the root vertex. In all other cases
                    470:  * it may be NULL.
                    471:  *
                    472:  * Note that this function may fail, hence the state of the destination
                    473:  * vertex, W, should /not/ be modified in a dependent manner until
                    474:  * this function returns. This function will update the W vertex with the
                    475:  * provided distance as appropriate.
                    476:  */
                    477: static unsigned int
                    478: ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
                    479:                           struct vertex *w, struct router_lsa_link *l,
                    480:                           unsigned int distance)
                    481: {
                    482:   struct listnode *node, *nnode;
                    483:   struct vertex_nexthop *nh;
                    484:   struct vertex_parent *vp;
                    485:   struct ospf_interface *oi = NULL;
                    486:   unsigned int added = 0;
                    487: 
                    488:   if (IS_DEBUG_OSPF_EVENT)
                    489:     {
                    490:       zlog_debug ("ospf_nexthop_calculation(): Start");
                    491:       ospf_vertex_dump("V (parent):", v, 1, 1);
                    492:       ospf_vertex_dump("W (dest)  :", w, 1, 1);
                    493:       zlog_debug ("V->W distance: %d", distance);
                    494:     }
                    495: 
                    496:   if (v == area->spf)
                    497:     {      
                    498:       /* 16.1.1 para 4.  In the first case, the parent vertex (V) is the
                    499:         root (the calculating router itself).  This means that the 
                    500:         destination is either a directly connected network or directly
                    501:         connected router.  The outgoing interface in this case is simply 
                    502:          the OSPF interface connecting to the destination network/router.
                    503:       */
                    504: 
                    505:       if (w->type == OSPF_VERTEX_ROUTER)
                    506:         {
                    507:           /* l  is a link from v to w
                    508:            * l2 will be link from w to v
                    509:            */
                    510:           struct router_lsa_link *l2 = NULL;
                    511:           
                    512:           /* we *must* be supplied with the link data */
                    513:           assert (l != NULL);
                    514:           
                    515:           if (IS_DEBUG_OSPF_EVENT)
                    516:             {
                    517:               char buf1[BUFSIZ];
                    518:               char buf2[BUFSIZ];
                    519:               
                    520:               zlog_debug("ospf_nexthop_calculation(): considering link "
                    521:                         "type %d link_id %s link_data %s",
                    522:                         l->m[0].type,
                    523:                         inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
                    524:                         inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
                    525:             }
                    526: 
                    527:           if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
                    528:             {
                    529:               /* If the destination is a router which connects to
                    530:                  the calculating router via a Point-to-MultiPoint
                    531:                  network, the destination's next hop IP address(es)
                    532:                  can be determined by examining the destination's
                    533:                  router-LSA: each link pointing back to the
                    534:                  calculating router and having a Link Data field
                    535:                  belonging to the Point-to-MultiPoint network
                    536:                  provides an IP address of the next hop router.
                    537: 
                    538:                  At this point l is a link from V to W, and V is the
                    539:                  root ("us").  Find the local interface associated 
                    540:                  with l (its address is in l->link_data).  If it
                    541:                  is a point-to-multipoint interface, then look through
                    542:                  the links in the opposite direction (W to V).  If
                    543:                  any of them have an address that lands within the
                    544:                  subnet declared by the PtMP link, then that link
                    545:                  is a constituent of the PtMP link, and its address is 
                    546:                  a nexthop address for V.
                    547:               */
                    548:               oi = ospf_if_is_configured (area->ospf, &l->link_data);
                    549:               if (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
                    550:                 {
                    551:                   struct prefix_ipv4 la;
                    552: 
                    553:                   la.family = AF_INET;
                    554:                   la.prefixlen = oi->address->prefixlen;
                    555: 
                    556:                   /* V links to W on PtMP interface
                    557:                      - find the interface address on W */
                    558:                   while ((l2 = ospf_get_next_link (w, v, l2)))
                    559:                     {
                    560:                       la.prefix = l2->link_data;
                    561: 
                    562:                       if (prefix_cmp ((struct prefix *) &la,
                    563:                                       oi->address) == 0)
                    564:                         /* link_data is on our PtMP network */
                    565:                         break;
                    566:                     }
                    567:                 } /* end l is on point-to-multipoint link */
                    568:               else
                    569:                 {
                    570:                   /* l is a regular point-to-point link.
                    571:                      Look for a link from W to V.
                    572:                    */
                    573:                   while ((l2 = ospf_get_next_link (w, v, l2)))
                    574:                     {
                    575:                       oi = ospf_if_is_configured (area->ospf,
                    576:                                                   &(l2->link_data));
                    577: 
                    578:                       if (oi == NULL)
                    579:                         continue;
                    580: 
                    581:                       if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
                    582:                                            &l->link_data))
                    583:                         continue;
                    584: 
                    585:                       break;
                    586:                     }
                    587:                 }
                    588: 
                    589:               if (oi && l2)
                    590:                 {
                    591:                   /* found all necessary info to build nexthop */
                    592:                   nh = vertex_nexthop_new ();
                    593:                   nh->oi = oi;
                    594:                   nh->router = l2->link_data;
                    595:                   ospf_spf_add_parent (v, w, nh, distance);
                    596:                   return 1;
                    597:                 }
                    598:               else
                    599:                 zlog_info("ospf_nexthop_calculation(): "
                    600:                           "could not determine nexthop for link");
                    601:             } /* end point-to-point link from V to W */
                    602:           else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
                    603:             {
                    604:               struct ospf_vl_data *vl_data;
                    605:               
                    606:               /* VLink implementation limitations: 
                    607:                * a) vl_data can only reference one nexthop, so no ECMP
                    608:                *    to backbone through VLinks. Though transit-area 
                    609:                *    summaries may be considered, and those can be ECMP.
                    610:                * b) We can only use /one/ VLink, even if multiple ones
                    611:                *    exist this router through multiple transit-areas.
                    612:                */
                    613:               vl_data = ospf_vl_lookup (area->ospf, NULL, l->link_id);
                    614:               
                    615:               if (vl_data 
                    616:                   && CHECK_FLAG (vl_data->flags, OSPF_VL_FLAG_APPROVED))
                    617:                 {
                    618:                   nh = vertex_nexthop_new ();
                    619:                   nh->oi = vl_data->nexthop.oi;
                    620:                   nh->router = vl_data->nexthop.router;
                    621:                   ospf_spf_add_parent (v, w, nh, distance);
                    622:                   return 1;
                    623:                 }
                    624:               else
                    625:                   zlog_info("ospf_nexthop_calculation(): "
                    626:                             "vl_data for VL link not found");
                    627:             } /* end virtual-link from V to W */
                    628:           return 0;
                    629:         } /* end W is a Router vertex */
                    630:       else
                    631:         {
                    632:           assert(w->type == OSPF_VERTEX_NETWORK);
                    633:           oi = ospf_if_is_configured (area->ospf, &(l->link_data));
                    634:           if (oi)
                    635:             {
                    636:               nh = vertex_nexthop_new ();
                    637:               nh->oi = oi;
                    638:               nh->router.s_addr = 0;
                    639:               ospf_spf_add_parent (v, w, nh, distance);
                    640:               return 1;
                    641:             }
                    642:         }
                    643:       zlog_info("ospf_nexthop_calculation(): "
                    644:                 "Unknown attached link");
                    645:       return 0;
                    646:     } /* end V is the root */
                    647:   /* Check if W's parent is a network connected to root. */
                    648:   else if (v->type == OSPF_VERTEX_NETWORK)
                    649:     {
                    650:       /* See if any of V's parents are the root. */
                    651:       for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
                    652:         {
                    653:           if (vp->parent == area->spf) /* connects to root? */
                    654:            {
                    655:              /* 16.1.1 para 5. ...the parent vertex is a network that
                    656:               * directly connects the calculating router to the destination
                    657:               * router.  The list of next hops is then determined by
                    658:               * examining the destination's router-LSA...
                    659:               */
                    660: 
                    661:              assert(w->type == OSPF_VERTEX_ROUTER);
                    662:               while ((l = ospf_get_next_link (w, v, l)))
                    663:                 {
                    664:                  /* ...For each link in the router-LSA that points back to the
                    665:                   * parent network, the link's Link Data field provides the IP
                    666:                   * address of a next hop router.  The outgoing interface to
                    667:                   * use can then be derived from the next hop IP address (or 
                    668:                   * it can be inherited from the parent network).
                    669:                   */
                    670:                  nh = vertex_nexthop_new ();
                    671:                  nh->oi = vp->nexthop->oi;
                    672:                  nh->router = l->link_data;
                    673:                  added = 1;
                    674:                   ospf_spf_add_parent (v, w, nh, distance);
                    675:                 }
                    676:             }
                    677:         }
                    678:       /* NB: This code is non-trivial.
                    679:        * 
                    680:        * E.g. it is not enough to know that V connects to the root. It is
                    681:        * also important that the while above, looping through all links from
                    682:        * W->V found at least one link, so that we know there is
                    683:        * bi-directional connectivity between V and W.  Otherwise, if we
                    684:        * /always/ return here, but don't check that W->V exists then we
                    685:        * we will prevent SPF from finding/using higher cost paths..
                    686:        *
                    687:        * See also bug #330, and also:
                    688:        *
                    689:        * http://blogs.sun.com/paulj/entry/the_difference_a_line_makes
                    690:        */
                    691:       if (added)
                    692:         return added;
                    693:     }
                    694: 
                    695:   /* 16.1.1 para 4.  If there is at least one intervening router in the
                    696:    * current shortest path between the destination and the root, the
                    697:    * destination simply inherits the set of next hops from the
                    698:    * parent.
                    699:    */
                    700:   if (IS_DEBUG_OSPF_EVENT)
                    701:     zlog_debug ("%s: Intervening routers, adding parent(s)", __func__);
                    702: 
                    703:   for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
                    704:     {
                    705:       added = 1;
                    706:       ospf_spf_add_parent (v, w, vp->nexthop, distance);
                    707:     }
                    708:   
                    709:   return added;
                    710: }
                    711: 
                    712: /* RFC2328 Section 16.1 (2).
                    713:  * v is on the SPF tree.  Examine the links in v's LSA.  Update the list
                    714:  * of candidates with any vertices not already on the list.  If a lower-cost
                    715:  * path is found to a vertex already on the candidate list, store the new cost.
                    716:  */
                    717: static void
                    718: ospf_spf_next (struct vertex *v, struct ospf_area *area,
                    719:               struct pqueue * candidate)
                    720: {
                    721:   struct ospf_lsa *w_lsa = NULL;
                    722:   u_char *p;
                    723:   u_char *lim;
                    724:   struct router_lsa_link *l = NULL;
                    725:   struct in_addr *r;
                    726:   int type = 0;
                    727: 
                    728:   /* If this is a router-LSA, and bit V of the router-LSA (see Section
                    729:      A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE.  */
                    730:   if (v->type == OSPF_VERTEX_ROUTER)
                    731:     {
                    732:       if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa))
                    733:         area->transit = OSPF_TRANSIT_TRUE;
                    734:     }
                    735:   
                    736:   if (IS_DEBUG_OSPF_EVENT)
                    737:     zlog_debug ("%s: Next vertex of %s vertex %s",
                    738:                 __func__, 
                    739:                 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
                    740:                 inet_ntoa(v->lsa->id));
                    741:   
                    742:   p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
                    743:   lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
                    744: 
                    745:   while (p < lim)
                    746:     {
                    747:       struct vertex *w;
                    748:       unsigned int distance;
                    749:       
                    750:       /* In case of V is Router-LSA. */
                    751:       if (v->lsa->type == OSPF_ROUTER_LSA)
                    752:         {
                    753:           l = (struct router_lsa_link *) p;
                    754: 
                    755:           p += (OSPF_ROUTER_LSA_LINK_SIZE +
                    756:                 (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
                    757: 
                    758:           /* (a) If this is a link to a stub network, examine the next
                    759:              link in V's LSA.  Links to stub networks will be
                    760:              considered in the second stage of the shortest path
                    761:              calculation. */
                    762:           if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
                    763:             continue;
                    764:           
                    765:           /* Infinite distance links shouldn't be followed, except
                    766:            * for local links (a stub-routed router still wants to
                    767:            * calculate tree, so must follow its own links).
                    768:            */
                    769:           if ((v != area->spf) && l->m[0].metric >= OSPF_OUTPUT_COST_INFINITE)
                    770:             continue;
                    771: 
                    772:           /* (b) Otherwise, W is a transit vertex (router or transit
                    773:              network).  Look up the vertex W's LSA (router-LSA or
                    774:              network-LSA) in Area A's link state database. */
                    775:           switch (type)
                    776:             {
                    777:             case LSA_LINK_TYPE_POINTOPOINT:
                    778:             case LSA_LINK_TYPE_VIRTUALLINK:
                    779:               if (type == LSA_LINK_TYPE_VIRTUALLINK)
                    780:                 {
                    781:                   if (IS_DEBUG_OSPF_EVENT)
                    782:                     zlog_debug ("looking up LSA through VL: %s",
                    783:                                inet_ntoa (l->link_id));
                    784:                 }
                    785: 
                    786:               w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id,
                    787:                                        l->link_id);
                    788:               if (w_lsa)
                    789:                 {
                    790:                   if (IS_DEBUG_OSPF_EVENT)
                    791:                     zlog_debug ("found Router LSA %s", inet_ntoa (l->link_id));
                    792:                 }
                    793:               break;
                    794:             case LSA_LINK_TYPE_TRANSIT:
                    795:               if (IS_DEBUG_OSPF_EVENT)
                    796:                 zlog_debug ("Looking up Network LSA, ID: %s",
                    797:                            inet_ntoa (l->link_id));
                    798:               w_lsa = ospf_lsa_lookup_by_id (area, OSPF_NETWORK_LSA,
                    799:                                              l->link_id);
                    800:               if (w_lsa)
                    801:                 if (IS_DEBUG_OSPF_EVENT)
                    802:                   zlog_debug ("found the LSA");
                    803:               break;
                    804:             default:
                    805:               zlog_warn ("Invalid LSA link type %d", type);
                    806:               continue;
                    807:             }
                    808:         }
                    809:       else
                    810:         {
                    811:           /* In case of V is Network-LSA. */
                    812:           r = (struct in_addr *) p;
                    813:           p += sizeof (struct in_addr);
                    814: 
                    815:           /* Lookup the vertex W's LSA. */
                    816:           w_lsa = ospf_lsa_lookup_by_id (area, OSPF_ROUTER_LSA, *r);
                    817:           if (w_lsa)
                    818:             {
                    819:               if (IS_DEBUG_OSPF_EVENT)
                    820:                 zlog_debug ("found Router LSA %s", inet_ntoa (w_lsa->data->id));
                    821:             }
                    822:         }
                    823: 
                    824:       /* (b cont.) If the LSA does not exist, or its LS age is equal
                    825:          to MaxAge, or it does not have a link back to vertex V,
                    826:          examine the next link in V's LSA.[23] */
                    827:       if (w_lsa == NULL)
                    828:         {
                    829:           if (IS_DEBUG_OSPF_EVENT)
                    830:             zlog_debug ("No LSA found");
                    831:           continue;
                    832:         }
                    833: 
                    834:       if (IS_LSA_MAXAGE (w_lsa))
                    835:         {
                    836:           if (IS_DEBUG_OSPF_EVENT)
                    837:             zlog_debug ("LSA is MaxAge");
                    838:           continue;
                    839:         }
                    840: 
                    841:       if (ospf_lsa_has_link (w_lsa->data, v->lsa) < 0 )
                    842:         {
                    843:           if (IS_DEBUG_OSPF_EVENT)
                    844:             zlog_debug ("The LSA doesn't have a link back");
                    845:           continue;
                    846:         }
                    847: 
                    848:       /* (c) If vertex W is already on the shortest-path tree, examine
                    849:          the next link in the LSA. */
                    850:       if (w_lsa->stat == LSA_SPF_IN_SPFTREE)
                    851:        {
                    852:          if (IS_DEBUG_OSPF_EVENT)
                    853:            zlog_debug ("The LSA is already in SPF");
                    854:          continue;
                    855:        }
                    856: 
                    857:       /* (d) Calculate the link state cost D of the resulting path
                    858:          from the root to vertex W.  D is equal to the sum of the link
                    859:          state cost of the (already calculated) shortest path to
                    860:          vertex V and the advertised cost of the link between vertices
                    861:          V and W.  If D is: */
                    862: 
                    863:       /* calculate link cost D. */
                    864:       if (v->lsa->type == OSPF_ROUTER_LSA)
                    865:        distance = v->distance + ntohs (l->m[0].metric);
                    866:       else /* v is not a Router-LSA */
                    867:        distance = v->distance;
                    868: 
                    869:       /* Is there already vertex W in candidate list? */
                    870:       if (w_lsa->stat == LSA_SPF_NOT_EXPLORED)
                    871:        {
                    872:           /* prepare vertex W. */
                    873:           w = ospf_vertex_new (w_lsa);
                    874: 
                    875:           /* Calculate nexthop to W. */
                    876:           if (ospf_nexthop_calculation (area, v, w, l, distance))
                    877:             pqueue_enqueue (w, candidate);
                    878:           else if (IS_DEBUG_OSPF_EVENT)
                    879:             zlog_debug ("Nexthop Calc failed");
                    880:        }
                    881:       else if (w_lsa->stat >= 0)
                    882:        {
                    883:          /* Get the vertex from candidates. */
                    884:          w = candidate->array[w_lsa->stat];
                    885: 
                    886:          /* if D is greater than. */  
                    887:          if (w->distance < distance)
                    888:             {
                    889:               continue;
                    890:             }
                    891:           /* equal to. */
                    892:          else if (w->distance == distance)
                    893:             {
                    894:              /* Found an equal-cost path to W.  
                    895:                * Calculate nexthop of to W from V. */
                    896:               ospf_nexthop_calculation (area, v, w, l, distance);
                    897:             }
                    898:            /* less than. */
                    899:          else
                    900:             {
                    901:               /* Found a lower-cost path to W.
                    902:                * nexthop_calculation is conditional, if it finds
                    903:                * valid nexthop it will call spf_add_parents, which
                    904:                * will flush the old parents
                    905:                */
                    906:               if (ospf_nexthop_calculation (area, v, w, l, distance))
                    907:                 /* Decrease the key of the node in the heap.
                    908:                  * trickle-sort it up towards root, just in case this
                    909:                  * node should now be the new root due the cost change. 
                    910:                  * (next pqueu_{de,en}queue will fully re-heap the queue).
                    911:                  */
                    912:                 trickle_up (w_lsa->stat, candidate);
                    913:             }
                    914:         } /* end W is already on the candidate list */
                    915:     } /* end loop over the links in V's LSA */
                    916: }
                    917: 
                    918: static void
                    919: ospf_spf_dump (struct vertex *v, int i)
                    920: {
                    921:   struct listnode *cnode;
                    922:   struct listnode *nnode;
                    923:   struct vertex_parent *parent;
                    924: 
                    925:   if (v->type == OSPF_VERTEX_ROUTER)
                    926:     {
                    927:       if (IS_DEBUG_OSPF_EVENT)
                    928:         zlog_debug ("SPF Result: %d [R] %s", i, inet_ntoa (v->lsa->id));
                    929:     }
                    930:   else
                    931:     {
                    932:       struct network_lsa *lsa = (struct network_lsa *) v->lsa;
                    933:       if (IS_DEBUG_OSPF_EVENT)
                    934:         zlog_debug ("SPF Result: %d [N] %s/%d", i, inet_ntoa (v->lsa->id),
                    935:                    ip_masklen (lsa->mask));
                    936:     }
                    937: 
                    938:   if (IS_DEBUG_OSPF_EVENT)
                    939:     for (ALL_LIST_ELEMENTS_RO (v->parents, nnode, parent))
                    940:       {
                    941:         zlog_debug (" nexthop %p %s %s", 
                    942:                     parent->nexthop,
                    943:                     inet_ntoa (parent->nexthop->router),
                    944:                     parent->nexthop->oi ? IF_NAME(parent->nexthop->oi)
                    945:                                         : "NULL");
                    946:       }
                    947: 
                    948:   i++;
                    949: 
                    950:   for (ALL_LIST_ELEMENTS_RO (v->children, cnode, v))
                    951:     ospf_spf_dump (v, i);
                    952: }
                    953: 
                    954: /* Second stage of SPF calculation. */
                    955: static void
                    956: ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v,
                    957:                         struct route_table *rt,
                    958:                         int parent_is_root)
                    959: {
                    960:   struct listnode *cnode, *cnnode;
                    961:   struct vertex *child;
                    962: 
                    963:   if (IS_DEBUG_OSPF_EVENT)
                    964:     zlog_debug ("ospf_process_stub():processing stubs for area %s",
                    965:                inet_ntoa (area->area_id));
                    966:   if (v->type == OSPF_VERTEX_ROUTER)
                    967:     {
                    968:       u_char *p;
                    969:       u_char *lim;
                    970:       struct router_lsa_link *l;
                    971:       struct router_lsa *rlsa;
                    972: 
                    973:       if (IS_DEBUG_OSPF_EVENT)
                    974:         zlog_debug ("ospf_process_stubs():processing router LSA, id: %s",
                    975:                    inet_ntoa (v->lsa->id));
                    976:       rlsa = (struct router_lsa *) v->lsa;
                    977: 
                    978: 
                    979:       if (IS_DEBUG_OSPF_EVENT)
                    980:         zlog_debug ("ospf_process_stubs(): we have %d links to process",
                    981:                    ntohs (rlsa->links));
                    982:       p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
                    983:       lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
                    984: 
                    985:       while (p < lim)
                    986:         {
                    987:           l = (struct router_lsa_link *) p;
                    988: 
                    989:           p += (OSPF_ROUTER_LSA_LINK_SIZE +
                    990:                 (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
                    991: 
                    992:           if (l->m[0].type == LSA_LINK_TYPE_STUB)
                    993:             ospf_intra_add_stub (rt, l, v, area, parent_is_root);
                    994:         }
                    995:     }
                    996: 
                    997:   ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1, 1);
                    998: 
                    999:   for (ALL_LIST_ELEMENTS (v->children, cnode, cnnode, child))
                   1000:     {
                   1001:       if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED))
                   1002:         continue;
                   1003:       
                   1004:       /* the first level of routers connected to the root
                   1005:        * should have 'parent_is_root' set, including those 
                   1006:        * connected via a network vertex.
                   1007:        */
                   1008:       if (area->spf == v)
                   1009:         parent_is_root = 1;
                   1010:       else if (v->type == OSPF_VERTEX_ROUTER)
                   1011:         parent_is_root = 0;
                   1012:         
                   1013:       ospf_spf_process_stubs (area, child, rt, parent_is_root);
                   1014: 
                   1015:       SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED);
                   1016:     }
                   1017: }
                   1018: 
                   1019: void
                   1020: ospf_rtrs_free (struct route_table *rtrs)
                   1021: {
                   1022:   struct route_node *rn;
                   1023:   struct list *or_list;
                   1024:   struct ospf_route *or;
                   1025:   struct listnode *node, *nnode;
                   1026: 
                   1027:   if (IS_DEBUG_OSPF_EVENT)
                   1028:     zlog_debug ("Route: Router Routing Table free");
                   1029: 
                   1030:   for (rn = route_top (rtrs); rn; rn = route_next (rn))
                   1031:     if ((or_list = rn->info) != NULL)
                   1032:       {
                   1033:         for (ALL_LIST_ELEMENTS (or_list, node, nnode, or))
                   1034:           ospf_route_free (or);
                   1035: 
                   1036:         list_delete (or_list);
                   1037: 
                   1038:         /* Unlock the node. */
                   1039:         rn->info = NULL;
                   1040:         route_unlock_node (rn);
                   1041:       }
                   1042:   route_table_finish (rtrs);
                   1043: }
                   1044: 
                   1045: static void
                   1046: ospf_rtrs_print (struct route_table *rtrs)
                   1047: {
                   1048:   struct route_node *rn;
                   1049:   struct list *or_list;
                   1050:   struct listnode *ln;
                   1051:   struct listnode *pnode;
                   1052:   struct ospf_route *or;
                   1053:   struct ospf_path *path;
                   1054:   char buf1[BUFSIZ];
                   1055:   char buf2[BUFSIZ];
                   1056: 
                   1057:   if (IS_DEBUG_OSPF_EVENT)
                   1058:     zlog_debug ("ospf_rtrs_print() start");
                   1059: 
                   1060:   for (rn = route_top (rtrs); rn; rn = route_next (rn))
                   1061:     if ((or_list = rn->info) != NULL)
                   1062:       for (ALL_LIST_ELEMENTS_RO (or_list, ln, or))
                   1063:         {
                   1064:           switch (or->path_type)
                   1065:             {
                   1066:             case OSPF_PATH_INTRA_AREA:
                   1067:               if (IS_DEBUG_OSPF_EVENT)
                   1068:                 zlog_debug ("%s   [%d] area: %s",
                   1069:                            inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
                   1070:                            or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
                   1071:                                                 buf2, BUFSIZ));
                   1072:               break;
                   1073:             case OSPF_PATH_INTER_AREA:
                   1074:               if (IS_DEBUG_OSPF_EVENT)
                   1075:                 zlog_debug ("%s IA [%d] area: %s",
                   1076:                            inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
                   1077:                            or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
                   1078:                                                 buf2, BUFSIZ));
                   1079:               break;
                   1080:             default:
                   1081:               break;
                   1082:             }
                   1083: 
                   1084:           for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path))
                   1085:             {
                   1086:               if (path->nexthop.s_addr == 0)
                   1087:                 {
                   1088:                   if (IS_DEBUG_OSPF_EVENT)
                   1089:                     zlog_debug ("   directly attached to %s\r\n",
                   1090:                                ifindex2ifname (path->ifindex));
                   1091:                 }
                   1092:               else
                   1093:                 {
                   1094:                   if (IS_DEBUG_OSPF_EVENT)
                   1095:                     zlog_debug ("   via %s, %s\r\n",
                   1096:                                inet_ntoa (path->nexthop),
                   1097:                                ifindex2ifname (path->ifindex));
                   1098:                 }
                   1099:             }
                   1100:         }
                   1101: 
                   1102:   zlog_debug ("ospf_rtrs_print() end");
                   1103: }
                   1104: 
                   1105: /* Calculating the shortest-path tree for an area. */
                   1106: static void
                   1107: ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table,
                   1108:                     struct route_table *new_rtrs)
                   1109: {
                   1110:   struct pqueue *candidate;
                   1111:   struct vertex *v;
                   1112:   
                   1113:   if (IS_DEBUG_OSPF_EVENT)
                   1114:     {
                   1115:       zlog_debug ("ospf_spf_calculate: Start");
                   1116:       zlog_debug ("ospf_spf_calculate: running Dijkstra for area %s",
                   1117:                  inet_ntoa (area->area_id));
                   1118:     }
                   1119: 
                   1120:   /* Check router-lsa-self.  If self-router-lsa is not yet allocated,
                   1121:      return this area's calculation. */
                   1122:   if (!area->router_lsa_self)
                   1123:     {
                   1124:       if (IS_DEBUG_OSPF_EVENT)
                   1125:         zlog_debug ("ospf_spf_calculate: "
                   1126:                    "Skip area %s's calculation due to empty router_lsa_self",
                   1127:                    inet_ntoa (area->area_id));
                   1128:       return;
                   1129:     }
                   1130: 
                   1131:   /* RFC2328 16.1. (1). */
                   1132:   /* Initialize the algorithm's data structures. */
                   1133:   
                   1134:   /* This function scans all the LSA database and set the stat field to
                   1135:    * LSA_SPF_NOT_EXPLORED. */
                   1136:   ospf_lsdb_clean_stat (area->lsdb);
                   1137:   /* Create a new heap for the candidates. */ 
                   1138:   candidate = pqueue_create();
                   1139:   candidate->cmp = cmp;
                   1140:   candidate->update = update_stat;
                   1141: 
                   1142:   /* Initialize the shortest-path tree to only the root (which is the
                   1143:      router doing the calculation). */
                   1144:   ospf_spf_init (area);
                   1145:   v = area->spf;
                   1146:   /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the
                   1147:    * spanning tree. */
                   1148:   *(v->stat) = LSA_SPF_IN_SPFTREE;
                   1149: 
                   1150:   /* Set Area A's TransitCapability to FALSE. */
                   1151:   area->transit = OSPF_TRANSIT_FALSE;
                   1152:   area->shortcut_capability = 1;
                   1153:   
                   1154:   for (;;)
                   1155:     {
                   1156:       /* RFC2328 16.1. (2). */
                   1157:       ospf_spf_next (v, area, candidate);
                   1158: 
                   1159:       /* RFC2328 16.1. (3). */
                   1160:       /* If at this step the candidate list is empty, the shortest-
                   1161:          path tree (of transit vertices) has been completely built and
                   1162:          this stage of the procedure terminates. */
                   1163:       if (candidate->size == 0)
                   1164:         break;
                   1165: 
                   1166:       /* Otherwise, choose the vertex belonging to the candidate list
                   1167:          that is closest to the root, and add it to the shortest-path
                   1168:          tree (removing it from the candidate list in the
                   1169:          process). */
                   1170:       /* Extract from the candidates the node with the lower key. */
                   1171:       v = (struct vertex *) pqueue_dequeue (candidate);
                   1172:       /* Update stat field in vertex. */
                   1173:       *(v->stat) = LSA_SPF_IN_SPFTREE;
                   1174: 
                   1175:       ospf_vertex_add_parent (v);
                   1176: 
                   1177:       /* RFC2328 16.1. (4). */
                   1178:       if (v->type == OSPF_VERTEX_ROUTER)
                   1179:         ospf_intra_add_router (new_rtrs, v, area);
                   1180:       else
                   1181:         ospf_intra_add_transit (new_table, v, area);
                   1182: 
                   1183:       /* RFC2328 16.1. (5). */
                   1184:       /* Iterate the algorithm by returning to Step 2. */
                   1185: 
                   1186:     } /* end loop until no more candidate vertices */
                   1187: 
                   1188:   if (IS_DEBUG_OSPF_EVENT)
                   1189:     {
                   1190:       ospf_spf_dump (area->spf, 0);
                   1191:       ospf_route_table_dump (new_table);
                   1192:     }
                   1193: 
                   1194:   /* Second stage of SPF calculation procedure's  */
                   1195:   ospf_spf_process_stubs (area, area->spf, new_table, 0);
                   1196: 
                   1197:   /* Free candidate queue. */
                   1198:   pqueue_delete (candidate);
                   1199:   
                   1200:   ospf_vertex_dump (__func__, area->spf, 0, 1);
                   1201:   /* Free nexthop information, canonical versions of which are attached
                   1202:    * the first level of router vertices attached to the root vertex, see
                   1203:    * ospf_nexthop_calculation.
                   1204:    */
                   1205:   ospf_canonical_nexthops_free (area->spf);
                   1206:   
                   1207:   /* Free SPF vertices, but not the list. List has ospf_vertex_free
                   1208:    * as deconstructor.
                   1209:    */
                   1210:   list_delete_all_node (&vertex_list);
                   1211:   
                   1212:   /* Increment SPF Calculation Counter. */
                   1213:   area->spf_calculation++;
                   1214: 
                   1215:   quagga_gettime (QUAGGA_CLK_MONOTONIC, &area->ospf->ts_spf);
                   1216: 
                   1217:   if (IS_DEBUG_OSPF_EVENT)
                   1218:     zlog_debug ("ospf_spf_calculate: Stop. %ld vertices",
                   1219:                 mtype_stats_alloc(MTYPE_OSPF_VERTEX));
                   1220: }
                   1221: 
                   1222: /* Timer for SPF calculation. */
                   1223: static int
                   1224: ospf_spf_calculate_timer (struct thread *thread)
                   1225: {
                   1226:   struct ospf *ospf = THREAD_ARG (thread);
                   1227:   struct route_table *new_table, *new_rtrs;
                   1228:   struct ospf_area *area;
                   1229:   struct listnode *node, *nnode;
                   1230: 
                   1231:   if (IS_DEBUG_OSPF_EVENT)
                   1232:     zlog_debug ("SPF: Timer (SPF calculation expire)");
                   1233: 
                   1234:   ospf->t_spf_calc = NULL;
                   1235: 
                   1236:   /* Allocate new table tree. */
                   1237:   new_table = route_table_init ();
                   1238:   new_rtrs = route_table_init ();
                   1239: 
                   1240:   ospf_vl_unapprove (ospf);
                   1241: 
                   1242:   /* Calculate SPF for each area. */
                   1243:   for (ALL_LIST_ELEMENTS (ospf->areas, node, nnode, area))
                   1244:     {
                   1245:       /* Do backbone last, so as to first discover intra-area paths
                   1246:        * for any back-bone virtual-links
                   1247:        */
                   1248:       if (ospf->backbone && ospf->backbone == area)
                   1249:         continue;
                   1250:       
                   1251:       ospf_spf_calculate (area, new_table, new_rtrs);
                   1252:     }
                   1253:   
                   1254:   /* SPF for backbone, if required */
                   1255:   if (ospf->backbone)
                   1256:     ospf_spf_calculate (ospf->backbone, new_table, new_rtrs);
                   1257:   
                   1258:   ospf_vl_shut_unapproved (ospf);
                   1259: 
                   1260:   ospf_ia_routing (ospf, new_table, new_rtrs);
                   1261: 
                   1262:   ospf_prune_unreachable_networks (new_table);
                   1263:   ospf_prune_unreachable_routers (new_rtrs);
                   1264: 
                   1265:   /* AS-external-LSA calculation should not be performed here. */
                   1266: 
                   1267:   /* If new Router Route is installed,
                   1268:      then schedule re-calculate External routes. */
                   1269:   if (1)
                   1270:     ospf_ase_calculate_schedule (ospf);
                   1271: 
                   1272:   ospf_ase_calculate_timer_add (ospf);
                   1273: 
                   1274:   /* Update routing table. */
                   1275:   ospf_route_install (ospf, new_table);
                   1276: 
                   1277:   /* Update ABR/ASBR routing table */
                   1278:   if (ospf->old_rtrs)
                   1279:     {
                   1280:       /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
                   1281:       /* ospf_route_delete (ospf->old_rtrs); */
                   1282:       ospf_rtrs_free (ospf->old_rtrs);
                   1283:     }
                   1284: 
                   1285:   ospf->old_rtrs = ospf->new_rtrs;
                   1286:   ospf->new_rtrs = new_rtrs;
                   1287: 
                   1288:   if (IS_OSPF_ABR (ospf))
                   1289:     ospf_abr_task (ospf);
                   1290: 
                   1291:   if (IS_DEBUG_OSPF_EVENT)
                   1292:     zlog_debug ("SPF: calculation complete");
                   1293: 
                   1294:   return 0;
                   1295: }
                   1296: 
                   1297: /* Add schedule for SPF calculation.  To avoid frequenst SPF calc, we
                   1298:    set timer for SPF calc. */
                   1299: void
                   1300: ospf_spf_calculate_schedule (struct ospf *ospf)
                   1301: {
                   1302:   unsigned long delay, elapsed, ht;
                   1303:   struct timeval result;
                   1304: 
                   1305:   if (IS_DEBUG_OSPF_EVENT)
                   1306:     zlog_debug ("SPF: calculation timer scheduled");
                   1307: 
                   1308:   /* OSPF instance does not exist. */
                   1309:   if (ospf == NULL)
                   1310:     return;
                   1311:   
                   1312:   /* SPF calculation timer is already scheduled. */
                   1313:   if (ospf->t_spf_calc)
                   1314:     {
                   1315:       if (IS_DEBUG_OSPF_EVENT)
                   1316:         zlog_debug ("SPF: calculation timer is already scheduled: %p",
                   1317:                    ospf->t_spf_calc);
                   1318:       return;
                   1319:     }
                   1320:   
                   1321:   /* XXX Monotic timers: we only care about relative time here. */
                   1322:   result = tv_sub (recent_relative_time (), ospf->ts_spf);
                   1323:   
                   1324:   elapsed = (result.tv_sec * 1000) + (result.tv_usec / 1000);
                   1325:   ht = ospf->spf_holdtime * ospf->spf_hold_multiplier;
                   1326:   
                   1327:   if (ht > ospf->spf_max_holdtime)
                   1328:     ht = ospf->spf_max_holdtime;
                   1329:   
                   1330:   /* Get SPF calculation delay time. */
                   1331:   if (elapsed < ht)
                   1332:     {
                   1333:       /* Got an event within the hold time of last SPF. We need to
                   1334:        * increase the hold_multiplier, if it's not already at/past
                   1335:        * maximum value, and wasn't already increased..
                   1336:        */
                   1337:       if (ht < ospf->spf_max_holdtime)
                   1338:         ospf->spf_hold_multiplier++;
                   1339:       
                   1340:       /* always honour the SPF initial delay */
                   1341:       if ( (ht - elapsed) < ospf->spf_delay)
                   1342:         delay = ospf->spf_delay;
                   1343:       else
                   1344:         delay = ht - elapsed;
                   1345:     }
                   1346:   else
                   1347:     {
                   1348:       /* Event is past required hold-time of last SPF */
                   1349:       delay = ospf->spf_delay;
                   1350:       ospf->spf_hold_multiplier = 1;
                   1351:     }
                   1352:   
                   1353:   if (IS_DEBUG_OSPF_EVENT)
                   1354:     zlog_debug ("SPF: calculation timer delay = %ld", delay);
                   1355: 
                   1356:   ospf->t_spf_calc =
                   1357:     thread_add_timer_msec (master, ospf_spf_calculate_timer, ospf, delay);
                   1358: }

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