diff options
| -rw-r--r-- | ospfd/ChangeLog | 46 | ||||
| -rw-r--r-- | ospfd/ospf_interface.c | 60 | ||||
| -rw-r--r-- | ospfd/ospf_interface.h | 5 | ||||
| -rw-r--r-- | ospfd/ospf_route.c | 5 | ||||
| -rw-r--r-- | ospfd/ospf_spf.c | 165 | ||||
| -rw-r--r-- | ospfd/ospf_spf.h | 5 | ||||
| -rw-r--r-- | ospfd/ospf_vty.c | 29 |
7 files changed, 233 insertions, 82 deletions
diff --git a/ospfd/ChangeLog b/ospfd/ChangeLog index ac596705..99599f54 100644 --- a/ospfd/ChangeLog +++ b/ospfd/ChangeLog @@ -1,3 +1,49 @@ +2006-04-24 Paul Jakma <paul.jakma@sun.com> + + * (general) More Virtual-link fixes, again with much help in + testing / debug from Juergen Kammer. Primarily in SPF. + * ospf_spf.h: Add guard. ospf_interface.h will include this + header. + * ospf_interface.h: Modify ospf_vl_lookup definition to take + struct ospf as argument, so as to allow for NULL area + argument. + (struct ospf_vl_data) Remove out_oi, instead add a struct + vertex_nexthop, to use as initial nexthop for backbone paths + through a vlink. + * ospf_interface.c: (ospf_vl_lookup) Modified to allow + NULL area to be passed to indicate "any" (first) area. + Add extra debug. + (ospf_vl_set_params) vl_oi -> nexthop. Add extra debug. + (ospf_vl_up_check) Fix debug, inet_ntoa returns a static + buffer.. + * ospf_route.c: (ospf_intra_add_router) Vlinks dont go through + backbone, don't bother checking. + * ospf_spf.c: (static struct list vertex_list) Record vertices + that will need to be freed. + (cmp) Order network before router vertices, as required, + wasn't implemented. + (vertex_nexthop_free) Mild additional robustness check. + (vertex_parent_free) Take void argument, as this function + is passed as list deconstructor for vertex parent list. + (ospf_vertex_new) More debug. Set deconstructor for parent + list. Track allocated vertices on the vertex_list. + (ospf_vertex_free) Get rid of the tricky recursive cleanup of + vertices. Now frees only the given vertex. + (ospf_vertex_add_parent) Fix assert. + (ospf_nexthop_calculation) Fix calculation of nexthop for + VLink vertices, lookup the vl_data and use its previously + recorded nexthop information. + (ospf_spf_calculate) Vertices are freed simply by deleting + vertex_list nodes and letting ospf_vertex_free as deconstructor + work per-node. + (ospf_spf_calculate_timer) Trivial optimisation, leave + backbone SPF calculation till last to reduce SPF churn on + VLink updates. + * ospf_vty.c: (ospf_find_vl_data) update call to ospf_vl_lookup + (no_ospf_area_vlink_cmd) ditto. + (show_ip_ospf_interface_sub) For Vlinks, the peer address is + more interesting than the output interface. + 2006-04-03 Paul Jakma <paul.jakma@sun.com> * (general) Fix issues with handling of Vlinks and entries diff --git a/ospfd/ospf_interface.c b/ospfd/ospf_interface.c index 52adc420..1264cac6 100644 --- a/ospfd/ospf_interface.c +++ b/ospfd/ospf_interface.c @@ -931,16 +931,36 @@ ospf_vl_if_delete (struct ospf_vl_data *vl_data) vlink_count--; } +/* Look up vl_data for given peer, optionally qualified to be in the + * specified area. NULL area returns first found.. + */ struct ospf_vl_data * -ospf_vl_lookup (struct ospf_area *area, struct in_addr vl_peer) +ospf_vl_lookup (struct ospf *ospf, struct ospf_area *area, + struct in_addr vl_peer) { struct ospf_vl_data *vl_data; struct listnode *node; - - for (ALL_LIST_ELEMENTS_RO (area->ospf->vlinks, node, vl_data)) - if (vl_data->vl_peer.s_addr == vl_peer.s_addr && - IPV4_ADDR_SAME (&vl_data->vl_area_id, &area->area_id)) - return vl_data; + + if (IS_DEBUG_OSPF_EVENT) + { + zlog_debug ("%s: Looking for %s", __func__, inet_ntoa (vl_peer)); + if (area) + zlog_debug ("%s: in area %s", __func__, inet_ntoa (area->area_id)); + } + + for (ALL_LIST_ELEMENTS_RO (ospf->vlinks, node, vl_data)) + { + if (IS_DEBUG_OSPF_EVENT) + zlog_debug ("%s: VL %s, peer %s", __func__, + vl_data->vl_oi->ifp->name, + inet_ntoa (vl_data->vl_peer)); + + if (area && !IPV4_ADDR_SAME (&vl_data->vl_area_id, &area->area_id)) + continue; + + if (IPV4_ADDR_SAME (&vl_data->vl_peer, &vl_peer)) + return vl_data; + } return NULL; } @@ -1005,14 +1025,15 @@ ospf_vl_set_params (struct ospf_vl_data *vl_data, struct vertex *v) for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp)) { - vl_data->out_oi = vp->nexthop->oi; + vl_data->nexthop.oi = vp->nexthop->oi; + vl_data->nexthop.router = vp->nexthop->router; if (!IPV4_ADDR_SAME(&voi->address->u.prefix4, - &vl_data->out_oi->address->u.prefix4)) + &vl_data->nexthop.oi->address->u.prefix4)) changed = 1; - voi->address->u.prefix4 = vl_data->out_oi->address->u.prefix4; - voi->address->prefixlen = vl_data->out_oi->address->prefixlen; + voi->address->u.prefix4 = vl_data->nexthop.oi->address->u.prefix4; + voi->address->prefixlen = vl_data->nexthop.oi->address->prefixlen; break; /* We take the first interface. */ } @@ -1050,19 +1071,16 @@ ospf_vl_set_params (struct ospf_vl_data *vl_data, struct vertex *v) &rl->link[i].link_data)) changed = 1; vl_data->peer_addr = rl->link[i].link_data; - if (IS_DEBUG_OSPF_EVENT) - zlog_debug ("ospf_vl_set_params: %s peer address is %s\n", - vl_data->vl_oi->ifp->name, - inet_ntoa(vl_data->peer_addr)); - return changed; } } } if (IS_DEBUG_OSPF_EVENT) - zlog_debug ("ospf_vl_set_params: %s peer address is %s\n", + zlog_debug ("%s: %s peer address: %s, cost: %d,%schanged", __func__, vl_data->vl_oi->ifp->name, - inet_ntoa(vl_data->peer_addr)); + inet_ntoa(vl_data->peer_addr), + voi->output_cost, + (changed ? " " : " un")); return changed; } @@ -1088,10 +1106,10 @@ ospf_vl_up_check (struct ospf_area *area, struct in_addr rid, { if (IS_DEBUG_OSPF_EVENT) { - zlog_debug ("ospf_vl_up_check(): considering VL, name: %s", - vl_data->vl_oi->ifp->name); - zlog_debug ("ospf_vl_up_check(): VL area: %s, peer ID: %s", - inet_ntoa (vl_data->vl_area_id), + zlog_debug ("%s: considering VL, %s in area %s", __func__, + vl_data->vl_oi->ifp->name, + inet_ntoa (vl_data->vl_area_id)); + zlog_debug ("%s: peer ID: %s", __func__, inet_ntoa (vl_data->vl_peer)); } diff --git a/ospfd/ospf_interface.h b/ospfd/ospf_interface.h index 28d95d7e..3c759405 100644 --- a/ospfd/ospf_interface.h +++ b/ospfd/ospf_interface.h @@ -24,6 +24,7 @@ #define _ZEBRA_OSPF_INTERFACE_H #include "ospfd/ospf_packet.h" +#include "ospfd/ospf_spf.h" #define IF_OSPF_IF_INFO(I) ((struct ospf_if_info *)((I)->info)) #define IF_DEF_PARAMS(I) (IF_OSPF_IF_INFO (I)->def_params) @@ -82,7 +83,7 @@ struct ospf_vl_data struct in_addr vl_area_id; /* Transit area for this VL. */ int format; /* area ID format */ struct ospf_interface *vl_oi; /* Interface data structure for the VL. */ - struct ospf_interface *out_oi; /* The interface to go out. */ + struct vertex_nexthop nexthop; /* Nexthop router and oi to use */ struct in_addr peer_addr; /* Address used to reach the peer. */ u_char flags; }; @@ -250,7 +251,7 @@ extern struct ospf_interface *ospf_vl_new (struct ospf *, struct ospf_vl_data *); extern struct ospf_vl_data *ospf_vl_data_new (struct ospf_area *, struct in_addr); -extern struct ospf_vl_data *ospf_vl_lookup (struct ospf_area *, +extern struct ospf_vl_data *ospf_vl_lookup (struct ospf *, struct ospf_area *, struct in_addr); extern void ospf_vl_data_free (struct ospf_vl_data *); extern void ospf_vl_add (struct ospf *, struct ospf_vl_data *); diff --git a/ospfd/ospf_route.c b/ospfd/ospf_route.c index 5eedbd82..646b625f 100644 --- a/ospfd/ospf_route.c +++ b/ospfd/ospf_route.c @@ -343,8 +343,9 @@ ospf_intra_add_router (struct route_table *rt, struct vertex *v, if (IS_DEBUG_OSPF_EVENT) zlog_debug ("ospf_intra_add_router: LS ID: %s", inet_ntoa (lsa->header.id)); - - ospf_vl_up_check (area, lsa->header.id, v); + + if (!OSPF_IS_AREA_BACKBONE(area)) + ospf_vl_up_check (area, lsa->header.id, v); if (!CHECK_FLAG (lsa->flags, ROUTER_LSA_SHORTCUT)) area->shortcut_capability = 0; diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index dbd06361..7228d2d4 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -46,6 +46,13 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA #include "ospfd/ospf_abr.h" #include "ospfd/ospf_dump.h" +static void ospf_vertex_free (void *); +/* List of allocated vertices, to simplify cleanup of SPF. + * Not thread-safe obviously. If it ever needs to be, it'd have to be + * dynamically allocated at begin of ospf_spf_calculate + */ +static struct list vertex_list = { .del = ospf_vertex_free }; + /* Heap related functions, for the managment of the candidates, to * be used with pqueue. */ static int @@ -54,9 +61,25 @@ cmp (void * node1 , void * node2) struct vertex * v1 = (struct vertex *) node1; struct vertex * v2 = (struct vertex *) node2; if (v1 != NULL && v2 != NULL ) - return (v1->distance - v2->distance); - else - return 0; + { + /* network vertices must be chosen before router vertices of same + * cost in order to find all shortest paths + */ + if ( ((v1->distance - v2->distance) == 0) + && (v1->type != v2->type)) + { + switch (v1->type) + { + case OSPF_VERTEX_NETWORK: + return -1; + case OSPF_VERTEX_ROUTER: + return 1; + } + } + else + return (v1->distance - v2->distance); + } + return 0; } static void @@ -81,7 +104,8 @@ vertex_nexthop_free (struct vertex_nexthop *nh) } /* Free the canonical nexthop objects for an area, ie the nexthop objects - * attached to the first-hop router vertices. + * attached to the first-hop router vertices, and any intervening network + * vertices. */ static void ospf_canonical_nexthops_free (struct vertex *root) @@ -106,11 +130,14 @@ ospf_canonical_nexthops_free (struct vertex *root) /* Free child nexthops pointing back to this root vertex */ for (ALL_LIST_ELEMENTS (child->parents, n2, nn2, vp)) - if (vp->parent == root) + if (vp->parent == root && vp->nexthop) vertex_nexthop_free (vp->nexthop); } } +/* TODO: Parent list should be excised, in favour of maintaining only + * vertex_nexthop, with refcounts. + */ static struct vertex_parent * vertex_parent_new (struct vertex *v, int backlink, struct vertex_nexthop *hop) { @@ -128,7 +155,7 @@ vertex_parent_new (struct vertex *v, int backlink, struct vertex_nexthop *hop) } static void -vertex_parent_free (struct vertex_parent *p) +vertex_parent_free (void *p) { XFREE (MTYPE_OSPF_VERTEX_PARENT, p); } @@ -148,48 +175,39 @@ ospf_vertex_new (struct ospf_lsa *lsa) new->distance = 0; new->children = list_new (); new->parents = list_new (); + new->parents->del = vertex_parent_free; + listnode_add (&vertex_list, new); + + if (IS_DEBUG_OSPF_EVENT) + zlog_debug ("%s: Created %s vertex %s", __func__, + new->type == OSPF_VERTEX_ROUTER ? "Router" : "Network", + inet_ntoa (new->lsa->id)); return new; } -/* Recursively free the given vertex and all its children - * and associated parent and nexthop information - * Parent should indicate which parent is trying to free this child, - * NULL parent is only valid for the root vertex. - */ static void -ospf_vertex_free (struct vertex *v, const struct ospf_area *area) +ospf_vertex_free (void *data) { - struct listnode *node, *nnode; - struct vertex *vc; + struct vertex *v = data; - assert (*(v->stat) == LSA_SPF_IN_SPFTREE); - - /* recurse down the tree, freeing furthest children first */ - if (v->children) - { - for (ALL_LIST_ELEMENTS (v->children, node, nnode, vc)) - ospf_vertex_free (vc, area); - - list_delete (v->children); - v->children = NULL; - } + if (IS_DEBUG_OSPF_EVENT) + zlog_debug ("%s: Free %s vertex %s", __func__, + v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network", + inet_ntoa (v->lsa->id)); - /* The vertex itself can only be freed when the last remaining parent - * with a reference to this vertex frees this vertex. Until then, we - * just cleanup /one/ parent association (doesnt matter which) - - * essentially using the parents list as a refcount. + /* There should be no parents potentially holding references to this vertex + * Children however may still be there, but presumably referenced by other + * vertices */ - if (listcount (v->parents) > 0) - { - vertex_parent_free (listgetdata (listhead (v->parents))); - list_delete_node (v->parents, listhead (v->parents)); - - if (listcount (v->parents) > 0) - return; /* there are still parent references left */ - } + //assert (listcount (v->parents) == 0); - list_delete (v->parents); + if (v->children) + list_delete (v->children); + v->children = NULL; + + if (v->parents) + list_delete (v->parents); v->parents = NULL; v->lsa = NULL; @@ -248,7 +266,7 @@ ospf_vertex_add_parent (struct vertex *v) struct vertex_parent *vp; struct listnode *node; - assert (v && v->children); + assert (v && v->parents); for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp)) { @@ -264,7 +282,7 @@ static void ospf_spf_init (struct ospf_area *area) { struct vertex *v; - + /* Create root node. */ v = ospf_vertex_new (area->router_lsa_self); @@ -455,7 +473,7 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, } if (v == area->spf) - { + { /* 16.1.1 para 4. In the first case, the parent vertex (V) is the root (the calculating router itself). This means that the destination is either a directly connected network or directly @@ -556,11 +574,35 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, ospf_spf_add_parent (v, w, nh); } else + zlog_info("ospf_nexthop_calculation(): " + "could not determine nexthop for link"); + } /* end point-to-point link from V to W */ + else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK) + { + struct ospf_vl_data *vl_data; + + /* VLink implementation limitations: + * a) vl_data can only reference one nexthop, so no ECMP + * to backbone through VLinks. Though transit-area + * summaries may be considered, and those can be ECMP. + * b) We can only use /one/ VLink, even if multiple ones + * exist this router through multiple transit-areas. + */ + vl_data = ospf_vl_lookup (area->ospf, NULL, l->link_id); + + if (vl_data + && CHECK_FLAG (vl_data->flags, OSPF_VL_FLAG_APPROVED)) { - zlog_info("ospf_nexthop_calculation(): " - "could not determine nexthop for link"); + nh = vertex_nexthop_new (); + nh->oi = vl_data->nexthop.oi; + nh->router = vl_data->nexthop.router; + ospf_spf_add_parent (v, w, nh); } - } /* end point-to-point link from V to W */ + else + zlog_info("ospf_nexthop_calculation(): " + "vl_data for VL link not found"); + } /* end virtual-link from V to W */ + return; } /* end W is a Router vertex */ else { @@ -572,8 +614,11 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, nh->oi = oi; nh->router.s_addr = 0; ospf_spf_add_parent (v, w, nh); + return; } } + zlog_info("ospf_nexthop_calculation(): " + "Unknown attached link"); return; } /* end V is the root */ /* Check if W's parent is a network connected to root. */ @@ -616,6 +661,8 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, */ for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp)) ospf_spf_add_parent (v, w, vp->nexthop); + + return; } /* RFC2328 Section 16.1 (2). @@ -757,8 +804,9 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, /* Calculate nexthop to W. */ w->distance = distance; - ospf_nexthop_calculation (area, v, w, l); - pqueue_enqueue (w, candidate); + + ospf_nexthop_calculation (area, v, w, l); + pqueue_enqueue (w, candidate); } else if (w_lsa->stat >= 0) { @@ -1080,8 +1128,10 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, */ ospf_canonical_nexthops_free (area->spf); - /* Free SPF vertices */ - ospf_vertex_free (area->spf, area); + /* Free SPF vertices, but not the list. List has ospf_vertex_free + * as deconstructor. + */ + list_delete_all_node (&vertex_list); /* Increment SPF Calculation Counter. */ area->spf_calculation++; @@ -1089,7 +1139,8 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, gettimeofday (&area->ospf->ts_spf, NULL); if (IS_DEBUG_OSPF_EVENT) - zlog_debug ("ospf_spf_calculate: Stop"); + zlog_debug ("ospf_spf_calculate: Stop. %ld vertices", + mtype_stats_alloc(MTYPE_OSPF_VERTEX)); } /* Timer for SPF calculation. */ @@ -1114,8 +1165,20 @@ ospf_spf_calculate_timer (struct thread *thread) /* Calculate SPF for each area. */ for (ALL_LIST_ELEMENTS (ospf->areas, node, nnode, area)) - ospf_spf_calculate (area, new_table, new_rtrs); - + { + /* Do backbone last, so as to first discover intra-area paths + * for any back-bone virtual-links + */ + if (ospf->backbone && ospf->backbone == area) + continue; + + ospf_spf_calculate (area, new_table, new_rtrs); + } + + /* SPF for backbone, if required */ + if (ospf->backbone) + ospf_spf_calculate (ospf->backbone, new_table, new_rtrs); + ospf_vl_shut_unapproved (ospf); ospf_ia_routing (ospf, new_table, new_rtrs); diff --git a/ospfd/ospf_spf.h b/ospfd/ospf_spf.h index 50e590d6..c1316e4c 100644 --- a/ospfd/ospf_spf.h +++ b/ospfd/ospf_spf.h @@ -20,6 +20,9 @@ * 02111-1307, USA. */ +#ifndef _QUAGGA_OSPF_SPF_H +#define _QUAGGA_OSPF_SPF_H + /* values for vertex->type */ #define OSPF_VERTEX_ROUTER 1 /* for a Router-LSA */ #define OSPF_VERTEX_NETWORK 2 /* for a Network-LSA */ @@ -60,3 +63,5 @@ extern void ospf_spf_calculate_schedule (struct ospf *); extern void ospf_rtrs_free (struct route_table *); /* void ospf_spf_calculate_timer_add (); */ + +#endif /* _QUAGGA_OSPF_SPF_H */ diff --git a/ospfd/ospf_vty.c b/ospfd/ospf_vty.c index 0b74bdf1..74361bcb 100644 --- a/ospfd/ospf_vty.c +++ b/ospfd/ospf_vty.c @@ -722,7 +722,7 @@ ospf_find_vl_data (struct ospf *ospf, struct ospf_vl_config_data *vl_config) return NULL; } - if ((vl_data = ospf_vl_lookup (area, vl_config->vl_peer)) == NULL) + if ((vl_data = ospf_vl_lookup (ospf, area, vl_config->vl_peer)) == NULL) { vl_data = ospf_vl_data_new (area, vl_config->vl_peer); if (vl_data->vl_oi == NULL) @@ -1074,7 +1074,7 @@ DEFUN (no_ospf_area_vlink, { /* Basic VLink no command */ /* Thats all folks! - BUGS B. strikes again!!!*/ - if ((vl_data = ospf_vl_lookup (area, vl_config.vl_peer))) + if ((vl_data = ospf_vl_lookup (ospf, area, vl_config.vl_peer))) ospf_vl_delete (ospf, vl_data); ospf_area_check_free (ospf, vl_config.area_id); @@ -2736,10 +2736,27 @@ show_ip_ospf_interface_sub (struct vty *vty, struct ospf *ospf, vty_out (vty, " Internet Address %s/%d,", inet_ntoa (oi->address->u.prefix4), oi->address->prefixlen); - if (oi->connected->destination) - vty_out (vty, " %s %s,", - ((ifp->flags & IFF_POINTOPOINT) ? "Peer" : "Broadcast"), - inet_ntoa (oi->connected->destination->u.prefix4)); + if (oi->connected->destination || oi->type == OSPF_IFTYPE_VIRTUALLINK) + { + struct in_addr *dest; + const char *dstr; + + if ((ifp->flags & IFF_POINTOPOINT) + || oi->type == OSPF_IFTYPE_VIRTUALLINK) + dstr = "Peer"; + else + dstr = "Broadcast"; + + /* For Vlinks, showing the peer address is probably more + * informative than the local interface that is being used + */ + if (oi->type == OSPF_IFTYPE_VIRTUALLINK) + dest = &oi->vl_data->peer_addr; + else + dest = &oi->connected->destination->u.prefix4; + + vty_out (vty, " %s %s,", dstr, inet_ntoa (*dest)); + } vty_out (vty, " Area %s%s", ospf_area_desc_string (oi->area), VTY_NEWLINE); |