[ospfd] Fix SPF of virtual-links
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.
diff --git a/ospfd/ChangeLog b/ospfd/ChangeLog
index ac59670..99599f5 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 52adc42..1264cac 100644
--- a/ospfd/ospf_interface.c
+++ b/ospfd/ospf_interface.c
@@ -931,16 +931,36 @@
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 @@
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 @@
&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 @@
{
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 28d95d7..3c75940 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 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 @@
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 5eedbd8..646b625 100644
--- a/ospfd/ospf_route.c
+++ b/ospfd/ospf_route.c
@@ -343,8 +343,9 @@
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 dbd0636..7228d2d 100644
--- a/ospfd/ospf_spf.c
+++ b/ospfd/ospf_spf.c
@@ -46,6 +46,13 @@
#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 @@
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 @@
}
/* 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 @@
/* 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 @@
}
static void
-vertex_parent_free (struct vertex_parent *p)
+vertex_parent_free (void *p)
{
XFREE (MTYPE_OSPF_VERTEX_PARENT, p);
}
@@ -148,48 +175,39 @@
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);
+ 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));
- /* 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;
- }
-
- /* 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 @@
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 @@
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 @@
}
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_spf_add_parent (v, w, nh);
}
else
- {
- zlog_info("ospf_nexthop_calculation(): "
- "could not determine nexthop for link");
- }
+ 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))
+ {
+ nh = vertex_nexthop_new ();
+ nh->oi = vl_data->nexthop.oi;
+ nh->router = vl_data->nexthop.router;
+ ospf_spf_add_parent (v, w, nh);
+ }
+ 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 @@
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 @@
*/
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 @@
/* 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_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 @@
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 @@
/* 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 50e590d..c1316e4 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_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 0b74bdf..74361bc 100644
--- a/ospfd/ospf_vty.c
+++ b/ospfd/ospf_vty.c
@@ -722,7 +722,7 @@
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 @@
{
/* 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 @@
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);